Geodesic
Decomposition of the Product of Cycles Based on Degree Partition
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 241-256.

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

The Cartesian product of n cycles is a 2n-regular, 2n-connected and bi- pancyclic graph. Let G be the Cartesian product of n even cycles and let 2n = n1+ n2+ ・ ・ ・ + nk with k ≥ 2 and ni ≥ 2 for each i. We prove that if k = 2, then G can be decomposed into two spanning subgraphs G1 and G2 such that each Gi is ni-regular, ni-connected, and bipancyclic or nearly bipancyclic. For k gt; 2, we establish that if all ni in the partition of 2n are even, then G can be decomposed into k spanning subgraphs G1, G2, . . ., Gk such that each Gi is ni-regular and ni-connected. These results are analogous to the corresponding results for hypercubes.
Keywords: hypercube, Cartesian product, n-connected, regular, bipan- cyclic, spanning subgraph 
@article{DMGT_2019_39_1_a18,
     author = {Borse, Y. M. and Shaikh, S. R.},
     title = {Decomposition of the {Product} of {Cycles} {Based} on {Degree} {Partition}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {241--256},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a18/}
}
TY  - JOUR
AU  - Borse, Y. M.
AU  - Shaikh, S. R.
TI  - Decomposition of the Product of Cycles Based on Degree Partition
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 241
EP  - 256
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a18/
LA  - en
ID  - DMGT_2019_39_1_a18
ER  - 
%0 Journal Article
%A Borse, Y. M.
%A Shaikh, S. R.
%T Decomposition of the Product of Cycles Based on Degree Partition
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 241-256
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a18/
%G en
%F DMGT_2019_39_1_a18
Borse, Y. M.; Shaikh, S. R. Decomposition of the Product of Cycles Based on Degree Partition. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 241-256. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a18/

[1] B. Alspach, J.-C. Bermond and D. Sotteau, Decomposition into cycles I: Hamilton decompositions, in: Cycles and Rays, G. Hahn, G. Sabidussi and R.E. Woodrow (Ed(s)), (Springer, Dordrecht, 1990) 9-18. doi: 10.1007/978-94-009-0517-7 2

[2] B. Alspach and M. Dean, Honeycomb toroidal graphs are Cayley graphs, Inform. Process. Lett. 109 (2009) 705-708. doi: 10.1016/j.ipl.2009.03.009

[3] Y.M. Borse and S.A. Kandekar, Decomposition of hypercubes into regular connected bipancyclic subgraphs, Discrete Math. Algorithms Appl. 7(3) (2015) Article 1550033. doi: 10.1142/S1793830915500330

[4] Y.M. Borse, A.V. Sonawane and S.R. Shaikh, Connected bipancyclic isomorphic m- factorizations of the Cartesian product of graphs, Australas. J. Combin. 66 (2016) 120-129.

[5] Y.M. Borse and B.N. Waphare, On removable and non-separating even cycles in graphs, J. Indian Math. Soc. 80 (2013) 221-234.

[6] X.-B. Chen, Panconnectivity and edge-pancyclicity of multidimensional torus net- works, Discrete Appl. Math. 178 (2014) 33-45. doi: 10.1016/j.dam.2014.06.021

[7] S.I. El-Zanati and C.V. Eynden, Cycle factorizations of cycle products, Discrete Math. 189 (1998) 267-275. doi: 10.1016/S0012-365X(98)00053-3

[8] M.F. Foregger, Hamiltonian decompositions of products of cycles, Discrete Math. 24 (1978) 251-260. doi: 10.1016/0012-365X(78)90096-1

[9] B. Jackson, Removable cycles in 2-connected graphs of minimum degree at least four, J. Lond. Math. Soc.(2) 21 (1980) 385-392. doi: 10.1112/jlms/s2-21.3.385

[10] A. Kotzig, Every Cartesian product of two circuits is decomposable into two Hamil- tonian circuits (Centre de Recherches Mathématiques, Montréal, 1973).

[11] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (Morgan Kaufmann, 1992).

[12] T.-K. Li, C.-H. Tsai, J.J.-M. Tan and L.-H. Hsu, Bipanconnectivity and edge fault- tolerant bipancyclicity of hypercubes, Inform. Process. Lett. 87 (2003) 107-110. doi: 10.1016/S0020-0190(03)00258-8

[13] W. Mader, Kreuzungsfreie a, b-Wege in endlichen Graphen, Abh. Math. Semin. Univ. Hambg. 42 (1974) 187-204. doi: 10.1007/BF02993546

[14] W. Mader, Connectivity and edge-connectivity in finite graphs, in: Surveys in Com- binatorics, B. Bollobás (Ed(s)), (Cambridge University Press, 1979) 66-95. doi: 10.1017/CBO9780511662133.005

[15] A.V. Sonawane and Y.M. Borse, Decomposing hypercubes into regular connected subgraphs, Discrete Math. Algorithms Appl. 8(4) (2016) Article 1650065. doi: 10.1142/S1793830916500658

[16] M. Xu, J.-M. Xu, X.-M. Hou, Fault diameter of Cartesian product graphs, Inform. Process. Lett. 93 (2005) 245-248. doi: 10.1016/j.ipl.2004.11.005.