Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 Spectral results on graphs with regularity constraints
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4309

title: Spectral results on graphs with regularity constraints
authors: Cardoso, D.M.
Rama, P.
keywords: Equitable partitions
Graph spectra
Graph theory
Strongly regular graphs
Constrained optimization
Eigenvalues and eigenfunctions
Matrix algebra
issue date: 2007
publisher: Elsevier
abstract: Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k1, τ1)-regular set S1 and a (k2, τ2)-regular set S2 such that k1 - τ1 = k2 - τ2 = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, over(π, ̄), induced by π, and the adjacency matrix of the quotient graph L (G) / over(π, ̄) is obtained from the adjacency matrix of G/π. © 2006 Elsevier Inc. All rights reserved.
URI: http://hdl.handle.net/10773/4309
ISSN: 0024-3795
publisher version/DOI: http://www.sciencedirect.com/science/article/pii/S0024379506004526
source: Linear Algebra and Its Applications
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
LAA-CardosoRama2007.pdfVersão Electrónica169.36 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2