×

Pack graphs with subgraphs of size three. (English) Zbl 1398.05129

Summary: An \(H\)-packing \(\mathcal{F}\) of a graph \(G\) is a set of edge-disjoint subgraphs of \(G\) in which each subgraph is isomorphic to \(H\). The leave \(L\) or the remainder graph \(L\) of a packing \(\mathcal{F}\) is the subgraph induced by the set of edges of \(G\) that does not occur in any subgraph of the packing \(\mathcal{F}\). If a leave \(L\) contains no edges, or simply \(L = \phi\), then \(G\) is said to be \(H\)-decomposable, denoted by \(H|G\). In this paper, we prove a conjecture made by G. Chartrand et al. [Util. Math. 46, 179–191 (1994; Zbl 0822.05061)]: If \(G\) is a graph of size \(q(G) \equiv 0 \pmod{3}\) and \(\delta(G) \geq 2\), then \(G\) is \(H\)-decomposable for some graph \(H\) of size 3.

MSC:

05C51 Graph designs and isomorphic decomposition
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0822.05061
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] A. A. Abueida and M. Daven, Multidesigns for graph-pairs of order \(4\) and \(5\), Graphs Combin. 19 (2003), no. 4, 433–447. · Zbl 1032.05105 · doi:10.1007/s00373-003-0530-3
[2] A. A. Abueida and T. O’Neil, Multidecomposition of \(λ K_m\) into small cycles and claws, Bull. Inst. Combin. Appl. 49 (2007), 32–40. · Zbl 1112.05084
[3] B. Alspach and H. Gavlas, Cycle decompositions of \(K_n\) and \(K_n-I\), J. Combin. Theory Ser. B 81 (2001), no. 1, 77–99. · Zbl 1023.05112 · doi:10.1006/jctb.2000.1996
[4] B. Alspach and R. Häggkvist, Some observations on the Oberwolfach problem, J. Graph Theory 9 (1985), no. 1, 117–187. · Zbl 0603.05032 · doi:10.1002/jgt.3190090114
[5] B. Alspach P. Schellenberg, D. R. Stinson and D. Wagner, The Oberwolfach problem and factors of uniform odd length cycles, J. Combin. Theory Ser. A 52 (1989), no. 1, 20–43. · Zbl 0684.05035 · doi:10.1016/0097-3165(89)90059-9
[6] B. Alspach and B. N. Varma, Decomposing complete graphs into cycles of length \(2p^e\), Ann. Discrete Math. 9 (1980), 155–162. · Zbl 0454.05041 · doi:10.1016/S0167-5060(08)70053-0
[7] J. Barát and C. Thomassen, Claw-decompositions and Tutte-orientations, J. Graph Theory 52 (2006), no. 2, 135–146. · Zbl 1117.05088 · doi:10.1002/jgt.20149
[8] J.-C. Bermond, C. Huang, A. Rosa and D. Sotteau, Decomposition of complete graphs into isomorphic subgraphs with five vertices, Ars Combin. 10 (1980), 211–254. · Zbl 0454.05053
[9] J.-C. Bermond and J. Schönheim, \(G\)-decompositions of \(K_n\), where \(G\) has four vertices or less, Discrete Math. 19 (1977), no. 2, 113–120. · Zbl 0376.05016
[10] E. J. Billington, N. J. Cavenagh and B. R. Smith, Path and cycle decompositions of complete equipartite graphs: \(3\) and \(5\) parts, Discrete Math. 310 (2010), no. 2, 241–254. · Zbl 1200.05135 · doi:10.1016/j.disc.2008.09.003
[11] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976. · Zbl 1226.05083
[12] L. Bulteau, G. Fertin, A. Labarre, R. Rizzi and I. Rusu, Decomposing cubic graphs into connected subgraphs of size three, in Computing and Combinatorics, 393–404, Lecture Notes in Comput. Sci. 9797, Springer, 2016. · Zbl 1476.68194
[13] G. Chartrand, F. Saba and C. M. Mynhardt, Prime graphs, prime-connected graphs and prime divisors of graphs, Utilitas Math. 46 (1994), 179–191. · Zbl 0822.05061
[14] A. A. Diwan, J. E. Dion, D. J. Mendell, M. J. Plantholt and S. K. Tipnis, The complexity of \(P_{4}\)-decomposition of regular graphs and multigraphs, Discrete Math. Theor. Comput. Sci. 17 (2015), no. 2, 63–75. · Zbl 1327.05270
[15] S. I. EI-Zanati, M. J. Plantholt and S. K. Tipnis, On decomposing even regular multigraphs into small isomorphic trees, Discrete Math. 325 (2014), 47–51. · Zbl 1288.05203 · doi:10.1016/j.disc.2014.02.011
[16] R. Häggkvist and R. Johansson, A note on edge-decompositions of planar graphs, Discrete Math. 283 (2004), no. 1-3, 263–266. · Zbl 1042.05083
[17] K. Heinrich, J. Liu and M. Yu, \(P_{4}\)-decompositions of regular graphs, J. Graph Theory 31 (1999), no. 2, 135–143. · Zbl 0927.05067 · doi:10.1002/(SICI)1097-0118(199906)31:2<135::AID-JGT6>3.0.CO;2-I
[18] D. G. Hoffman C. C. Lindner and C. A. Rodger, On the construction of odd cycle systems, J. Graph Theory 13 (1989), no. 4, 417–426. · Zbl 0704.05031 · doi:10.1002/jgt.3190130405
[19] A. Kotzig, On the decomposition of a complete graph into \(4k\)-gons, Mat.-Fyz. Čas 15 (1965), no. 3, 229–233. · Zbl 0134.43402
[20] C. Lin and T.-W. Shyu, A necessary and sufficient condition for the star decomposition of complete graphs, J. Graph Theory 23 (1996), no. 4, 361–364. · Zbl 0880.05069 · doi:10.1002/(SICI)1097-0118(199612)23:4<361::AID-JGT5>3.0.CO;2-P
[21] C. C. Lindner, K. T. Phelps and C. A. Rodger, The spectrum for \(2\)-perfect \(6\)-cycle systems, J. Combin. Theory Ser. A 57 (1991), no. 1, 76–85. · Zbl 0758.05015 · doi:10.1016/0097-3165(91)90007-4
[22] R. S. Manikandan and P. Paulraja, \(C_p\)-decompositions of some regular graphs, Discrete Math. 306 (2006), no. 4, 429–451. · Zbl 1087.05048 · doi:10.1016/j.disc.2005.08.006
[23] M. Merker, Decomposing series-parallel graphs into paths of length \(3\) and triangles, Electronic Notes in Discrete Mathematics 49 (2015), 367–370. · Zbl 1346.05236
[24] N. Oksimets, A characterization of Eulerian graphs with trianglefree Euler tours, Technical Report 1 (2003), Department of Mathematics, Umea University.
[25] C. A. Parker, Complete Bipartite Graph Path Decompositions, Ph.D. Dissertation, Auburn University, 1998.
[26] C. A. Rodger, Graph decompositions, Matematiche (Catania) 45 (1990), no. 1, 119–139. · Zbl 0735.05066
[27] T.-W. Shyu, Decomposition of complete graphs into paths and stars, Discrete Math. 310 (2010), no. 15-16, 2164–2169 · Zbl 1219.05146 · doi:10.1016/j.disc.2010.04.009
[28] B. R. Smith, Decomposing complete equipartite graphs into cycles of length \(2p\), J. Combin. Des. 16 (2008), no. 3, 244–252. · Zbl 1149.05026 · doi:10.1002/jcd.20173
[29] D. Sotteau, Decomposition of \(K_{m,n}(K_{m,n}^*)\) into cycles (circuits) of length \(2k\), J. Combin. Theory Ser. B 30 (1981), no. 1, 75–81. · Zbl 0463.05048 · doi:10.1016/0095-8956(81)90093-9
[30] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979), no. 3, 273–278. · Zbl 0421.05016 · doi:10.1016/0012-365X(79)90034-7
[31] M. Tarsi, On the decomposition of a graph into stars, Discrete Math. 36 (1981), no. 3, 299–304. · Zbl 0467.05054 · doi:10.1016/S0012-365X(81)80025-8
[32] C. Thomassen, Decompositions of highly connected graphs into paths of length \(3\), J. Graph Theory 58 (2008), no. 4, 286–292. · Zbl 1214.05134 · doi:10.1002/jgt.20311
[33] K. Ushio, S. Tazawa and S. Yamamoto, On claw-decomposition of a complete multipartite graph, Hiroshima Math. J. 8 (1978), no. 1, 207–210. · Zbl 0382.05022
[34] R. M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congressus Numerantium 15 (1976), 647–659. · Zbl 0322.05116
[35] S. Yamomoto, H. Ikeda, S. Shige-eda, K. Ushio and N. Hamada, On claw-decomposition of complete graphs and complete bigraphs, Hiroshima Math. J. 5 (1975), 33–42. · Zbl 0297.05143
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.