On the inertia of weighted (k - 1)-cyclic graphs - Deng, Shibing (Ars mathematica contemporanea, 2016)
Let ?$G_w$? be a weighted graph. The inertia of ?$G_w$? is the triple ?$In (G_w)=(i_+ (G_w), i_ - (G_w), i_0(G_w))$?, where ?$i _+ (G_w)$?, ?$i_- (G_w)$?, ?$i_0(G_w)$? are, respectively, the number of the positive, negative and zero eigenvalues of the adjacency matrix ?$A(G_w)$? of ?$G_w$? including their multiplicities. A simple ?$n$?-vertex connected graph is called a ?$(k - 1)$?-cyclic graph provided that its number of edges equals ?$n + k - 2$?. Let ?$θ(r_1, r_2, …, r_k)_w$? be an ?$n$?-vertex simple weighted graph obtained from ?$k$? weighted paths ?$(P_{r_1})_w, ((P_{r_2})_w, …,(P_{r_k})_w$? by identifying their initial vertices and terminal vertices, respectively. Set ?$Θ_ k: = \{θ(r_1, r_2, …, r_k)_w \colon r_1 + r_2 + … + r_k = n + 2k - 2\}$?. The inertia of the weighted graph ?$θ(r_1, r_2, …, r_k)_w$? is studied. Also, the weighted ?$(k - 1)$?-cyclic graphs that contain ?$θ(r_1, r_2, …, r_k)_w$? as an induced subgraph are studied. We characterize those graphs among ?$Θ_ k$? that have extreme inertia. The results generalize the corresponding results obtained in X.Z. Tan, B.L. Liu, The nullity of (k - 1)-cyclic graphs, Linear Algebra Appl. 438 (2013) 3144-3153 and G.H. Yu et al., The inertia of weighted unicyclic graphs, Linear Algebra Appl. 448 (2014) 130-152.
Keywords: adjacency matrix; inertia; sosednostna matrika; utežen k-cikličen graf; vztrajnost; weighted k-cyclic graph