fbpx
Wikipedia

Cubic graph

May 17, 2023

Not to be confused with graphs of cubic functions, hypercube graph, cube graph, cubical graph.

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

The Petersen graph is a cubic graph.
The complete bipartite graph is an example of a bicubic graph

A bicubic graph is a cubic bipartite graph.

Symmetry

In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.[1] Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number s such that each two oriented paths of length s can be mapped to each other by exactly one symmetry of the graph. He showed that s is at most 5, and provided examples of graphs with each possible value of s from 1 to 5.[2]

Semi-symmetric cubic graphs include the Gray graph (the smallest semi-symmetric cubic graph), the Ljubljana graph, and the Tutte 12-cage.

The Frucht graph is one of the five smallest cubic graphs without any symmetries:[3] it possesses only a single graph automorphism, the identity automorphism.[4]

Coloring and independent sets

According to Brooks' theorem every connected cubic graph other than the complete graph K4 has a vertex coloring with at most three colors. Therefore, every connected cubic graph other than K4 has an independent set of at least n/3 vertices, where n is the number of vertices in the graph: for instance, the largest color class in a 3-coloring has at least this many vertices.

According to Vizing's theorem every cubic graph needs either three or four colors for an edge coloring. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings. By Kőnig's line coloring theorem every bicubic graph has a Tait coloring.

The bridgeless cubic graphs that do not have a Tait coloring are known as snarks. They include the Petersen graph, Tietze's graph, the Blanuša snarks, the flower snark, the double-star snark, the Szekeres snark and the Watkins snark. There is an infinite number of distinct snarks.[5]

Topology and geometry

Cubic graphs arise naturally in topology in several ways. For example, if one considers a graph to be a 1-dimensional CW complex, cubic graphs are generic in that most 1-cell attaching maps are disjoint from the 0-skeleton of the graph. Cubic graphs are also formed as the graphs of simple polyhedra in three dimensions, polyhedra such as the regular dodecahedron with the property that three faces meet at every vertex.

 
Representation of a planar embedding as a graph-encoded map

An arbitrary graph embedding on a two-dimensional surface may be represented as a cubic graph structure known as a graph-encoded map. In this structure, each vertex of a cubic graph represents a flag of the embedding, a mutually incident triple of a vertex, edge, and face of the surface. The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple and leaving the other two members unchanged.[6]

Hamiltonicity

There has been much research on Hamiltonicity of cubic graphs. In 1880, P.G. Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example to Tait's conjecture, the 46-vertex Tutte graph, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices, the Horton graph.[7] Later, Mark Ellingham constructed two more counterexamples: the Ellingham–Horton graphs.[8][9] Barnette's conjecture, a still-open combination of Tait's and Tutte's conjecture, states that every bicubic polyhedral graph is Hamiltonian. When a cubic graph is Hamiltonian, LCF notation allows it to be represented concisely.

If a cubic graph is chosen uniformly at random among all n-vertex cubic graphs, then it is very likely to be Hamiltonian: the proportion of the n-vertex cubic graphs that are Hamiltonian tends to one in the limit as n goes to infinity.[10]

David Eppstein conjectured that every n-vertex cubic graph has at most 2n/3 (approximately 1.260n) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles.[11] The best proven estimate for the number of distinct Hamiltonian cycles is  .[12]

Other properties

Unsolved problem in mathematics:

What is the largest possible pathwidth of an  -vertex cubic graph?

(more unsolved problems in mathematics)

The pathwidth of any n-vertex cubic graph is at most n/6. The best known lower bound on the pathwidth of cubic graphs is 0.082n. It is not known how to reduce this gap between this lower bound and the n/6 upper bound.[13]

It follows from the handshaking lemma, proven by Leonhard Euler in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices.

Petersen's theorem states that every cubic bridgeless graph has a perfect matching.[14]Lovász and Plummer conjectured that every cubic bridgeless graph has an exponential number of perfect matchings. The conjecture was recently proved, showing that every cubic bridgeless graph with n vertices has at least 2n/3656 perfect matchings.[15]

Algorithms and complexity

Several researchers have studied the complexity of exponential time algorithms restricted to cubic graphs. For instance, by applying dynamic programming to a path decomposition of the graph, Fomin and Høie showed how to find their maximum independent sets in time 2n/6 + o(n).[13] The travelling salesman problem in cubic graphs can be solved in time O(1.2312n) and polynomial space.[16][17]

Several important graph optimization problems are APX hard, meaning that, although they have approximation algorithms whose approximation ratio is bounded by a constant, they do not have polynomial time approximation schemes whose approximation ratio tends to 1 unless P=NP. These include the problems of finding a minimum vertex cover, maximum independent set, minimum dominating set, and maximum cut.[18] The crossing number (the minimum number of edges which cross in any graph drawing) of a cubic graph is also NP-hard for cubic graphs but may be approximated.[19] The Travelling Salesman Problem on cubic graphs has been proven to be NP-hard to approximate to within any factor less than 1153/1152.[20]

See also

 
Wikimedia Commons has media related to 3-regular graphs.

References

  1. ^ Foster, R. M. (1932), "Geometrical Circuits of Electrical Networks", Transactions of the American Institute of Electrical Engineers, 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068, S2CID 51638449.
  2. ^ Tutte, W. T. (1959), "On the symmetry of cubic graphs", Can. J. Math., 11: 621–624, doi:10.4153/CJM-1959-057-2, S2CID 124273238.
  3. ^ Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1976), Computer investigation of cubic graphs, EUT report, vol. 76-WSK-01, Dept. of Mathematics and Computing Science, Eindhoven University of Technology
  4. ^ Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987, S2CID 124723321.
  5. ^ Isaacs, R. (1975), "Infinite families of nontrivial trivalent graphs which are not Tait colorable", American Mathematical Monthly, 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844.
  6. ^ Bonnington, C. Paul; Little, Charles H. C. (1995), The Foundations of Topological Graph Theory, Springer-Verlag.
  7. ^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
  8. ^ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
  9. ^ Ellingham, M. N.; Horton, J. D. (1983), "Non-Hamiltonian 3-connected cubic bipartite graphs", Journal of Combinatorial Theory, Series B, 34 (3): 350–353, doi:10.1016/0095-8956(83)90046-1.
  10. ^ Robinson, R.W.; Wormald, N.C. (1994), "Almost all regular graphs are Hamiltonian", Random Structures and Algorithms, 5 (2): 363–374, doi:10.1002/rsa.3240050209.
  11. ^ Eppstein, David (2007), "The traveling salesman problem for cubic graphs" (PDF), Journal of Graph Algorithms and Applications, 11 (1): 61–81, arXiv:cs.DS/0302030, doi:10.7155/jgaa.00137.
  12. ^ Gebauer, H. (2008), "On the number of Hamilton cycles in bounded degree graphs", Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), pp. 241–248, doi:10.1137/1.9781611972986.8, ISBN 9781611972986.
  13. ^ a b Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", Information Processing Letters, 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012.
  14. ^ Petersen, Julius Peter Christian (1891), "Die Theorie der regulären Graphs (The theory of regular graphs)", Acta Mathematica, 15 (15): 193–220, doi:10.1007/BF02392606, S2CID 123779343.
  15. ^ Esperet, Louis; Kardoš, František; King, Andrew D.; Kráľ, Daniel; Norine, Serguei (2011), "Exponentially many perfect matchings in cubic graphs", Advances in Mathematics, 227 (4): 1646–1664, arXiv:1012.2878, doi:10.1016/j.aim.2011.03.015, S2CID 4401537.
  16. ^ Xiao, Mingyu; Nagamochi, Hiroshi (2013), "An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure", Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 7876, Springer-Verlag, pp. 96–107, arXiv:1212.6831, doi:10.1007/978-3-642-38236-9_10, ISBN 978-3-642-38236-9.
  17. ^ Xiao, Mingyu; Nagamochi, Hiroshi (2012), "An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure", Algorithmica, 74 (2): 713–741, arXiv:1212.6831, Bibcode:2012arXiv1212.6831X, doi:10.1007/s00453-015-9970-4, S2CID 7654681.
  18. ^ Alimonti, Paola; Kann, Viggo (2000), "Some APX-completeness results for cubic graphs", Theoretical Computer Science, 237 (1–2): 123–134, doi:10.1016/S0304-3975(98)00158-3.
  19. ^ Hliněný, Petr (2006), "Crossing number is hard for cubic graphs", Journal of Combinatorial Theory, Series B, 96 (4): 455–471, doi:10.1016/j.jctb.2005.09.009.
  20. ^ Karpinski, Marek; Schmied, Richard (2013), Approximation Hardness of Graphic TSP on Cubic Graphs, arXiv:1304.6800, Bibcode:2013arXiv1304.6800K.

External links

May 17, 2023
cubic, graph, confused, with, graphs, cubic, functions, hypercube, graph, cube, graph, cubical, graph, mathematical, field, graph, theory, cubic, graph, graph, which, vertices, have, degree, three, other, words, cubic, graph, regular, graph, also, called, triv. Not to be confused with graphs of cubic functions hypercube graph cube graph cubical graph In the mathematical field of graph theory a cubic graph is a graph in which all vertices have degree three In other words a cubic graph is a 3 regular graph Cubic graphs are also called trivalent graphs The Petersen graph is a cubic graph The complete bipartite graph K 3 3 displaystyle K 3 3 is an example of a bicubic graph A bicubic graph is a cubic bipartite graph Contents 1 Symmetry 2 Coloring and independent sets 3 Topology and geometry 4 Hamiltonicity 5 Other properties 6 Algorithms and complexity 7 See also 8 References 9 External linksSymmetry EditIn 1932 Ronald M Foster began collecting examples of cubic symmetric graphs forming the start of the Foster census 1 Many well known individual graphs are cubic and symmetric including the utility graph the Petersen graph the Heawood graph the Mobius Kantor graph the Pappus graph the Desargues graph the Nauru graph the Coxeter graph the Tutte Coxeter graph the Dyck graph the Foster graph and the Biggs Smith graph W T Tutte classified the symmetric cubic graphs by the smallest integer number s such that each two oriented paths of length s can be mapped to each other by exactly one symmetry of the graph He showed that s is at most 5 and provided examples of graphs with each possible value of s from 1 to 5 2 Semi symmetric cubic graphs include the Gray graph the smallest semi symmetric cubic graph the Ljubljana graph and the Tutte 12 cage The Frucht graph is one of the five smallest cubic graphs without any symmetries 3 it possesses only a single graph automorphism the identity automorphism 4 Coloring and independent sets EditAccording to Brooks theorem every connected cubic graph other than the complete graph K4 has a vertex coloring with at most three colors Therefore every connected cubic graph other than K4 has an independent set of at least n 3 vertices where n is the number of vertices in the graph for instance the largest color class in a 3 coloring has at least this many vertices According to Vizing s theorem every cubic graph needs either three or four colors for an edge coloring A 3 edge coloring is known as a Tait coloring and forms a partition of the edges of the graph into three perfect matchings By Konig s line coloring theorem every bicubic graph has a Tait coloring The bridgeless cubic graphs that do not have a Tait coloring are known as snarks They include the Petersen graph Tietze s graph the Blanusa snarks the flower snark the double star snark the Szekeres snark and the Watkins snark There is an infinite number of distinct snarks 5 Topology and geometry EditCubic graphs arise naturally in topology in several ways For example if one considers a graph to be a 1 dimensional CW complex cubic graphs are generic in that most 1 cell attaching maps are disjoint from the 0 skeleton of the graph Cubic graphs are also formed as the graphs of simple polyhedra in three dimensions polyhedra such as the regular dodecahedron with the property that three faces meet at every vertex Representation of a planar embedding as a graph encoded map An arbitrary graph embedding on a two dimensional surface may be represented as a cubic graph structure known as a graph encoded map In this structure each vertex of a cubic graph represents a flag of the embedding a mutually incident triple of a vertex edge and face of the surface The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple and leaving the other two members unchanged 6 Hamiltonicity EditThere has been much research on Hamiltonicity of cubic graphs In 1880 P G Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit William Thomas Tutte provided a counter example to Tait s conjecture the 46 vertex Tutte graph in 1946 In 1971 Tutte conjectured that all bicubic graphs are Hamiltonian However Joseph Horton provided a counterexample on 96 vertices the Horton graph 7 Later Mark Ellingham constructed two more counterexamples the Ellingham Horton graphs 8 9 Barnette s conjecture a still open combination of Tait s and Tutte s conjecture states that every bicubic polyhedral graph is Hamiltonian When a cubic graph is Hamiltonian LCF notation allows it to be represented concisely If a cubic graph is chosen uniformly at random among all n vertex cubic graphs then it is very likely to be Hamiltonian the proportion of the n vertex cubic graphs that are Hamiltonian tends to one in the limit as n goes to infinity 10 David Eppstein conjectured that every n vertex cubic graph has at most 2n 3 approximately 1 260n distinct Hamiltonian cycles and provided examples of cubic graphs with that many cycles 11 The best proven estimate for the number of distinct Hamiltonian cycles is O 1 276 n displaystyle O 1 276 n 12 Other properties EditUnsolved problem in mathematics What is the largest possible pathwidth of an n displaystyle n vertex cubic graph more unsolved problems in mathematics The pathwidth of any n vertex cubic graph is at most n 6 The best known lower bound on the pathwidth of cubic graphs is 0 082n It is not known how to reduce this gap between this lower bound and the n 6 upper bound 13 It follows from the handshaking lemma proven by Leonhard Euler in 1736 as part of the first paper on graph theory that every cubic graph has an even number of vertices Petersen s theorem states that every cubic bridgeless graph has a perfect matching 14 Lovasz and Plummer conjectured that every cubic bridgeless graph has an exponential number of perfect matchings The conjecture was recently proved showing that every cubic bridgeless graph with n vertices has at least 2n 3656 perfect matchings 15 Algorithms and complexity EditSeveral researchers have studied the complexity of exponential time algorithms restricted to cubic graphs For instance by applying dynamic programming to a path decomposition of the graph Fomin and Hoie showed how to find their maximum independent sets in time 2n 6 o n 13 The travelling salesman problem in cubic graphs can be solved in time O 1 2312n and polynomial space 16 17 Several important graph optimization problems are APX hard meaning that although they have approximation algorithms whose approximation ratio is bounded by a constant they do not have polynomial time approximation schemes whose approximation ratio tends to 1 unless P NP These include the problems of finding a minimum vertex cover maximum independent set minimum dominating set and maximum cut 18 The crossing number the minimum number of edges which cross in any graph drawing of a cubic graph is also NP hard for cubic graphs but may be approximated 19 The Travelling Salesman Problem on cubic graphs has been proven to be NP hard to approximate to within any factor less than 1153 1152 20 See also Edit Wikimedia Commons has media related to 3 regular graphs Table of simple cubic graphsReferences Edit Foster R M 1932 Geometrical Circuits of Electrical Networks Transactions of the American Institute of Electrical Engineers 51 2 309 317 doi 10 1109 T AIEE 1932 5056068 S2CID 51638449 Tutte W T 1959 On the symmetry of cubic graphs Can J Math 11 621 624 doi 10 4153 CJM 1959 057 2 S2CID 124273238 Bussemaker F C Cobeljic S Cvetkovic D M Seidel J J 1976 Computer investigation of cubic graphs EUT report vol 76 WSK 01 Dept of Mathematics and Computing Science Eindhoven University of Technology Frucht R 1949 Graphs of degree three with a given abstract group Canadian Journal of Mathematics 1 4 365 378 doi 10 4153 CJM 1949 033 6 ISSN 0008 414X MR 0032987 S2CID 124723321 Isaacs R 1975 Infinite families of nontrivial trivalent graphs which are not Tait colorable American Mathematical Monthly 82 3 221 239 doi 10 2307 2319844 JSTOR 2319844 Bonnington C Paul Little Charles H C 1995 The Foundations of Topological Graph Theory Springer Verlag Bondy J A and Murty U S R Graph Theory with Applications New York North Holland p 240 1976 Ellingham M N Non Hamiltonian 3 Connected Cubic Partite Graphs Research Report No 28 Dept of Math Univ Melbourne Melbourne 1981 Ellingham M N Horton J D 1983 Non Hamiltonian 3 connected cubic bipartite graphs Journal of Combinatorial Theory Series B 34 3 350 353 doi 10 1016 0095 8956 83 90046 1 Robinson R W Wormald N C 1994 Almost all regular graphs are Hamiltonian Random Structures and Algorithms 5 2 363 374 doi 10 1002 rsa 3240050209 Eppstein David 2007 The traveling salesman problem for cubic graphs PDF Journal of Graph Algorithms and Applications 11 1 61 81 arXiv cs DS 0302030 doi 10 7155 jgaa 00137 Gebauer H 2008 On the number of Hamilton cycles in bounded degree graphs Proc 4th Workshop on Analytic Algorithmics and Combinatorics ANALCO 08 pp 241 248 doi 10 1137 1 9781611972986 8 ISBN 9781611972986 a b Fomin Fedor V Hoie Kjartan 2006 Pathwidth of cubic graphs and exact algorithms Information Processing Letters 97 5 191 196 doi 10 1016 j ipl 2005 10 012 Petersen Julius Peter Christian 1891 Die Theorie der regularen Graphs The theory of regular graphs Acta Mathematica 15 15 193 220 doi 10 1007 BF02392606 S2CID 123779343 Esperet Louis Kardos Frantisek King Andrew D Kraľ Daniel Norine Serguei 2011 Exponentially many perfect matchings in cubic graphs Advances in Mathematics 227 4 1646 1664 arXiv 1012 2878 doi 10 1016 j aim 2011 03 015 S2CID 4401537 Xiao Mingyu Nagamochi Hiroshi 2013 An Exact Algorithm for TSP in Degree 3 Graphs via Circuit Procedure and Amortization on Connectivity Structure Theory and Applications of Models of Computation Lecture Notes in Computer Science vol 7876 Springer Verlag pp 96 107 arXiv 1212 6831 doi 10 1007 978 3 642 38236 9 10 ISBN 978 3 642 38236 9 Xiao Mingyu Nagamochi Hiroshi 2012 An Exact Algorithm for TSP in Degree 3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure Algorithmica 74 2 713 741 arXiv 1212 6831 Bibcode 2012arXiv1212 6831X doi 10 1007 s00453 015 9970 4 S2CID 7654681 Alimonti Paola Kann Viggo 2000 Some APX completeness results for cubic graphs Theoretical Computer Science 237 1 2 123 134 doi 10 1016 S0304 3975 98 00158 3 Hlineny Petr 2006 Crossing number is hard for cubic graphs Journal of Combinatorial Theory Series B 96 4 455 471 doi 10 1016 j jctb 2005 09 009 Karpinski Marek Schmied Richard 2013 Approximation Hardness of Graphic TSP on Cubic Graphs arXiv 1304 6800 Bibcode 2013arXiv1304 6800K External links EditRoyle Gordon Cubic symmetric graphs The Foster Census Archived from the original on 2011 10 23 Weisstein Eric W Bicubic Graph MathWorld Weisstein Eric W Cubic Graph MathWorld Retrieved from https en wikipedia org w index php title Cubic graph amp oldid 1136140068, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.