×

Hamilton weights and Petersen minors. (English) Zbl 0996.05088

Summary: A \((1,2)\)-Eulerian weight \(w\) of a cubic graph is called a Hamilton weight if every faithful circuit cover of the graph with respect to \(w\) is a set of two Hamilton circuits. Let \(G\) be a 3-connected cubic graph containing no Petersen minor. It is proved in this paper that \(G\) admits a Hamilton weight if and only if \(G\) can be obtained from \(K_4\) by a series of \(\Delta\leftrightarrow Y\)-operations. As a byproduct of the proof of the main theorem, we also prove that if \(G\) is a permutation graph and \(w\) is a \((1,2)\)-Eulerian weight of \(G\) such that \((G,w)\) is a critical contra pair, then the Petersen minor appears “almost everywhere” in the graph \(G\).

MSC:

05C45 Eulerian and Hamiltonian graphs
05C83 Graph minors
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, Discrete Math 111 pp 11– (1993) · Zbl 0789.05075 · doi:10.1016/0012-365X(93)90135-G
[2] Alspach, Trans Amer Math Soc 344 pp 131– (1994) · doi:10.1090/S0002-9947-1994-1181180-1
[3] Ellingham, Congr Numer 44 pp 33– (1984)
[4] Fleischner, Congr Numer 63 pp 9– (1988)
[5] and Edge colourings of graphs, Research Notes in Mathematics No. 16, Piman, 1977. · Zbl 0421.05023
[6] and Edge colourings of graphs, Selected Topics in Graph Theory, and (Editors), Academic Press, London, 1978, 103-126.
[7] Cycle double covers-current status and new approaches, Contributed lecture at Cycle Double Cover Conjecture Workshop, IINFORM, Vienna, 1991.
[8] Goddyn, J Combin Theory Ser B 71 pp 310– (1997) · Zbl 0901.05060 · doi:10.1006/jctb.1997.1775
[9] Goldwasser, Congr Numer 113 pp 143– (1996)
[10] Greenwell, Canad Math Bull 16 pp 525– (1973) · Zbl 0275.05107 · doi:10.4153/CMB-1973-086-2
[11] Chapter 5 in Restricted edge-colourings, PhD thesis, Cambridge University, 1988.
[12] On circuit covers, circuit decompositions and Euler tours of graphs, Surveys in Combinatorics, (Editor), London Math Soc Lecture Note Ser 187 Cambridge Univ Press, Cambridge, 1993, pp. 191-210. · Zbl 0791.05081
[13] A survey of the cycle double cover conjecture, Cycles in Graphs, and (Editor), Ann Discrete Math 27 (1985), 1-12.
[14] Robertson, J Combin Theory Ser B 70 pp 2– (1997) · Zbl 0883.05056 · doi:10.1006/jctb.1997.1750
[15] Sums of circuits, Graph Theory and Related Topics and (Editor), Academic Press: New York, 1979, pp. 342-355.
[16] Szekeres, Bull Austral Math Soc 8 pp 367– (1973) · Zbl 0249.05111 · doi:10.1017/S0004972700042660
[17] Thomason, Ann Discrete Math 3 pp 259– (1978) · Zbl 0382.05039 · doi:10.1016/S0167-5060(08)70511-9
[18] Thomason, J Graph Theory 6 pp 219– (1982) · Zbl 0495.05025 · doi:10.1002/jgt.3190060218
[19] Hamiltonian circuits, Colloquio Internazional sulle Teorie Combinatorics, Atti dei Convegni Lincei 17, Accad Naz Lincei, Roma I (1976), 193-199.
[20] Problem 2, Proc 5th British Comb Conf, Utilitas Mathematica, (1976), 696.
[21] Zhang, J Graph Theory 20 pp 91– (1995) · Zbl 0854.05070 · doi:10.1002/jgt.3190200110
[22] Integer Flows and Cycle Covers of Graphs, Marcel Dekker Inc., NY, (1997), (ISBN: 0-8247-9790-6).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.