×

Circuit extension and circuit double cover of graphs. (English) Zbl 1281.05083

Summary: Let \(G\) be a cubic graph and \(C\) be a circuit. An extension of \(C\) is a circuit \(D\) such that \(V(C)\subseteq V(D)\) and \(E(C)\neq E(D)\). The study of circuit extension is motivated by the circuit double cover conjecture. It was proved by H. Fleischner [in: Cycle double cover conjecture workshop. Barbados, February 25 – March 4 (1990)] that a circuit \(C\) is extendable if \(C\) has only one non-trivial Tutte bridge. It was further improved by M. Chan, M. Chudnovsky and P. D. Seymour (2009) that a circuit is extendable if it has only one odd Tutte bridge. Those earlier results are improved in this paper that \(C\) is extendable if all odd Tutte bridges of \(C\) are sequentially lined up along \(C\). It was proved that if every circuit is extendable for every bridgeless cubic graph, then the circuit double cover conjecture is true (J. Kahn et al. (1987)). Although graphs with stable circuits have been discovered by H. Fleischner [Graph Theory 18, No. 5, 449–459 (1994; Zbl 0807.05050)] and M. Kochol [Discrete Math. 233, No. 1–3, 247–256 (2001; Zbl 0986.05063)], variations of this approach remain one of most promising approaches to the circuit double cover conjecture. Following some early investigation of P. D. Seymour and H. Fleischner, we further study the relation between circuit extension and circuit double cover conjecture, and propose a new approach to the conjecture. This new approach is verified for some graphs with stable circuits constructed by Fleischner and Kochol.

MSC:

05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B., Cycle covers of cubic multigraphs, Discrete Math., 111, 11-17 (1993) · Zbl 0789.05075
[2] Alspach, B.; Goddyn, L.; Zhang, C.-Q., Graphs with the circuit cover property, Tran. Amer. Math. Soc., 344, 131-154 (1994) · Zbl 0810.05043
[3] Alspach, B.; Godsil, C., Unsolved problems, (Cycles in Graphs. Cycles in Graphs, Ann. Discrete Math., vol. 27 (1985), North-Holland: North-Holland Amsterdam), 461-467
[5] Esteva, E. G.M.; Jensen, T. R., On semiextensions and circuit double covers, J. Combin. Theory Ser. B, 97, 474-482 (2007) · Zbl 1113.05053
[6] Esteva, E. G.M.; Jensen, T. R., A note on semiextensions of stable circuits, Discrete Math., 309, 4952-4954 (2009) · Zbl 1229.05167
[7] Fleischner, H., Cycle decompositions, 2-coverings, removable cycles and the four-color disease, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic Press: Academic Press New York), 233-246
[8] Fleischner, H., Proof of the strong 2-cover conjecture for planar graphs, J. Combin. Theory Ser. B, 40, 229-230 (1986) · Zbl 0587.05041
[9] Fleischner, H., Eulerian graph, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory (2) (1983), Academic Press: Academic Press London), 17-53
[11] Fleischner, H., Uniqueness of maximal dominating cycles in 3-regular graphs and Hamiltonian cycles in 4-regular graphs, J. Graph Theory, 18, 449-459 (1994) · Zbl 0807.05050
[12] Fleischner, H.; Häggkvist, R., Circuit double covers in special types of cubic graphs, Discrete Math., 309, 5724-5728 (2009) · Zbl 1218.05129
[14] Häggkvist, R.; Markström, K., Cycle double covers and spanning minors I, J. Combin. Theory Ser. B, 96, 183-206 (2006) · Zbl 1085.05039
[15] Häggkvist, R.; Markström, K., Cycle double covers and spanning minors II, Discrete Math., 306, 762-778 (2006) · Zbl 1092.05036
[16] Häggkvist, R.; McGuinness, S., Double covers of cubic graphs with oddness 4, J. Combin. Theory Ser. B, 93, 251-277 (2005) · Zbl 1056.05114
[17] Huck, A., On cycle-double covers of graphs of small oddness, Discrete Math., 229, 125-165 (2001) · Zbl 0982.05081
[18] Huck, A.; Kochol, M., Five cycle double covers of some cubic graphs, J. Combin. Theory Ser. B, 64, 119-125 (1995) · Zbl 0820.05045
[19] Itai, A.; Rodeh, M., Covering a graph by circuits, (Automata, Languages and Programming. Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 62 (1978), Springer-Verlag: Springer-Verlag Berlin), 289-299
[20] Jaeger, F., A survey of the cycle double cover conjecture, (Alspach, B.; Godsil, C., Cycles in Graphs. Cycles in Graphs, Ann. Discrete Math., vol. 27 (1985), North-Holland: North-Holland Amsterdam), 1-12
[22] Kochol, M., Stable dominating circuits in snarks, Discrete Math., 233, 247-256 (2001) · Zbl 0986.05063
[23] Seymour, P. D., Sums of circuits, (Bondy, J. A.; Murty, U. S.R., Graph Theory and Related Topics (1979), Academic Press: Academic Press New York), 342-355
[26] Szekeres, G., Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc., 8, 367-387 (1973) · Zbl 0249.05111
[27] Tarsi, M., Semi-duality and the cycle double cover conjecture, J. Combin. Theory Ser. B, 41, 332-340 (1986) · Zbl 0607.05019
[28] Thomason, A., Hamiltonian Cycles and uniquely edge colorable graphs, Ann. Discrete Math., 3, 259-268 (1978) · Zbl 0382.05039
[30] Ye, D.; Zhang, C.-Q., Cycle double covers and the semi-kotzig frame, Europ. J. Combin., 33, 4, 624-631 (2012) · Zbl 1239.05077
[31] Zhang, C.-Q., Circuit Double Cover of Graphs (2012), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1250.05006
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.