Czechoslovak Mathematical Journal, Vol. 63, No. 1, pp. 73-90, 2013

Relations between $(\kappa,\tau)$-regular sets and star complements

Milica Anđelić, Domingos M. Cardoso, Slobodan K. Simić

Milica Anđelić, University of Aveiro, Aveiro, Portugal, Faculty of Mathematics, University of Belgrade, Serbia, e-mail:; Domingos Cardoso, University of Aveiro, Aveiro, Portugal, e-mail:; Slobodan K. Simic, Mathematical Institute SANU, Belgrade, Serbia, e-mail:

Abstract: 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.

Keywords: eigenvalue, star complement, non-main eigenvalue, Hamiltonian graph

Classification (MSC 2010): 05C50

Full text available as PDF.

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at
Subscribers of Springer need to access the articles on their site, which is

[Previous Article] [Next Article] [Contents of This Number] [Contents of Czechoslovak Mathematical Journal]