On Decomposing Regular Graphs Into Isomorphic Double-Stars

• Autorzy: Saad I. El-Zanati , Marie Ermete , James Hasty , Michael J. Plantholt , Shailesh Tipnis
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph decomposition; double-stars

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 1
• Strony: 73-79

Daty

wydano

2015-02-01

otrzymano

2013-08-26

poprawiono

2014-02-07

zaakceptowano

2014-02-10

online

2015-02-06

Twórcy

autor

Saad I. El-Zanati

• Department of Mathematics Illinois State University Normal, Illinois 61790–4520, U.S.A.

autor

Marie Ermete

• Department of Mathematics Illinois State University Normal, Illinois 61790–4520, U.S.A.

autor

James Hasty

• Department of Mathematics Illinois State University Normal, Illinois 61790–4520, U.S.A.

autor

Michael J. Plantholt

• Department of Mathematics Illinois State University Normal, Illinois 61790–4520, U.S.A.

autor

Shailesh Tipnis

• Department of Mathematics Illinois State University Normal, Illinois 61790–4520, U.S.A.

Bibliografia

• [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]
• [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]
• [4] J.A Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2013) #DS6.
• [5] R. Häggkvist, Decompositions of complete bipartite graphs, London Math. Soc. Lecture Note Ser. C.U.P., Cambridge 141 (1989) 115-147.
• [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]
• [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.
• [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).

Identyfikatory

DOI

10.7151/dmgt.1779