Decomposition of Complete Bipartite Multigraphs Into Paths and Cycles Having k Edges

Shanmugasundaram Jeevadoss; Appu Muthusamy

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 715-731
  • ISSN: 2083-5892

Abstract

top
We give necessary and sufficient conditions for the decomposition of complete bipartite multigraph Km,n(λ) into paths and cycles having k edges. In particular, we show that such decomposition exists in Km,n(λ), when λ ≡ 0 (mod 2), [...] and k(p + q) = 2mn for k ≡ 0 (mod 2) and also when λ ≥ 3, λm ≡ λn ≡ 0(mod 2), k(p + q) =λ_mn, m, n ≥ k, (resp., m, n ≥ 3k/2) for k ≡ 0(mod 4) (respectively, for k ≡ 2(mod 4)). In fact, the necessary conditions given above are also sufficient when λ = 2.

How to cite

top

Shanmugasundaram Jeevadoss, and Appu Muthusamy. "Decomposition of Complete Bipartite Multigraphs Into Paths and Cycles Having k Edges." Discussiones Mathematicae Graph Theory 35.4 (2015): 715-731. <http://eudml.org/doc/276024>.

@article{ShanmugasundaramJeevadoss2015,
abstract = {We give necessary and sufficient conditions for the decomposition of complete bipartite multigraph Km,n(λ) into paths and cycles having k edges. In particular, we show that such decomposition exists in Km,n(λ), when λ ≡ 0 (mod 2), [...] and k(p + q) = 2mn for k ≡ 0 (mod 2) and also when λ ≥ 3, λm ≡ λn ≡ 0(mod 2), k(p + q) =λ\_mn, m, n ≥ k, (resp., m, n ≥ 3k/2) for k ≡ 0(mod 4) (respectively, for k ≡ 2(mod 4)). In fact, the necessary conditions given above are also sufficient when λ = 2.},
author = {Shanmugasundaram Jeevadoss, Appu Muthusamy},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {path; cycle; graph decomposition; multigraph},
language = {eng},
number = {4},
pages = {715-731},
title = {Decomposition of Complete Bipartite Multigraphs Into Paths and Cycles Having k Edges},
url = {http://eudml.org/doc/276024},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Shanmugasundaram Jeevadoss
AU - Appu Muthusamy
TI - Decomposition of Complete Bipartite Multigraphs Into Paths and Cycles Having k Edges
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 715
EP - 731
AB - We give necessary and sufficient conditions for the decomposition of complete bipartite multigraph Km,n(λ) into paths and cycles having k edges. In particular, we show that such decomposition exists in Km,n(λ), when λ ≡ 0 (mod 2), [...] and k(p + q) = 2mn for k ≡ 0 (mod 2) and also when λ ≥ 3, λm ≡ λn ≡ 0(mod 2), k(p + q) =λ_mn, m, n ≥ k, (resp., m, n ≥ 3k/2) for k ≡ 0(mod 4) (respectively, for k ≡ 2(mod 4)). In fact, the necessary conditions given above are also sufficient when λ = 2.
LA - eng
KW - path; cycle; graph decomposition; multigraph
UR - http://eudml.org/doc/276024
ER -

References

top
  1. [1] A.A. Abueida and M. Daven, Multidesigns for graph-pairs of order 4 and 5, Graphs Combin. 19 (2003) 433-447. doi:10.1007/s00373-003-0530-3[Crossref] Zbl1032.05105
  2. [2] A.A. Abueida and M. Daven, Multidecompositions of the complete graph, Ars Combin. 72 (2004) 17-22. Zbl1071.05059
  3. [3] A.A. Abueida, M. Daven and K.J. Roblee, Multidesigns of the λ-fold complete graph- pairs of orders 4 and 5, Australas. J. Combin. 32 (2005) 125-136. Zbl1067.05054
  4. [4] A.A. Abueida and T. O’Neil, Multidecomposition of Km(λ) into small cycles and claws, Bull. Inst. Comb. Appl. 49 (2007) 32-40. 
  5. [5] A.A. Abueida and C. Hampson, Multidecomposition of Kn − F into graph-pairs of order 5 where F is a Hamilton cycle or an (almost) 1-factor , Ars Combin. 97 (2010) 399-416. Zbl1249.05303
  6. [6] A.A. Abueida and M. Daven, Multidecompositions of several graph products, Graphs Combin. 29 (2013) 315-326. doi:10.1007/s00373-011-1127-x[Crossref] Zbl1267.05223
  7. [7] A.A. Abueida and C. Lian, On the decompositions of complete graphs into cycles and stars on the same number of edges, Discuss. Math. Graph Theory 34 (2014) 113-125. doi:10.7151/dmgt.1719[Crossref][WoS] Zbl1292.05211
  8. [8] J.A. Bondy and U.R.S. Murty, Graph Theory with Applications (The Macmillan Press Ltd, New York, 1976). Zbl1226.05083
  9. [9] C.C. Chou, C.M. Fu and W.C. Huang, Decomposition of Km,n into short cycles, Discrete Math. 197/198 (1999) 195-203. doi:10.1016/S0012-365X(99)90063-8[Crossref] 
  10. [10] C.C. Chou and C.M. Fu, Decomposition of Km,n into 4-cycles and 2t-cycles, J. Comb. Optim. 14 (2007) 205-218. doi:10.1007/s10878-007-9060-x[Crossref] Zbl1132.05047
  11. [11] S. Jeevadoss and A. Muthusamy, Sufficient condition for {C4, C2t}-decomposition of K2m,2n-An improved bound, S. Arumugam and B. Smyth (Eds.), Combinatorial Algorithms, IWOCA 2012, LNCS, (Springer-Verlag Berlin Heidelberg) 7643 (2012) 143-147. Zbl1293.05216
  12. [12] S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite graphs into paths and cycles, Discrete Math. 331 (2014) 98-108. doi:10.1016/j.disc.2014.05.009[Crossref] Zbl1297.05190
  13. [13] H.-C. Lee and Y.-P. Chu Multidecompositions of the balanced complete bipartite graphs into paths and stars, ISRN Combinatorics (2013). doi:10.1155/2013/398473[Crossref] 
  14. [14] H.-C. Lee, Multidecompositions of complete bipartite graphs into cycles and stars, Ars Combin. 108 (2013) 355-364. Zbl1289.05375
  15. [15] H.-C. Lee, Decomposition of complete bipartite graphs with a 1-factor removed into cycles and stars, Discrete Math. 313 (2013) 2354-2358. doi:10.1016/j.disc.2013.06.014[WoS] 
  16. [16] D.G. Sarvate and L. Zhang, Decomposition of a λKv into equal number of K3s and P3s, Bull. Inst. Comb. Appl. 67 (2013) 43-48. 
  17. [17] T.-W. Shyu, Decompositions of complete graphs into paths and cycles, Ars Combin. 97 (2010) 257-270. Zbl1249.05313
  18. [18] T.-W. Shyu, Decompositions of complete graphs into paths and stars, Discrete Math. 330 (2010) 2164-2169. doi:10.1016/j.disc.2010.04.009[Crossref] Zbl1219.05146
  19. [19] T.-W. Shyu, Decompositions of complete graphs into paths of length three and tri- angles, Ars Combin. 107 (2012) 209-224. 
  20. [20] T.-W. Shyu, Decomposition of complete graphs into cycles and stars, Graphs Com- bin. 29 (2013) 301-313. doi:10.1007/s00373-011-1105-3[Crossref] Zbl1263.05079
  21. [21] T.-W. Shyu, Decomposition of complete bipartite graphs into paths and stars with same number of edges, Discrete Math. 313 (2013) 865-871. doi:10.1016/j.disc.2012.12.020[Crossref] 
  22. [22] D. Sotteau, Decomposition of Km,n (K* m,n) into cycles (circuits) of length 2k, J. Combin. Theory Ser. B 30 (1981) 75-81. doi:10.1016/0095-8956(81)90093-9 [Crossref] 
  23. [23] M. Truszczyński, Note on the decomposition of λKm,n(λK*m,n) into paths, Discrete Math. 55 (1985) 89-96. doi:10.1016/S0012-365X(85)80023-6 [Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.