Graphs with regularity constraints
 
 
Description:  Graphs with (k,)-regular sets or equitable partitions are examples of graphs with regularity constraints. In this talk some relations between the existence of such structures in a graph and the properties of the spectrum of the (0,1)-adjacency matrix of the graph and of its line graph, are examined. In addition, using adjacency eigenvectors, a necessary and sufficient condition for a subset of vertices of a primitive strongly regular graph to be (k,)-regular is presented. Furthermore, some combinatorial properties of graphs with (k,)-regular sets are considered. Namely, the existence of perfect matchings and perfect induced matchings in a graph is related with the (k,)-regular sets of its line graph. Additionally, Seidel switching is considered and necessary and sufficient conditions for the complement of a regular graph, with respect to an equitable bipartition, to be regular are shown. Finally, some relations between the Laplacian eigenvalues and eigenvectors and the existence of almost equitable partitions (which are generalizations of equitable partitions) are considered.
Area(s):
Date:  2006-01-10
Start Time:   14:30
Speaker:  Paula Rama (Universidade de Aveiro)
Place:  5.5
Research Groups: -Algebra and Combinatorics
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support