×

zbMATH — the first resource for mathematics

The spectrum of optimal excess graphs for trees with up to four edges. (English) Zbl 1439.05135
Summary: C. Huang and A. Rosa [Ars Comb. 5, 23–63 (1978; Zbl 0418.05041)] solved the spectrum problem for decomposition for trees with up to eight edges. Also, the packing and covering problems were settled for trees with up to six edges by Y. Roditty [J. Comb. Theory, Ser. A 35, 213–243 (1983; Zbl 0521.05053); Int. J. Math. Math. Sci. 9, 277–282 (1986; Zbl 0608.05028); Ars Comb. 19, 81–93 (1985; Zbl 0578.05013)]. In this paper, we find the spectrum of excess graphs for trees with up to four edges. Moreover, we use new techniques in our proofs and state lemmas that will be useful for generalizing our result for trees with higher number of edges.
MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bermond, J. C.; Coudert, D.; Yu, M. L., On DRC-Covering of \(K_n\) by cycles, J. Combin. Des., 11, 2, 100-112 (2003) · Zbl 1031.05101
[2] West, D., Introduction to Graph Theory (2001), Prentice Hall
[3] Plucker, J., System der analytischen Geometrie, auf neue Betrachtungsweisen gegrundet, und insbesondere eine ausfuhrliche Theorie der Curven dritter Ordnung enthaltend (1835), Duncker and Humblot: Duncker and Humblot Berlin
[4] Roditty, Y., Packing and covering of the complete graph with a graph \(G\) of four vertices or less, J. Combin. Theory Ser. B, 34, 2, 231-243 (1983) · Zbl 0521.05053
[5] Roditty, Y., Packing and covering of the complete graph. II. The trees of order six, Ars Combin., 19, 81-93 (1985) · Zbl 0578.05013
[6] Roditty, Y., The packing and covering of the complete graph. I. The forests of order five, Int. J. Math. Math. Sci., 9, 2, 277-282 (1986) · Zbl 0608.05028
[7] Roditty, Y., Packing and covering of the complete graph. IV. The trees of order seven, Ars Combin., 35, 33-64 (1993) · Zbl 0796.05074
[8] Kennedy, J. A., Maximum packings of \(K_n\) with hexagons, Astralas. J. Combin., 7, 101-110 (1993) · Zbl 0773.05082
[9] Kennedy, J. A., Maximum packings of \(K_n\) with hexagons: corrigendum, Astralas. J. Combin, 10, 293 (1994) · Zbl 0813.05052
[10] Kennedy, J. A., Minimum coverings of \(K_n\) with hexagons, Astralas. J. Combin., 16, 295-303 (1997) · Zbl 0879.05056
[11] Dyer, D.; Haghshenas, S.; Shalaby, N., Constructing the spectrum for packings of the complete graph with trees that have up to five edges, J. Combin. Math. Combin. Comput., 98, 65-88 (2016) · Zbl 1355.05196
[12] Dyer, D.; Haghshenas, S.; Shalaby, N., Constructing the spectrum of packings and coverings for the complete graph with stars with up to five edges, Graphs Combin., 34, 3, 943-961 (2016) · Zbl 1339.05305
[13] Huang, C.; Rosa, A., Decomposition of complete graphs into trees, Ars Combin., 5, 23-63 (1978) · Zbl 0418.05041
[14] Dyer, D.; Haghshenas, S.; Shalaby, N., Constructing the spectrum of packings and coverings for the complete graph with 4-stars, J. Combin. Math. Combin. Comput., 96, 321-334 (2016) · Zbl 1341.05153
[15] Gyarfas, A.; Lehel, J., (Hajnal, A.; Sos, V. T., Packing Trees of Different Order Into \(K_n\). Combinatorics (1978), Amsterdam: Amsterdam North-Holland), 463-469 · Zbl 0389.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.