Geodesic
On Trees as Star Complements in Regular Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 621-636

Voir la notice de l'article provenant de la source Library of Science

Let G be a connected r-regular graph (r gt; 3) of order n with a tree of order t as a star complement for an eigenvalue µ ∉ −1, 0. It is shown that n ≤ 1/2 (r + 1)t − 2. Equality holds when G is the complement of the Clebsch graph (with µ = 1, r = 5, t = 6, n = 16).
Keywords: eigenvalue, regular graph, star complement, tree 
Rowlinson, Peter. On Trees as Star Complements in Regular Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 621-636. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a16/
@article{DMGT_2020_40_2_a16,
     author = {Rowlinson, Peter},
     title = {On {Trees} as {Star} {Complements} in {Regular} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {621--636},
     year = {2020},
     volume = {40},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a16/}
}
TY  - JOUR
AU  - Rowlinson, Peter
TI  - On Trees as Star Complements in Regular Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 621
EP  - 636
VL  - 40
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a16/
LA  - en
ID  - DMGT_2020_40_2_a16
ER  - 
%0 Journal Article
%A Rowlinson, Peter
%T On Trees as Star Complements in Regular Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 621-636
%V 40
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a16/
%G en
%F DMGT_2020_40_2_a16

[1] F.K. Bell and P. Rowlinson, On the multiplicities of graph eigenvalues, Bull. Lond. Math. Soc. 35 (2003) 401–408. doi:10.1112/S0024609303002030

[2] J. Capaverde and P. Rowlinson, Eigenvalue multiplicity in quartic graphs, Linear Algebra Appl. 535 (2017) 160–170. doi:10.1016/j.laa.2017.08.023

[3] N.E. Clarke, W.D. Garraway, C.A. Hickman and R.J. Nowakowski, Graphs where star sets are matched to their complements, J. Combin. Math. Combin. Comput. 37 (2001) 177–185.

[4] D. Cvetković, M. Doob, I. Gutman and A. Torǧasev, Recent Results in the Theory of Graph Spectra (North-Holland, Amsterdam, 1988).

[5] D. Cvetković, P. Rowlinson and S.K. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2010).

[6] P. Rowlinson, Eigenvalue multiplicity in cubic graphs, Linear Algebra Appl. 444 (2014) 211–218. doi:10.1016/j.laa.2013.11.036

[7] P. Rowlinson, An extension of the star complement technique for regular graphs, Linear Algebra Appl. 557 (2018) 496–507. doi:10.1016/j.laa.2018.08.018

[8] P. Rowlinson, Eigenvalue multiplicity in regular graphs, Discrete Appl. Math. 269 (2019) 11–17. doi:10.1016/j.dam.2018.07.023

[9] P. Rowlinson and B. Tayfeh-Rezaie, Star complements in regular graphs: Old and new results, Linear Algebra Appl. 432 (2010) 2230–2242. doi:10.1016/j.laa.2009.04.022