1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Cubic Graphs Having Only k-Cycles in Each 2-Factor

Published Online: 18 Feb 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 25 Dec 2020
Accepted: 09 Dec 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[1] 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.00610.1016/j.jctb.2007.08.006 Search in Google Scholar

[2] 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.00210.1016/j.jctb.2004.05.002 Search in Google Scholar

[3] 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-510.1090/S0002-9904-1976-14122-5 Search in Google Scholar

[4] N. Biggs, Three remarkable graphs, Canad. J. Math. 25 (1973) 397–411. https://doi.org/10.4153/CJM-1973-040-110.4153/CJM-1973-040-1 Search in Google Scholar

[5] 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-210.1007/s00283-012-9275-2 Search in Google Scholar

[6] J.A. Bondy, Variations on the Hamiltonian theme, Canad. Math. Bull. 15 (1972) 57–62. https://doi.org/10.4153/CMB-1972-012-310.4153/CMB-1972-012-3 Search in Google Scholar

[7] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, New York, 1976).10.1007/978-1-349-03521-2 Search in Google Scholar

[8] M. DeVos, V.V. Mkrtchyan and S.S. Petrosyan, Petersen graph conjecture — Open Problem Garden (2007). http://garden.irmacs.sfu.ca/?q=op/petersen˙graph˙conjecture Search in Google Scholar

[9] 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.207910.1006/jctb.2001.2079 Search in Google Scholar

[10] 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.149510.7151/dmgt.1495 Search in Google Scholar

[11] 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-X10.1016/S0095-8956(02)00031-X Search in Google Scholar

[12] 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.02110.1016/j.dam.2015.04.021 Search in Google Scholar

[13] 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.00310.1016/j.jctb.2004.11.003 Search in Google Scholar

[14] 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.102910.1006/jctb.1995.1029 Search in Google Scholar

[15] 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/231984410.2307/2319844 Search in Google Scholar

[16] 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.2038610.1002/jgt.20386 Search in Google Scholar

[17] 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.abe10.26493/1855-3974.194.abe Search in Google Scholar

[18] 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-310.1016/S0012-365X(01)00189-3 Search in Google Scholar

[19] 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-710.1016/S0012-365X(00)00327-7 Search in Google Scholar

[20] 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.02610.1016/j.disc.2011.05.026 Search in Google Scholar

[21] M.M. Matthews and D.P. Sumner, Hamiltonian results in K1,3-free graphs, J. Graph Theory 8 (1984) 139–146. https://doi.org/10.1002/jgt.319008011610.1002/jgt.3190080116 Search in Google Scholar

[22] J.M.O. Mitchell, The genus of the Coxeter graph, Canad. Math. Bull. 38 (1995) 462–464.10.4153/CMB-1995-067-7 Search in Google Scholar

[23] 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.00210.1016/j.jctb.2019.02.002 Search in Google Scholar

[24] P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh Sect. A 10 (1880) 729. https://doi.org/10.1017/S037016460004464310.1017/S0370164600044643 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo