Inertia indices of signed graphs with given cyclomatic number and given number of pendant vertices

2025/06/29 by 潔 山浦, Pu, Jie, Fang Duan +1
Chemistry · Computer Science · Mathematics · #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Spectral Theory (math.SP) #Statistics Theory (math.ST) #Synthesis and Properties of Aromatic Compounds

paper · pdf · doi:10.48550/arxiv.2506.23112

openalex publication_date 2025/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let Γ=(G, σ) be a signed graph of order n with underlying graph G and a sign function σ: E(G)→ \+, -\. Denoted by i₊(Γ), θ(Γ) and p(Γ) the positive inertia index, the cyclomatic number and the number of pendant vertices of Γ, respectively. In this article, we prove that i₊(Γ), θ(Γ) and p(Γ) are related by the inequality i₊(Γ)≥ (n-p(Γ))/(2)-θ(Γ). Furthermore, we completely characterize the signed graph Γ for which i₊(Γ)=(n-p(Γ))/(2)-θ(Γ). As a by-product, the inequalities i_-(Γ)≥ (n-p(Γ))/(2)-θ(Γ) and η(Γ)≤ p(Γ)+2θ(Γ) are also obtained, respectively.

Citations

• On signed graphs with at most two eigenvalues unequal to ± 1
• Open problems in the spectral theory of signed graphs
• The inertia of weighted unicyclic graphs
• Spectral criterion for cycle balance in networks
• On the notion of balance of a signed graph.

Related

• Connected signed graphs with given inertia indices and given girth
• Characterizing the positive inertia index of connected signed graphs in terms of girth
• The inertia set of a signed graph
• On the inertia set of a signed graph with loops
• Inertias of Laplacian matrices of weighted signed graphs