On the rank (nullity) of a connected graph

arXiv1903.02929MaRDI QIDQ6315216FDOQ6315216

Authors: Zhi-Wen Wang, Jiming Guo 

Publication date: 7 March 2019

Abstract: The rank $r(G)$ of a graph $G$ is the rank of its adjacency matrix $A(G)$ and the nullity $eta(G)$ of $G$ is the multiplicity of $0$ as an eigenvalue of $A(G)$. In this paper, we prove that if $G$ is a connected graph of order $n$ with rank $r$, then $G$ contains a nonsingular connected induced subgraph of order $r$. As an application of the result, we completely solve the following problem posed by Zhou, Wong and Sun in [Linear Algebra and its Applications, 555 (2018) 314-320]: Let $G$ be a connected graph of order $n$ with nullity $eta(G)$ and the maximum degree $Delta$. Then ${\displaystyle }$eta(G)lefrac{(Delta-2)n+2}{Delta-1},${\displaystyle }$ the equality holds if and only if $Gcong{C}_n$ ($nequiv0$ $(mod4)$) or $Gcong{K}_{Delta,Delta}$.

This page was built for publication: On the rank (nullity) of a connected graph

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