Some Criteria for a Signed Graph to Have Full Rank

2017/08/23 by Saieed Akbari, Akbari, S., Ali Selk Ghafari +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research

paper · pdf · doi:10.48550/arxiv.1708.07118

openalex publication_date 2017/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A weighted graph G^ω consists of a simple graph G with a weight ω, which is a mapping,ω: E(G)→ℤ\backslash\0\. A signed graph is a graph whose edges are labeled with -1 or 1. In this paper, we characterize graphs which have a sign such that their signed adjacency matrix has full rank, and graphs which have a weight such that their weighted adjacency matrix does not have full rank. We show that for any arbitrary simple graph G, there is a sign σ so that G^σ has full rank if and only if G has a \1,2\-factor. We also show that for a graph G, there is a weight ω so that G^ω does not have full rank if and only if G has at least two \1,2\-factors.

Related

• The rank of a signed graph in terms of girth
• The relation between the independence number and rank of a signed graph
• On Sign-Invertible Graphs
• Signed graphs with maximal index
• Maximizing the index of signed complete graphs with spanning trees on k pendant vertices