Cubic graph

The Petersen graph is a cubic graph.
The complete bipartite graph is an example of a bicubic 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.

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, the cubic graphs with 2g-2 vertices describe the different ways of cutting a surface of genus g ≥ 2 into pairs of pants. 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?

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

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, archived from the original on 2011-07-16, retrieved 2010-07-21.
  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.

Read other articles:

Wing Udara 3 TempurLanud IswahyudiLambang Wing Udara 3Dibentuk5 Mei 2000Negara IndonesiaCabang TNI Angkatan UdaraTipe unitSatuan Tempur Buru SergapBagian dariLanud IswahyudiMotoLabda Gagana NirwestiSitus webwww.lanud-iswahjudi.mil.id Wing Udara 3 Tempur adalah satuan yang bertugas menyelenggarakan pembinaan teknis dalam rangka kesiapan operasi awak pesawat skadron udara yang berada dalam jajarannya.[1] Wing Udara 3 berada di bawah kendali Lanud Iswahyudi, (Komando Operasi Angkata...

American Catholic episcopal conference United States Conference of Catholic BishopsAbbreviationUSCCBFormation1966TypeNon-governmental organizationLegal statusCivil nonprofitPurposeTo act collaboratively and consistently on vital issues confronting the Church and society.To foster communion with the Church in other nations, within the Church universal, under the leadership of its supreme pastor, the Roman Pontiff.To offer appropriate assistance to each bishop in fulfilling his particular minis...

              • 1951 → Elecciones parlamentarias de Israel de 1949Elección de los 120 miembros del Knesset Fecha 25 de enero de 1949 Tipo Legislativa Demografía electoral Hab. registrados 506,567 Votantes 440,095 Participación    86.88 % Resultados Mapai - David Ben Gurión Votos 155,274   Escaños obtenidos 46      35.72 % Mapam - Meir Ya'ari Votos 64,018...

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (نوفمبر 2018) كلوديا باسولس معلومات شخصية الميلاد 3 أكتوبر 1979 (44 سنة)  برشلونة  مواطنة إسبانيا  الحياة العملية المدرسة الأم المعهد الوطني للفنون المسرحيةجامعة كارو

بوابة محمديةمعلومات عامةنوع المبنى بوابةالمنطقة الإدارية District 12 (en) [1][2] البلد  إيرانبني بطلب من محمد شاه قاجار[2] أبرز الأحداثالافتتاح الرسمي 1847 التفاصيل التقنيةجزء من Tahmasp Wall (en) [2] — بازار طهران الكبير[2] مواد البناء طابوق[2] قصارة[2] بلاط[2&#...

Twin-engine light utility helicopter EC145 H145 A EC145 from the Stanford Medical Center Role Light utility helicopterType of aircraft National origin Multinational Manufacturer Eurocopter / Kawasaki Aerospace Company Airbus Helicopters First flight 12 June 1999 Introduction 2002 Status In service Produced 1999–present Number built over 1,500[1] Developed from MBB/Kawasaki BK 117 Variants Eurocopter UH-72 Lakota The Airbus Helicopters H145 (formerly Eurocopter EC145) is a twin-engin...

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يوليو 2019) ميخائيل دان معلومات شخصية الميلاد 11 سبتمبر 1921  ديترويت  تاريخ الوفاة 27 مايو 2016 (94 سنة) [1]  مواطنة الولايات المتحدة  الحياة العملية المدرسة الأم �...

La plaza de Isabel II, es una pequeña plaza situada al comienzo de la calle de la Marina en la ciudad de Santa Cruz de Tenerife. Popularmente ha sido conocida como Chorro de Isabel II, Chorro de Santa Isabel y por La Pila. Su nombre fue cambiado por el de Patricio Estévanez el 13 de mayo de 1931, pero el 5 de octubre de 1936 la Comisión Gestora Municipal acordó restituirle su nombre actual.[1]​ Fuente Fuente de Isabel II La plaza posee una fuente neoclásica de orden toscano, diseñ...

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Maret 2023. Reformasi administrasi (dalam bahasa Inggris: administrative reform) adalah sebuah perubahan terstruktur mengenai suatu sistem administrasi dalam usaha membawa perubahan besar-besaran dalam sistem birokrasi sehingga menjadi lebih efektif.[1] Peng...

Dramatic tradition of classical India History of literatureby era Ancient (corpora) Bronze Age Sumerian Ancient Egyptian Akkadian Ugarit Hittite Classical Classical Chinese Aramaic Ancient Greek Ancient Hebrew Classical Latin Ancient Meitei Syriac Prakrit Tamil Sangam Classical Sanskrit Early Medieval Telugu Kannada New Persian Pali Armenian Byzantine Greek Welsh Old English Georgian Old German Japanese Old Turkic Arabic Norse Bulgarian Medieval by century 10th 11th 12th 13th 14th Early Moder...

Konstantin KorovinPortrait of Konstantin Korovin, by Valentin Serov, 1891Lahir5 December [K.J.: 23 November] 1861Moscow, Kekaisaran RusiaMeninggal11 September 1939(1939-09-11) (umur 77)Paris, PrancisKebangsaanRussiaPendidikanMember Academy of Arts (1905)Dikenal atasLukisanKarya terkenalHammerfest: Aurora Borealis 1894–1895Portrait of Feodor Chaliapin 1915Gerakan politikImpresionismePenghargaanLegion of Honour Konstantin Alekseyevich Korovin (bahasa Rusia: Константи́н А�...

Опис Обкладинка пісні Коді Сімпсона iYiYi за участі Flo Rida Джерело http://www.rnbxbeatz.com/2010/06/05/cody-simpson-%E2%80%93-iyiyi-ep/ Час створення 2010 Автор зображення Atlantic Records Ліцензія Це зображення є обкладинкою музичного альбому або синглу. Найімовірніше, авторськими правами на обкладинку володіє в...

State park in Hartford County, Connecticut Talcott Mountain State ParkView of the Hartford skyline from Heublein TowerLocation in ConnecticutShow map of ConnecticutTalcott Mountain State Park (the United States)Show map of the United StatesLocationAvon, Bloomfield & Simsbury, Connecticut, United StatesCoordinates41°49′25″N 72°47′56″W / 41.82361°N 72.79889°W / 41.82361; -72.79889[1]Area574 acres (232 ha)[2]Elevation915 ft (279&#...

Patti WebsterBorn(1964-06-18)June 18, 1964Somerville, New Jersey, United StatesDiedSeptember 13, 2013(2013-09-13) (aged 49)Somerville, New Jersey, United StatesAlma materVirginia TechOccupation(s)Publicist, author, Christian minister Patti Webster (June 18, 1964 – September 13, 2013) was an American entertainment publicist, author, and minister. As the CEO of W&W Public Relations, a company she founded in 1991, Webster represented notable recording artists, athletes, and actor...

Hamlet in County Antrim, Northern Ireland Human settlement in Northern IrelandKnocknacarryIrish: Cnoc na Caraidh / Cnoc na Cora[1]KnocknacarryLocation within Northern IrelandPopulation138 (2001 Census)DistrictCauseway Coast and GlensCountyCounty AntrimCountryNorthern IrelandSovereign stateUnited KingdomPost townBallymenaPostcode districtBT44Dialling code028UK ParliamentNorth AntrimNI AssemblyNorth Antrim List of places UK Northern Ireland Antrim 55°07′...

Hospital in South Ayrshire, ScotlandUniversity Hospital AyrNHS Ayrshire and ArranUniversity Hospital AyrShown in South AyrshireGeographyLocationAyr, South Ayrshire, ScotlandCoordinates55°25′50″N 4°35′35″W / 55.43056°N 4.59306°W / 55.43056; -4.59306OrganisationCare systemNHS ScotlandTypeDistrict generalAffiliated universityUniversity of the West of ScotlandServicesEmergency departmentYes Accident & EmergencyBeds333HistoryOpened1991LinksWebsiteUniversity ...

Scout Laws by country This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by adding missing items with reliable sources. Scout Laws by countryWorld Organization of the Scout Movement map  Scouting portal The following is a list of Scout Laws in national Scout and Guide organizations. Africa Scout Region Africa Scout Region South Africa Main article: Scouts South Africa A Scout's honour is to be trusted A Scout is loyal A Scout's dut...

2016 aggravated rape and murder in Germany Murder of Maria LadenburgerFlowers at the river Dreisam where the body was foundTime16 October 2016(2016-10-16) (aged 19)LocationFreiburg im Breisgau, Baden-Württemberg, GermanyCoordinates47°59′25″N 7°53′35″E / 47.990165°N 7.893157°E / 47.990165; 7.893157 (murder site)DeathsMaria LadenburgerConvictedHussein KhavariConvictionsMurder, aggravated rapeSentenceLife imprisonment Maria Ladenburger (6 Decembe...

2008 Montana Republican presidential caucuses and primary ← 2004 February 5, 2008 (2008-02-05) 2012 →   Candidate Mitt Romney Ron Paul John McCain Home state Massachusetts Texas Arizona Popular vote 625 400 358 Percentage 38.34% 24.54% 21.96%   Candidate Mike Huckabee Home state Arkansas Popular vote 245 Percentage 15.03% Election results by county.   Mitt Romney   Ron Paul   John McCain  ...

Protected area in Queensland, AustraliaBellthorpe National ParkQueenslandIUCN category II (national park) The range in the background is in the national park.Bellthorpe National ParkNearest town or cityWoodfordCoordinates26°51′57″S 152°41′21″E / 26.86583°S 152.68917°E / -26.86583; 152.68917Area75.5 km2 (29.2 sq mi)Managing authoritiesQueensland Parks and Wildlife ServiceWebsiteBellthorpe National ParkSee alsoProtected areas of Queensland Bell...