On Double-Star Decomposition of Graphs

Saieed Akbari, et al. "On Double-Star Decomposition of Graphs." Discussiones Mathematicae Graph Theory 37.3 (2017): 835-840. <http://eudml.org/doc/288480>.

@article{SaieedAkbari2017,
abstract = {A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k1 + 1, k2 + 1, 1, . . . , 1) is denoted by Sk1,k2. We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into Sk1,k2 and Sk1−1,k2, for all positive integers k1 and k2 such that k1 + k2 = k.},
author = {Saieed Akbari, Shahab Haghi, Hamidreza Maimani, Abbas Seify},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph decomposition; double-stars; bipartite graph},
language = {eng},
number = {3},
pages = {835-840},
title = {On Double-Star Decomposition of Graphs},
url = {http://eudml.org/doc/288480},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Saieed Akbari
AU - Shahab Haghi
AU - Hamidreza Maimani
AU - Abbas Seify
TI - On Double-Star Decomposition of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 835
EP - 840
AB - A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k1 + 1, k2 + 1, 1, . . . , 1) is denoted by Sk1,k2. We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into Sk1,k2 and Sk1−1,k2, for all positive integers k1 and k2 such that k1 + k2 = k.
LA - eng
KW - graph decomposition; double-stars; bipartite graph
UR - http://eudml.org/doc/288480
ER -