Article in volume
Authors:
Title:
Cubic graphs having only k-cycles in each 2-factor
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 281-296
Received: 2020-12-25 , Revised: 2021-12-09 , Accepted: 2021-12-09 , Available online: 2022-02-05 , https://doi.org/10.7151/dmgt.2447
Abstract:
We consider the class of $2$-connected cubic graphs having only $k$-cycles in
each $2$-factor, and obtain the following two results:
(i) every 2-connected cubic graph having only $8$-cycles in each $2$-factor
is isomorphic to a unique Hamiltonian graph of order $8$; and
(ii) a $2$-connected cubic planar graph $G$ has only $k$-cycles in each
$2$-factor if and only if $k=4$ and $G$ is the complete graph of order $4$.
Keywords:
cubic graph, $2$-factor, Hamiltonian cycle, $2$-factor Hamiltonian
References:
- M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan, Pseudo $2$-factor isomorphic regular bipartite graphs, J. Combin. Theory Ser. B 98 (2008) 432–442.
https://doi.org/10.1016/j.jctb.2007.08.006 - R.E.L. Aldred, M. Funk, B. Jackson, D. Labbate and J. Sheehan, Regular bipartite graphs with all $2$-factors isomorphic, J. Combin. Theory Ser. B 92 (2004) 151–161.
https://doi.org/10.1016/j.jctb.2004.05.002 - K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711–712.
https://doi.org/10.1090/S0002-9904-1976-14122-5 - N. Biggs, Three remarkable graphs, Canad. J. Math. 25 (1973) 397–411.
https://doi.org/10.4153/CJM-1973-040-1 - A. Bonato and R.J. Nowakowski, Sketchy tweets: Ten minute conjectures in graph theory, Math. Intelligencer 34 (2012) 8–15.
https://doi.org/10.1007/s00283-012-9275-2 - J.A. Bondy, Variations on the Hamiltonian theme, Canad. Math. Bull. 15 (1972) 57–62.
https://doi.org/10.4153/CMB-1972-012-3 - J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, New York, 1976).
- M. DeVos, V.V. Mkrtchyan and S.S. Petrosyan, \mbox{Petersen} graph conjecture –- Open Problem Garden (2007).
http://garden.irmacs.sfu.ca/?q=op/petersen_graph_conjecture - A.A. Diwan, Disconnected $2$-factors in planar cubic bridgeless graphs, J. Combin. Theory Ser. B 84 (2002) 249–259.
https://doi.org/10.1006/jctb.2001.2079 - J.-L. Fouquet, H. Thuillier and J.-M. Vanherpe, On a family of cubic graphs containing the flower snarks, Discuss. Math. Graph Theory 30 (2010) 289–314.
https://doi.org/10.7151/dmgt.1495 - M. Funk, B. Jackson, D. Labbate and J. Sheehan, $2$-Factor hamiltonian graphs, J. Combin. Theory Ser. B 87 (2003) 138–144.
https://doi.org/10.1016/S0095-8956(02)00031-X - J. Goedgebeur, A counterexample to the pseudo $2$-factor isomorphic graph conjecture, Discrete Appl. Math. 193 (2015) 57–60.
https://doi.org/10.1016/j.dam.2015.04.021 - R. Häggkvist and S. McGuinness, Double covers of cubic graphs with oddness $4$, J. Combin. Theory Ser. B 93 (2005) 251–277.
https://doi.org/10.1016/j.jctb.2004.11.003 - A. Huck and M. Kochol, Five cycle double covers of some cubic graphs, J. Combin. Theory Ser. B 64 (1995) 119–125.
https://doi.org/10.1006/jctb.1995.1029 - R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221–239.
https://doi.org/10.2307/2319844 - B. Jackson and K. Yoshimoto, Spanning even subgraphs of $3$-edge-connected graphs, J. Graph Theory 62 (2009) 37–47.
https://doi.org/10.1002/jgt.20386 - A. Kündgen and R.B. Richter, On $2$-factors with long cycles in cubic graphs, Ars Math. Contemp. 4 (2011) 79–93.
https://doi.org/10.26493/1855-3974.194.abe - D. Labbate, Characterizing minimally $1$-factorable $r$-regular bipartite graphs, Discrete Math. 248 (2002) 109–123.
https://doi.org/10.1016/S0012-365X(01)00189-3 - D. Labbate, On $3$-cut reductions of minimally $1$-factorable cubic bigraphs, Discrete Math. 231 (2001) 303–310.
https://doi.org/10.1016/S0012-365X(00)00327-7 - R. Lukot'ka, E. Máčajová, J. Mazák and M. Škoviera, Circuits of length $5$ in $2$-factors of cubic graphs, Discrete Math. 312 (2012) 2131–2134.
https://doi.org/10.1016/j.disc.2011.05.026 - M.M. Matthews and D.P. Sumner, Hamiltonian results in $K_{1,3}$-free graphs, J. Graph Theory 8 (1984) 139–146.
https://doi.org/10.1002/jgt.3190080116 - J.M.O. Mitchell, The genus of the Coxeter graph, Canad. Math. Bull. 38 (1995) 462–464.
- N. Robertson, P. Seymour and R. Thomas, Excluded minors in cubic graphs, J. Combin. Theory Ser. B 138 (2019) 219–285.
https://doi.org/10.1016/j.jctb.2019.02.002 - P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh Sect. A 10 (1880) 729.
https://doi.org/10.1017/S0370164600044643
Close