Graphs with least eigenvalue -2 attaining a convex quadratic upper bound for the stability number
Author(s) -
Domingos M. Cardoso,
Dragoš Cvetković
Publication year - 2006
Publication title -
bulletin classe des sciences mathematiques et natturalles
Language(s) - English
Resource type - Journals
eISSN - 2406-0909
pISSN - 0561-7332
DOI - 10.2298/bmat0631041c
Subject(s) - combinatorics , upper and lower bounds , mathematics , eigenvalues and eigenvectors , indifference graph , regular polygon , chordal graph , quadratic equation , stability (learning theory) , discrete mathematics , graph , computer science , physics , mathematical analysis , geometry , quantum mechanics , machine learning
summary:Let $G$ be a finite graph with an eigenvalue $\mu $ of multiplicity $m$. A set $X$ of $m$ vertices in $G$ is called a star set for $\mu $ in $G$ if $\mu $ is not an eigenvalue of the star complement $G\setminus X$ which is the subgraph of $G$ induced by vertices not in $X$. A vertex subset of a graph is $(\kappa ,\tau )$-regular if it induces a $\kappa $-regular subgraph and every vertex not in the subset has $\tau $ neighbors in it. We investigate the graphs having a $(\kappa ,\tau )$-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom