Relation between the skew-rank of an oriented graph and the independence number of its underlying graph

2017/04/23 by Jing Huang, Huang, J., Shuolin Li +3 · 1 citation
Computer Science · Mathematics · #05C50 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1704.06867

openalex publication_date 2017/04/23 · openalex created_date 2019/06/27 · openalex updated_date 2026/08/01

Abstract

An oriented graph G^σ is a digraph without loops or multiple arcs whose underlying graph is G. Let S(G^σ) be the skew-adjacency matrix of G^σ and α(G) be the independence number of G. The rank of S(G^σ) is called the skew-rank of G^σ, denoted by sr(G^σ). Wong et al. [European J. Combin. 54 (2016) 76-86] studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that sr(G^σ)+2α(G)\geqslant 2|V_G|-2d(G), where |V_G| is the order of G and d(G) is the dimension of cycle space of G. We also obtain sharp lower bounds for sr(G^σ)+α(G), sr(G^σ)-α(G), sr(G^σ)/α(G) and characterize all corresponding extremal graphs.

Cited by

• The rank of a complex unit gain graph in terms of the rank of its underlying graph

Related

• Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph
• The skew-rank of oriented graphs
• On oriented graphs with minimal skew energy
• Lower bounds of the skew spectral radii and skew energy of oriented graphs
• The relation between the independence number and rank of a signed graph