Opuscula Math. 39, no. 5 (2019), 623-643
https://doi.org/10.7494/OpMath.2019.39.5.623
Opuscula Mathematica
On 1-rotational decompositions of complete graphs into tripartite graphs
Abstract. Consider a tripartite graph to be any simple graph that admits a proper vertex coloring in at most 3 colors. Let \(G\) be a tripartite graph with \(n\) edges, one of which is a pendent edge. This paper introduces a labeling on such a graph \(G\) used to achieve 1-rotational \(G\)-decompositions of \(K_{2nt}\) for any positive integer \(t\). It is also shown that if \(G\) with a pendent edge is the result of adding an edge to a path on \(n\) vertices, then \(G\) admits such a labeling.
Keywords: graph decomposition, 1-rotational, vertex labeling.
Mathematics Subject Classification: 05C78, 05C51.
- A. Blinco, S.I. El-Zanati, C. Vanden Eynden, On the cyclic decomposition of complete graphs into almost-bipartite graphs, Discrete Math. 284 (2004), 71-81.
- R.C. Bunge, A. Chantasartrassmee, S.I. El-Zanati, C. Vanden Eynden, On cyclic decompositions of complete graphs into tripartite graphs, J. Graph Theory 72 (2013), 90-111.
- R.C. Bunge, S.I. El-Zanati, W. O'Hanlon, C. Vanden Eynden, On \(\gamma\)-labeling the almost bipartite graph \(P_m + e\), Ars Combin. 107 (2012), 65-80.
- S.I. El-Zanati, C. Vanden Eynden, On Rosa-type labelings and cyclic graph decompositions, Mathematica Slovaca 59 (2009), 1-18.
- S.I. El-Zanati, C. Vanden Eynden, N. Punnim, On the cyclic decomposition of complete graphs into bipartite graphs, Australas. J. Combin. 24 (2001), 209-219.
- J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 20 (2017), Dynamic Survey 6, 432 pp., http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6
- A. Rosa, On certain valuations of the vertices of a graph, in: Théorie des graphes, journées internationales d'études, Rome 1966 (Dunod, Paris, 1967), 349-355.
- Ryan C. Bunge
https://orcid.org/0000-0003-0051-379X- Illinois State University, Department of Mathematics, Normal, IL 61790-4520, USA
- Communicated by Dalibor Fronček.
- Received: 2019-01-08.
- Revised: 2019-06-06.
- Accepted: 2019-06-18.
- Published online: 2019-09-05.
