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

DOI10.1016/J.LAA.2021.01.002MaRDI QIDQ2229516zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 17 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.00002

zbMATH Keywords

dimension of cycle spacematching numbernullitysigned graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G^{sigma}=(G,sigma)$ be a signed graph and $A(G,sigma)$ be its adjacency matrix. Denote by $m(G)$ the matching number of $G$. Let $eta(G,sigma)$ be the nullity of $(G,sigma)$. 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 ${\displaystyle }$|V(G)|-2m(G)-c(G)leqeta(G,sigma)leq |V(G)|-2m(G)+2c(G),${\displaystyle }$ 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,(0leqsleq3c(G),seq1)$ for a given $c(G)$.

Recommendations

• No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\)
• Signed graphs with maximum nullity two
• A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\)
• Signed graphs with stable maximum nullity at most two
• Graphs \(G\) with nullity \(2c(G) + p(G) - 1\)
• The nullity of bicyclic signed graphs
• Graphs with nullity \(2c(G)+p(G)-1\)
• Further results on the nullity of signed graphs
• Two-connected signed graphs with maximum nullity at most two
• Graphs \(G\) with nullity \(n(G) - g(G) -1\)

Cites work

• A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\)
• A note on the nullity of unicyclic signed graphs
• Bounds for the matching number and cyclomatic number of a signed graph in terms of rank
• Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank
• Characterization of graphs with given order, given size and given matching number that minimize nullity
• Further results on the nullity of signed graphs
• Graph theory with applications
• No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\)
• On the Laplacian Eigenvalues of Signed Graphs
• On the relation between theH-rank of a mixed graph and the matching number of its underlying graph
• Relation between the skew-rank of an oriented graph and the rank of its underlying graph
• Skew-rank of an oriented graph in terms of matching number
• Spektren endlicher Grafen
• The extremal graphs with respect to their nullity
• The rank of a graph after vertex addition
• The rank of a signed graph in terms of the rank of its underlying graph

Cited in

(17)

• The nullity of a graph with fractional matching number
• On connected signed graphs with rank equal to girth
• The rank of a signed graph
• No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\)
• Bounds for the matching number and cyclomatic number of a signed graph in terms of rank
• The nullity of bicyclic signed graphs
• scientific article; zbMATH DE number 7692350 (Why is no real title available?)
• Inertia indices of a complex unit gain graph in terms of matching number
• The nullities of signed cycle-spliced graphs
• On the difference between the skew-rank of an oriented graph and the rank of its underlying graph
• On connected \(\mathbb{T}\)-gain graphs with rank equal to girth
• Singularity of cycle-spliced signed graphs
• A bound on the rank of weighted graphs in terms of girth
• Signed graphs G^ with nullity n(G^) - g(G^) -1
• On the nullity of cycle-spliced \(\mathbb{T}\)-gain graphs
• Relation between the rank of a signed graph and the fractional matching number of its underlying graph
• The left row rank of quaternion unit gain graphs in terms of girth

This page was built for publication: No signed graph with the nullity \(\eta(G,\sigma)=|V(G)|-2m(G)+2c(G)-1\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229516)