Geodesic
Cubic graphs having only k-cycles in each 2-factor
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 281-296 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_2024_44_1_a13,
     author = {Matsumoto, Naoki and Noguchi, Kenta and Yashima, Takamasa},
     title = {Cubic graphs having only k-cycles in each 2-factor},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {281--296},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a13/}
}
TY  - JOUR
AU  - Matsumoto, Naoki
AU  - Noguchi, Kenta
AU  - Yashima, Takamasa
TI  - Cubic graphs having only k-cycles in each 2-factor
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 281
EP  - 296
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a13/
LA  - en
ID  - DMGT_2024_44_1_a13
ER  - 
%0 Journal Article
%A Matsumoto, Naoki
%A Noguchi, Kenta
%A Yashima, Takamasa
%T Cubic graphs having only k-cycles in each 2-factor
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 281-296
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a13/
%G en
%F DMGT_2024_44_1_a13
Matsumoto, Naoki; Noguchi, Kenta; Yashima, Takamasa. Cubic graphs having only k-cycles in each 2-factor. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 281-296. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a13/

[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.006

[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.002

[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-5

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

[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-2

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

[7] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, New York, 1976).

[8] 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

[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.2079

[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.1495

[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-X

[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.021

[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.003

[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.1029

[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/2319844

[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.20386

[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.abe

[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-3

[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-7

[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.026

[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.3190080116

[22] J.M.O. Mitchell, The genus of the Coxeter graph, Canad. Math. Bull. 38 (1995) 462–464.

[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.002

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