DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

A.D. Austin and B.C. Wagner

Title:

Ascending subgraph decompositions of oriented graphs that factor into triangles

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-01-31, Revised: 2020-02-05, Accepted: 2020-02-05, 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

PDF
Close