Bounds for the matching number and cyclomatic number of a signed graph in terms of rank

摘要

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 m(G), c(G) and r(G, sigma) be the matching number, the cyclomatic number and the rank of the adjacency matrix of (G, sigma), respectively. In this paper, we investigate the relation among the rank, the matching number and the cyclomatic number of a signed graph, and prove that 2m(G) - 2c(G)) <= r(G, sigma) <= 2m(G)+c(G). Furthermore, signed graphs reaching the lower bound or the upper bound are respectively characterized. (C) 2019 Elsevier Inc. All rights reserved.