| 词条 | Quartic graph |
| 释义 |
In the mathematical field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph.[1] ExamplesSeveral well-known graphs are quartic. They include:
Every medial graph is a quartic plane graph, and every quartic plane graph is the medial graph of a pair of dual plane graphs or multigraphs.[5] Knot diagrams and link diagrams are also quartic plane multigraphs, in which the vertices represent the crossings of the diagram and are marked with additional information concerning which of the two branches of the knot crosses the other branch at that point.[6] PropertiesBecause the degree of every vertex in a quartic graph is even, every connected quartic graph has an Euler tour. And as with regular bipartite graphs more generally, every bipartite quartic graph has a perfect matching. In this case, a much simpler and faster algorithm for finding such a matching is possible than for irregular graphs: by selecting every other edge of an Euler tour, one may find a 2-factor, which in this case must be a collection of cycles, each of even length, with each vertex of the graph appearing in exactly one cycle. By selecting every other edge again in these cycles, one obtains a perfect matching in linear time. The same method can also be used to color the edges of the graph with four colors in linear time.[7] Quartic graphs have an even number of Hamiltonian decompositions.[8] Open problemsIt is an open conjecture whether all quartic Hamiltonian graphs have an even number of Hamiltonian circuits, or have more than one Hamiltonian circuit. The answer is known to be false for quartic multigraphs.[9] See also{{commons category|4-regular graphs}}
References1. ^{{citation | last = Toida | first = S. | journal = Journal of Combinatorial Theory | mr = 0347693 | pages = 124–133 | series = Series B | title = Construction of quartic graphs | volume = 16 | year = 1974 | doi=10.1016/0095-8956(74)90054-9}}. 2. ^{{citation | last = Chvátal | first = V. | author-link = Václav Chvátal | doi = 10.1016/S0021-9800(70)80057-6 | issue = 1 | journal = Journal of Combinatorial Theory | pages = 93–94 | title = The smallest triangle-free 4-chromatic 4-regular graph | volume = 9 | year = 1970}}. 3. ^{{citation | last = Folkman | first = Jon | journal = Journal of Combinatorial Theory | mr = 0224498 | pages = 215–232 | title = Regular line-symmetric graphs | volume = 3 | year = 1967 | doi=10.1016/s0021-9800(67)80069-3}}. 4. ^{{citation | last = Meredith | first = G. H. J. | journal = Journal of Combinatorial Theory | mr = 0311503 | pages = 55–60 | series = Series B | title = Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs | volume = 14 | year = 1973 | doi=10.1016/s0095-8956(73)80006-1}}. 5. ^{{citation | last1 = Bondy | first1 = J. A. | last2 = Häggkvist | first2 = R. | doi = 10.1007/BF02190157 | issue = 1 | journal = Aequationes Mathematicae | mr = 623315 | pages = 42–45 | title = Edge-disjoint Hamilton cycles in 4-regular planar graphs | volume = 22 | year = 1981}}. 6. ^{{citation | last = Welsh | first = Dominic J. A. | authorlink = Dominic Welsh | contribution = The complexity of knots | doi = 10.1016/S0167-5060(08)70385-6 | location = Amsterdam | mr = 1217989 | pages = 159–171 | publisher = North-Holland | series = Annals of Discrete Mathematics | title = Quo vadis, graph theory? | volume = 55 | year = 1993}}. 7. ^{{citation | last = Gabow | first = Harold N. | issue = 4 | journal = International Journal of Computer and Information Sciences | mr = 0422081 | pages = 345–355 | title = Using Euler partitions to edge color bipartite multigraphs | volume = 5 | year = 1976 | doi=10.1007/bf00998632}}. 8. ^{{citation | last = Thomason | first = A. G. | journal = Annals of Discrete Mathematics | mr = 499124 | pages = 259–268 | title = Hamiltonian cycles and uniquely edge colourable graphs | volume = 3 | year = 1978 | doi=10.1016/s0167-5060(08)70511-9}}. 9. ^{{citation | last = Fleischner | first = Herbert | doi = 10.1002/jgt.3190180503 | issue = 5 | journal = Journal of Graph Theory | mr = 1283310 | pages = 449–459 | title = Uniqueness of maximal dominating cycles in 3-regular graphs and of Hamiltonian cycles in 4-regular graphs | volume = 18 | year = 1994}}. External links
2 : Graph families|Regular graphs |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。