On the nullity of a graph with cut-points

DOI10.1016/J.LAA.2011.06.039MaRDI QIDQ648933zbMATH OpenOpenAlexWikidataFDO

Authors Shi-Cai Gong, Guanghui Xu

Publication date 29 November 2011

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

Full work available at URL https://doi.org/10.1016/j.laa.2011.06.039

zbMATH Keywords

Adjacency matrixCut-pointLine graphNullity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Review text

Let \(G\) be a graph with the vertex set \(\{v_1,\ldots,v_n\}\). The adjacency matrix of \(G\) is an \(n\times n\) matrix \(A(G)\) whose \((i, j)\)-entry is 1 if \(v_i\) is adjacent to \(v_j\) and 0 otherwise. The nullity of \(G\) is the multiplicity of zero as an eigenvalue of \(A(G)\). It is shown that the set of the nullities of all graphs with exactly \(k\) induced cycles is \(\{0,1,\ldots,k+1\}\). Moreover, it is proved that for a graph \(G\) with \(k\) induced cycles if the nullity of the line graph of \(G\) is \(k+1\), then \(G\) has an even number of vertices.

Recommendations

• Publication:4489185
• Graphs with nullity \(2c(G)+p(G)-1\)
• Remarks on the nullity of graphs
• A note on graphs with zero nullity
• On \((k+1)\)-line graphs of \(k\)-trees and their nullities

Cites work

• Describing the nonsingular unicyclic graph
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 1472133 (Why is no real title available?)
• Matrix Analysis
• More about singular line graphs of trees
• On the construction of graphs of nullity one
• On the null-spaces of acyclic and unicyclic singular graphs
• On the nullity of bicyclic graphs
• On the nullity of graphs
• On the nullity of graphs with pendant trees
• On the nullity of graphs with pendent vertices
• On the nullity of line graphs of trees
• On the nullity of unicyclic graphs
• Spektren endlicher Grafen
• Trees with maximum nullity

Cited in

(54)

• On the construction of graphs of nullity one
• An upper bound of the nullity of a graph in terms of order and maximum degree
• The rank of a signed graph in terms of the rank of its underlying graph
• On the relation between the positive inertia index and negative inertia index of weighted graphs
• On the nullspace of arc-transitive graphs over finite fields
• A characterization of long graphs of arbitrary rank
• The nullity of (k-1)-cyclic graphs
• Relationship between the rank and the matching number of a graph
• Graphs \(G\) with nullity \(2c(G) + p(G) - 1\)
• Graphs with nullity \(2c(G)+p(G)-1\)
• Nullity and singularity of a graph in which every block is a cycle
• Graphs with eigenvalue \(-1\) of multiplicity \(2 \theta (G)+ \rho (G) -1\)
• The rank of a signed graph
• Proof of a conjecture on the nullity of a connected graph in terms of order and maximum degree
• On \((k+1)\)-line graphs of \(k\)-trees and their nullities
• Nullspace vertex partition in graphs
• No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\)
• The leaf-free graphs with nullity \(2 c ( G ) - 1\)
• The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices
• A sharp upper bound of the nullity of a connected graph in terms of order and maximum degree
• The rank of a complex unit gain graph in terms of the rank of its underlying graph
• The positive and the negative inertia index of line graphs of trees
• The signature of line graphs and power trees
• 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
• The signature of k-cyclic graphs of -type
• Coalescing Fiedler and core vertices.
• On the rank of weighted graphs
• Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices
• Characterization of graphs whose signature equals the number of odd cycles
• The nullity of \(k\)-cyclic graphs of \(\infty\)-type
• On the nullity of the line graph of unicyclic graph with depth one
• scientific article; zbMATH DE number 1472133 (Why is no real title available?)
• A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\)
• scientific article; zbMATH DE number 844155 (Why is no real title available?)
• Nullity of a graph in terms of path cover number
• Characterization of sub-long graphs of arbitrary rank
• Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph
• An improved lower bound for the nullity of a graph in terms of matching number
• Normalized Laplacian eigenvalues with chromatic number and independence number of graphs
• Relation between the rank of a signed graph and the rank of its underlying graph
• Nullity of a graph with a cut-edge
• The nullity of bicyclic signed graphs
• Relation between the skew-rank of an oriented graph and the rank of its underlying graph
• The extremal graphs with respect to their nullity
• Nullities of cycle-spliced bipartite graphs
• Proof of a conjecture on the nullity of a graph
• Line graphs of trees with the largest eigenvalue multiplicity
• The gap between the rank of a complex unit gain graph and its underlying graph
• Bounds of nullity for complex unit gain graphs
• A note proving the nullity of block graphs is unbounded
• Nullity of graphs -- a survey and some new results
• On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph
• Bounding the multiplicities of eigenvalues of graph matrices in terms of circuit rank

This page was built for publication: On the nullity of a graph with cut-points

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