Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651060 | Discrete Mathematics | 2007 | 11 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Domingos M. Cardoso, Paula Rama,