Geodesic
2-Spanning Cyclability Problems of Some Generalized Petersen Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 713-731.

Voir la notice de l'article provenant de la source Library of Science

A graph G is called r-spanning cyclable if for every r distinct vertices v1, v2, . . ., vr of G, there exists r cycles C1, C2, . . ., Cr in G such that vi is on Ci for every i, and every vertex of G is on exactly one cycle Ci. In this paper, we consider the 2-spanning cyclable problem for the generalized Petersen graph GP (n, k). We solved the problem for k ≤ 4. In addition, we provide an additional observation for general k as well as stating a conjecture.
Keywords: Petersen graph, spanning cyclable 
@article{DMGT_2020_40_3_a1,
     author = {Yang, Meng-Chien and Hsu, Lih-Hsing and Hung, Chun-Nan and Cheng, Eddie},
     title = {2-Spanning {Cyclability} {Problems} of {Some} {Generalized} {Petersen} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {713--731},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a1/}
}
TY  - JOUR
AU  - Yang, Meng-Chien
AU  - Hsu, Lih-Hsing
AU  - Hung, Chun-Nan
AU  - Cheng, Eddie
TI  - 2-Spanning Cyclability Problems of Some Generalized Petersen Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 713
EP  - 731
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a1/
LA  - en
ID  - DMGT_2020_40_3_a1
ER  - 
%0 Journal Article
%A Yang, Meng-Chien
%A Hsu, Lih-Hsing
%A Hung, Chun-Nan
%A Cheng, Eddie
%T 2-Spanning Cyclability Problems of Some Generalized Petersen Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 713-731
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a1/
%G en
%F DMGT_2020_40_3_a1
Yang, Meng-Chien; Hsu, Lih-Hsing; Hung, Chun-Nan; Cheng, Eddie. 2-Spanning Cyclability Problems of Some Generalized Petersen Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 713-731. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a1/

[1] M. Albert, R.E.L. Aldred and D. Holton, On 3*-connected graphs, Australas. J. Combin. 24 (2001) 193–207.

[2] B. Alspach, The classification of Hamiltonian generalized Petersen graphs, J. Combin. Theory Ser. B 34 (1983) 293–312. doi:10.1016/0095-8956(83)90042-4

[3] B. Alspach, D. Bryant and D. Dyer, Paley graphs have Hamilton decompositions, Discrete Math. 312 (2012) 113–118. doi:10.1016/j.disc.2011.06.003

[4] B. Alspach and J. Liu, On the Hamilton connectivity of generalized Petersen graphs, Discrete Math. 309 (2009) 5461–5473. doi:10.1016/j.disc.2008.12.016

[5] M. Behzad, P. Hatami and E.S. Mahmoodian, Minimum vertex covers in the generalized Petersen graphs P(n, 2), Bull. Inst. Combin. Appl. 56 (2009) 98–102.

[6] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory Ser. B 11 (1971) 80–84. doi:10.1016/0095-8956(71)90016-5

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

[8] M.Y. Chan and S.J. Lee, On the existence of Hamiltonian circuits in faulty hyper-cubes, SIAM J. Discrete Math. 4 (1991) 511–527. doi:10.1137/0404045

[9] R.J. Faundree, Survey of results on k-ordered graphs, Discrete Math. 229 (2001) 73–87. doi:10.1016/S0012-365X(00)00202-8

[10] J.R. Faundree, R.J. Gould, A.V. Kostochka, L. Lesniak, I. Schiermeyer and A. Saito, Degree conditions for k-ordered Hamiltonian graphs, J. Graph Theory 42 (2003) 199–210. doi:10.1002/jgt.10084

[11] S. Fujita and T. Araki, Three-round adaptive diagnosis in binary n-cubes, Lecture Notes in Comput. Sci. 3341 (2004) 442–451. doi:10.1007/978-3-540-30551-4_39

[12] S.L. Hakimi and E.F. Schmeichel, On the number of cycles of length k in a maximal planar graph, J. Graph Theory 3 (1979) 69–86. doi:10.1002/jgt.3190030108

[13] C.-N. Hung, D. Lu, R. Jia, C.-K. Lin, L. Lipták, E. Cheng, J.J.M. Tan and L.-H. Hsu, 4 -ordered Hamiltonian problems for the generalized Petersen graph GP (n, 4), Math. Comput. Modelling 57 (2013) 595–601. doi:10.1016/j.mcm.2012.07.022

[14] S.Y. Hsieh, G.H. Chen and C.W. Ho, Fault-free Hamiltonian cycles in faulty arrangement graphs, IEEE Trans. Parallel Distributed Systems 10 (1999) 223–237. doi:10.1109/71.755822

[15] L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks (CRC Press, 2009).

[16] L.-H. Hsu, J.M. Tan, E. Cheng, L. Lipták, C.K. Lin and M. Tsai, Solution to an open problem of 4 -ordered Hamiltonian graphs, Discrete Math. 312 (2012) 2356–2370. doi:10.1016/j.disc.2012.04.003

[17] M. Lewinter and W. Widulski, Hyper-Hamilton laceable and caterpillar-spannable product graphs, Comput. Math. Appl. 34 (1997) 99–104. doi:10.1016/S0898-1221(97)00223-X

[18] R. Li, S. Li and Y. Guo, Degree conditions on distance 2 vertices that imply k-ordered Hamiltonian, Discrete Appl. Math. 158 (2010) 331–339. doi:10.1016/j.dam.2009.05.005

[19] C.-K. Lin, H.-M. Huang and L.-H. Hsu, The super connectivity of the pancake graphs and super laceability of the star graphs, Theoret. Comput. Sci. 339 (2005) 257–271. doi:10.1016/j.tcs.2005.02.007

[20] C.-K. Lin, H.-M. Huang, J.J.M. Tan and L.-H. Hsu, On spanning connected graphs, Discrete Math. 308 (2008) 1330–1333. doi:10.1016/j.disc.2007.03.072

[21] J. Liu, Hamiltonian decompositions of Cayley graphs on Abelian groups, Discrete Math. 131 (1994) 163–171. doi:10.1016/0012-365X(94)90381-6

[22] J. Liu, Hamiltonian decompositions of Cayley graphs on abelian groups of even order, J. Combin. Theory Ser. B 88 (2003) 305–321. doi:10.1016/S0095-8956(03)00033-9

[23] K. Mészáros, On 3 -regular 4 -ordered graphs, Discrete Math. 308 (2008) 2149–2155. doi:10.1016/j.disc.2007.04.061

[24] L. Ng and M. Schultz, k-ordered Hamiltonian graphs, J. Graph Theory 24 (1997) 45–57. doi:10.1002/(SICI)1097-0118(199701)24:1〈45::AID-JGT6〉3.0.CO;2-J

[25] G.N. Robertson, Graphs Minimal under Girth, Valency and Connectivity Constraints, PhD Thesis (University of Waterloo, 1968).

[26] D.R. Silaban, A. Parestu, B.N. Herawati, K.A. Sugeng and Slamin, Vertex-magic total labelings of union of generalized Petersen graphs and union of special circulant graphs, J. Combin. Math. Combin. Comput. 71 (2009) 201–207.

[27] C. Tong, X. Lin, Y. Yang and M. Luo, 2 -rainbow domination of generalized Petersen graphs P(n, 2), Discrete Appl. Math. 157 (2009) 1932–1937. doi:10.1016/j.dam.2009.01.020

[28] M.E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969) 152–164. doi:10.1016/S0021-9800(69)80116-X

[29] G. Xu, 2 -rainbow domination in generalized Petersen graphs P(n, 3), Discrete Appl. Math. 157 (2009) 2570–2573. doi:10.1016/j.dam.2009.03.016