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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.