On the inertia of weighted (k - 1)-cyclic graphs

Shibing Deng, Shuchao Li, Feifei Song


Let Gw be a weighted graph. The inertia of Gw is the triple In(Gw) = (i + (Gw), i − (Gw), i0(Gw)), where i + (Gw), i − (Gw), i0(Gw) are, respectively, the number of the positive, negative and zero eigenvalues of the adjacency matrix A(Gw) of Gw 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 θ(r1, r2, …, rk)w be an n-vertex simple weighted graph obtained from k weighted paths (Pr1)w, (Pr2)w, …, (Prk)w by identifying their initial vertices and terminal vertices, respectively. Set Θ k:  = {θ(r1, r2, …, rk)w: r1 + r2 + ⋯ + rk = n + 2k − 2}.  The inertia of the weighted graph θ(r1, r2, …, rk)w is studied. Also, the weighted (k − 1)-cyclic graphs that contain θ(r1, r2, …, rk)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].


Weighted k-cyclic graph, adjacency matrix, inertia

Full Text:


DOI: https://doi.org/10.26493/1855-3974.673.4a1

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications