Article in volume
Authors:
Title:
Ascending subgraph decompositions of oriented graphs that factor into triangles
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 811-822
Received: 2018-01-31 , Revised: 2020-02-05 , Accepted: 2020-02-05 , Available online: 2020-02-21 , https://doi.org/10.7151/dmgt.2306
Abstract:
In 1987, Alavi, Boals, Chartrand, Erdős, and Oellermann conjectured that
all graphs have an ascending subgraph decomposition (ASD). In a previous
paper, Wagner showed that all oriented complete balanced tripartite graphs have
an ASD. In this paper, we will show that all orientations of an oriented graph
that can be factored into triangles with a large portion of the triangles being
transitive have an ASD. We will also use the result to obtain an ASD for any
orientation of complete multipartite graphs with $3n$ partite classes each
containing $2$ vertices (a $K(2:3n)$) or $4$ vertices (a $K(4:3n))$.
Keywords:
ascending subgraph decomposition, graph factorization, Oberwolfach problem
References:
- Y. Alavi, A.J. Boals, G. Chartrand, P. Erdős and O. Oellermann, The ascending subgraph decomposition problem, Congr. Numer. 58 (1987) 7–14.
- G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 4th Ed. (Chapman & Hall/CRC, Boca Raton, 2005).
- H.-L. Fu and W.-H. Hu, Ascending subgraph decompositions of regular graphs, Discrete Math. 253 (2002) 11–18.
https://doi.org/10.1016/S0012-365X(01)00445-9 - C. Huang, A. Kotzig and A. Rosa, On a variation of the Oberwolfach problem, Discrete Math. 27 (1979) 261–277.
https://doi.org/10.1016/0012-365X(79)90162-6 - J. Liu, The equipartite Oberwolfach problem with uniform tables, J. Combin. Theory Ser. A 101 (2003) 20–34.
https://doi.org/10.1016/S0097-3165(02)00011-0 - J. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).
- B.C. Wagner, Ascending subgraph decompositions of tournaments of order $6n+3$, Graphs Combin. 29 (2013) 1951–1959.
https://doi.org/10.1007/s00373-012-1236-1 - B.C. Wagner, Ascending subgraph decompositions of tournaments of orders $6n+2$ and $6n+1$, Graphs Combin. 32 (2016) 813–822.
https://doi.org/10.1007/s00373-015-1591-9 - B.C. Wagner, Ascending subgraph decompositions in oriented complete balanced tripartite graphs, Graphs Combin. 29 (2013) 1549–1555.
https://doi.org/10.1007/s00373-012-1208-5
Close