No signed graph with the nullity η(G,σ)=|V(G)|-2m(G)+2c(G)-1

2020/05/29 by Yong Lu, Jingwen Wu, Lu, Yong +1
Computer Science · Mathematics · #05C35 #05C50 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2006.00002

openalex publication_date 2020/05/29 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28

Abstract

Let G^σ=(G,σ) be a signed graph and A(G,σ) be its adjacency matrix. Denote by m(G) the matching number of G. Let η(G,σ) be the nullity of (G,σ). He et al. [Bounds for the matching number and cyclomatic number of a signed graph in terms of rank, Linear Algebra Appl. 572 (2019), 273--291] proved that |V(G)|-2m(G)-c(G)≤η(G,σ)≤ |V(G)|-2m(G)+2c(G), where c(G) is the dimension of cycle space of G. Signed graphs reaching the lower bound or the upper bound are respectively characterized by the same paper. In this paper, we will prove that no signed graphs with nullity |V(G)|-2m(G)+2c(G)-1. We also prove that there are infinite signed graphs with nullity |V(G)|-2m(G)+2c(G)-s,~(0≤ s≤3c(G), s≠1) for a given c(G).

Related

• An upper bound on the nullity of signed graphs
• Further results on the nullity of signed graphs
• Two-connected signed graphs with maximum nullity at most two
• The nullity of the net Laplacian matrix of a signed graph
• No mixed graph with the nullity η(\widetildeG)=|V(G)|-2m(G)+2c(G)-1