The relation between the independence number and rank of a signed graph

arXiv1907.07837MaRDI QIDQ6322296FDOQ6322296

Authors: Shengjie He, Rong-Xia Hao 

Publication date: 17 July 2019

Abstract: A signed graph $(G,sigma)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $(G,sigma)$. Let $c(G)$, $alpha(G)$ and $r(G,sigma)$ be the cyclomatic number, the independence number and the rank of the adjacency matrix of $(G,sigma)$, respectively. In this paper, we study the relation among the independence number, the rank and the cyclomatic number of a signed graph $(G,sigma)$ with order $n$, and prove that $2n-2c(G)leqr(G,sigma)+2alpha(G)leq2n$. Furthermore, the signed graphs that reaching the lower bound are investigated.

This page was built for publication: The relation between the independence number and rank of a signed graph

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