DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

Discussiones Mathematicae Graph Theory

Article in press


Authors:

Z.-C. Chen, H.-C. Lee

Title:

Decomposing the complete graph into Hamiltonian paths (cycles) and 3-stars

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-01-12, Revised: 2018-05-14, Accepted: 2018-05-14, https://doi.org/10.7151/dmgt.2153

Abstract:

Let $H$ be a graph. A decomposition of $H$ is a set of edge-disjoint subgraphs of $H$ whose union is $H$. A Hamiltonian path (respectively, cycle) of $H$ is a path (respectively, cycle) {that} contains every vertex of $H$ exactly once. A $k$-star, denoted by $S_k$, is a star with $k$ edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into $\alpha$ copies of Hamiltonian path (cycle) and $\beta$ copies of $S_3$.

Keywords:

decomposition, complete graph, Hamiltonian path, Hamiltonian cycle, star

PDF
Close