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: milica.andelic@ua.pt; Domingos Cardoso, University of Aveiro, Aveiro, Portugal, e-mail: dcardoso@ua.pt; Slobodan K. Simic, Mathematical Institute SANU, Belgrade, Serbia, e-mail: sksimic@mi.sanu.ac.rs

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.