Decomposition of complete graphs into connected bipartite unicyclic graphs with eight edges

John Fahnenstiel, Dalibor Froncek


We prove that each of the 34 non-isomorphic connected unicyclic bipartite graphs with eight edges decomposes the complete graph Kn whenever the necesary conditions are satisfied.


graph decomposition, Rosa type labeling, $\alpha$-labeling, $\sigma^+$-labeling

Full Text:




A. Blinco, Decompositions of complete graphs into theta graphs with fewer than ten edges, Util. Math. 64 (2003), 197--212.

C. Colbourn, G. Ge, A. Ling, Graph designs for the eight-edge five-vertex graphs, Discrete Math.309 (2009), 6440--6445.

Y.G. Cui, Decompositions and packings of $lambda K_v$ into $K_{2s2}$ with a pendent edge, Hebei Normal University, Master Thesis, 2002.

S. El-Zanati, C. Vanden Eynden, On Rosa-type labelings and cyclic graph decompositions, Math. Slovaca 59 (1) (2009), 1--18.

S. El-Zanati, M.J. Kenig, C.V. Eynden, Near $alpha$-labelings of bipartite graphs, Australas. J. Combin. 21 (2000), 275--285.

Q. Kang, Z. Wang, Optimal packings and coverings of $lambda K_{v}$ with graphs $K_{5}-P_{5}$, Bull. Inst. Combin. Appl. 41 (2004), 22--41.

Q. Kang, L. Yuan, S. Liu, Graph Designs for all Graphs with Six Vertices and Eight Edges, Acta Math. Appl. Sin. (Engl. Ser. 21 (3) (2005), 469--484.

Q. Kang, H. Zuo, Y. Zhang, Decompositions of $lambda K_v$ into $k$-circuits with one chord, Australas. J. Combin. 30 (2004), 229--246.

A. Rosa, On certain valuations of the vertices of a graph, In: Theory of Graphs (Intl. Symp. Rome 1966), Gordon and Breach, Dunod, Paris, 1967, 349--355.

Z. Tian, Y. Du, Q. Kang, Decomposing complete graphs into graphs with six vertices and seven edges, Ars Combin. 81 (2006), 257--279.

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.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats