On some graph transformations that preserve sgn$(\lambda_2-2)$

Bojana Mihailović
University of Belgrade - School of Electrical Engineering, Belgrade, Serbia

Marija Rasajski
University of Belgrade - School of Electrical Engineering, Belgrade, Serbia

PDF

Minisymposium: SPECTRAL GRAPH THEORY

Content: For a simple graph $G$ (a non-oriented graph without loops or multiple edges), with the $\left( 0,1\right) $-adjacency matrix $A$, we define $P_G\left( \lambda \right) =\det \left( \lambda I-A\right) $ to be its \textit{characteristic polynomial}. The roots of the characteristic polynomial are the \textit{eigenvalues} of $G$, and, since they are all real numbers, we can assume the non-increasing order: $\lambda _1 \geq\lambda _2\geq ...\geq \lambda _n$. Graphs having $\lambda _2\leq 2$ are called \textit{reflexive graphs}. A \textit{cactus} is a graph whose any two cycles have at most one common vertex. So far we have determined all classes of reflexive cacti with 4 and 5 cycles and several classes of reflexive cacti with 2 and 3 cycles. Now we describe some graph transformations that preserve sgn$(\lambda_2-2)$, which establish connections between correspondent families of reflexive graphs within the same class, as well as between families that belong to different classes. Using these transformations, we improved our previous results and discovered some new classes of reflexive cacti.

Back to all abstracts