# On Decomposing Regular Graphs Into Isomorphic Double-Stars

Saad I. El-Zanati; Marie Ermete; James Hasty; Michael J. Plantholt; Shailesh Tipnis

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 1, page 73-79
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topSaad I. El-Zanati, et al. "On Decomposing Regular Graphs Into Isomorphic Double-Stars." Discussiones Mathematicae Graph Theory 35.1 (2015): 73-79. <http://eudml.org/doc/271229>.

@article{SaadI2015,

abstract = {A double-star is a tree with exactly two vertices of degree greater than 1. If T is a double-star where the two vertices of degree greater than one have degrees k1+1 and k2+1, then T is denoted by Sk1,k2 . In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star Sk,k−1 decomposes every 2k-regular graph that contains a perfect matching.},

author = {Saad I. El-Zanati, Marie Ermete, James Hasty, Michael J. Plantholt, Shailesh Tipnis},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph decomposition; double-stars},

language = {eng},

number = {1},

pages = {73-79},

title = {On Decomposing Regular Graphs Into Isomorphic Double-Stars},

url = {http://eudml.org/doc/271229},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Saad I. El-Zanati

AU - Marie Ermete

AU - James Hasty

AU - Michael J. Plantholt

AU - Shailesh Tipnis

TI - On Decomposing Regular Graphs Into Isomorphic Double-Stars

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 1

SP - 73

EP - 79

AB - A double-star is a tree with exactly two vertices of degree greater than 1. If T is a double-star where the two vertices of degree greater than one have degrees k1+1 and k2+1, then T is denoted by Sk1,k2 . In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star Sk,k−1 decomposes every 2k-regular graph that contains a perfect matching.

LA - eng

KW - graph decomposition; double-stars

UR - http://eudml.org/doc/271229

ER -

## References

top- [1] P. Adams, D. Bryant and M. Buchanan, A survey on the existence of G-designs, J. Combin. Des. 16 (2008) 373-410. doi:10.1002/jcd.20170[Crossref] Zbl1168.05303
- [2] D. Bryant and S. El-Zanati, Graph decompositions, in: Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz (Ed(s)), (2nd Ed., Chapman & Hall/CRC, Boca Raton, 2007) 477-485.
- [3] S.I. El-Zanati, M.J. Plantholt and S. Tipnis, On decomposing even regular multi- graphs into small isomorphic trees, Discrete Math. 325 (2014) 47-51. doi:10.1016/j.disc.2014.02.011[Crossref] Zbl1288.05203
- [4] J.A Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2013) #DS6. Zbl0953.05067
- [5] R. Häggkvist, Decompositions of complete bipartite graphs, London Math. Soc. Lecture Note Ser. C.U.P., Cambridge 141 (1989) 115-147. Zbl0702.05065
- [6] M.S. Jacobson, M. Truszczy´nski and Zs. Tuza, Decompositions of regular bipartite graphs, Discrete Math. 89 (1991) 17-27. doi:10.1016/0012-365X(91)90396-J[Crossref]
- [7] F. Jaeger, C. Payan and M. Kouider, Partition of odd regular graphs into bistars, Discrete Math. 46 (1983) 93-94. doi:10.1016/0012-365X(83)90275-3[Crossref] Zbl0516.05052
- [8] K.F. Jao, A.V. Kostochka and D.B. West, Decomposition of Cartesian products of regular graphs into isomorphic trees, J. Comb. 4 (2013) 469-490. Zbl1290.05108
- [9] A. Kotzig, Problem 1, in: Problem session, Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XXIV (1979) 913-915.
- [10] G. Ringel, Problem 25, in: Theory of Graphs and its Applications, Proc. Symposium Smolenice 1963, Prague (1964), 162.
- [11] H. Snevily, Combinatorics of Finite Sets, Ph.D. Thesis, (University of Illinois 1991).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.