Article ID Journal Published Year Pages File Type
4651060 Discrete Mathematics 2007 11 Pages PDF
Abstract

A set of vertices S⊆V(G)S⊆V(G) is (k,τ)(k,τ)-regular if it induces a k-regular subgraph of G   such that |NG(v)∩S|=τ∀v∉S. Note that a connected graph with more than one edge has a perfect matching if and only if its line graph has a (0,2)(0,2)-regular set. In this paper, some spectral results on the adjacency matrix of graphs with (k,τ)(k,τ)-regular sets are presented. Relations between the combinatorial structure of a p  -regular graph with a (k,τ)(k,τ)-regular set and the eigenspace corresponding to each eigenvalue λ∉{p,k-τ}λ∉{p,k-τ} are deduced. Finally, additional results on the effects of Seidel switching (with respect to a bipartition induced by S) of regular graphs are also introduced.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,