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

DOI10.1007/S10878-018-0282-XzbMATH Open1398.05093arXiv1704.06867OpenAlexW2608213386MaRDI QIDQ724735FDOQ724735

Authors: Jing Huang, Shuchao Li, Hua Wang 

Publication date: 26 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: An oriented graph $G^{s}igma$ is a digraph without loops or multiple arcs whose underlying graph is $G$. Let $Sleft(G^{s}igmaight)$ be the skew-adjacency matrix of $G^{s}igma$ and $alpha(G)$ be the independence number of $G$. The rank of $S(G^{s}igma)$ is called the skew-rank of $G^{s}igma$, denoted by $sr(G^{s}igma)$. 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^{s}igma)+2alpha(G)geqslant2|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^{s}igma)+alpha(G),,sr(G^{s}igma)-alpha(G)$, $sr(G^{s}igma)/alpha(G)$ and characterize all corresponding extremal graphs.

Full work available at URL: https://arxiv.org/abs/1704.06867

Recommendations

• Skew-rank of an oriented graph and independence number of its underlying graph
• Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph
• Relation between the skew-rank of an oriented graph and the rank of its underlying graph
• On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph
• Skew-rank of an oriented graph with edge-disjoint cycles

zbMATH Keywords

oriented graphindependence numberskew-rankevenly-oriented cycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Skew spectra of oriented graphs
• Some inequalities on the skew-spectral radii of oriented graphs
• Skew-adjacency matrices of graphs
• Title not available (Why is that?)
• On the independence number of a graph in terms of order and size
• Characteristic polynomials of skew-adjacency matrices of oriented graphs
• Variable neighborhood search for extremal graphs. I: The AutoGraphiX system
• Bicyclic oriented graphs with skew-rank 2 or 4
• Skew spectra of oriented bipartite graphs
• Skew spectrum of the Cartesian product of an oriented graph with an oriented hypercube
• The skew-rank of oriented graphs
• Classes of graphs with minimum skew rank 4
• Variable neighborhood search for extremal graphs. XIV: The AutoGraphiX 2 system
• Minimum rank of skew-symmetric matrices described by a graph
• Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices
• Classes of structurable algebras of skew-rank
• Structurable algebras of skew-rank 1 over the affine plane
• Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures
• More on the minimum skew-rank of graphs
• Bicyclic oriented graphs with skew-rank 6
• On graphs of minimum skew rank 4
• Skew-rank of an oriented graph in terms of matching number
• Relation between the skew-rank of an oriented graph and the rank of its underlying graph

Cited In (23)

• On the relation between theH-rank of a mixed graph and the matching number of its underlying graph
• Relations between the inertia indices of a mixed graph and those of its underlying graph
• The rank of a complex unit gain graph in terms of the matching number
• Relation between the \(H\)-rank of a mixed graph and the rank of its underlying graph
• The relation between the \(H\)-rank of a mixed graph and the independence number of its underlying graph
• Relation between the inertia indices of a complex unit gain graph and those of its underlying graph
• Adjacency rank and independence number of a signed graph
• On the characteristic polynomials and \(H\)-ranks of the weighted mixed graphs
• On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph
• Relation between the skew-rank of an oriented graph and the rank of its underlying graph
• Some mixed graphs with \(H\)-rank 4, 6 or 8
• Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph
• Relation between the Hermitian energy of a mixed graph and the matching number of its underlying graph
• Skew-rank of an oriented graph and independence number of its underlying graph
• The rank of a complex unit gain graph in terms of the rank of its underlying graph
• Relation between the skew energy of an oriented graph and its matching number
• On the relation between the adjacency rank of a complex unit gain graph and the matching number of its underlying graph
• Relationship between the rank and the matching number of a graph
• Relations between the skew spectrum of an oriented graph and the spectrum of an associated signed graph
• Smith normal form and the generalized spectral characterization of oriented graphs
• Relation between the rank of a signed graph and the rank of its underlying graph
• Bounds for the rank of a complex unit gain graph in terms of the independence number
• Bounds on the nullity, the \(H\)-rank and the Hermitian energy of a mixed graph

Uses Software

• AutoGraphiX

This page was built for publication: Relation between the skew-rank of an oriented graph and the independence number of its underlying graph

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