Decomposition of complete graphs into connected unicyclic graphs with eight edges and pentagon
Abstract
A G-decomposition of the complete graph Kn is a family of pairwise edge disjoint subgraphs of Kn, all isomorphic to G, such that every edge of Kn belongs to exactly one copy of G. Using standard decomposition techniques based on ρ-labelings, introduced by Rosa in 1967, and their modifications we show that each of the ten non-isomorphic connected unicyclic graphs with eight edges containing the pentagon decomposes the complete graph Kn whenever the necessary conditions are satisfied.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2019.3.1.3
References
A. Blinco, S. El-Zanati, C. Vanden Eynden, On the cyclic decomposition of complete graphs into almost-bipartite graphs, Discrete Math. 284(1– 3) (2004), 71–81.
R. Bunge, A. Chantasartrassmee, S. El-Zanati, C. Vanden Eynden, On cyclic decompositions of complete graphs into tripartite graphs J. Graph Theory 72 (2013), 90–111.
C. Colbourn, G. Ge, A. Ling, Graph designs for the eight-edge five-vertex graphs, Discrete Math. 309 (2009), 6440–6445.
S. El-Zanati, On Rosa-type labelings and cyclic graph decompositions, Math. Slovaca 59(1) (2009), 1–18.
J. Fahnestiel, D. Froncek, Decomposition of complete graphs into con- nected bipartite unicyclic graphs with eight edges, submitted.
Q. Kang, L. Yuan, S. Liu, Graph Designs for all Graphs with Six Vertices and Eight Edges, Acta Math. Sin. (Engl. Ser.), 21(3) (2005), 469–484.
A. Kotzig, On well spread sets of integers. Reports of the CRM CRM- 161 (1972).
A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Intl. Symp. Rome 1966), Gordon and Breach, Dunod, Paris, 1967, 349–355.
J. Yin, B. Gong, Existence of G-designs with |V (G)| = 6, In: W.D. Wallis et al (eds). Combinatorial designs and applications, Marcel Dekker, New York, 1990, 201–218.
Y. Zhang, Q. Kang, Decompositions of Kv into four kinds of graphs with eight vertices and eight edges, J. Combin. Math. Combin. Comput. 94 (2015), 157–165.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.