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

DOI10.1007/S10878-018-0282-XMaRDI QIDQ724735zbMATHOpenAlexFDO

Authors Jing Huang, Shuchao Li, Hua Wang

Publication date 26 July 2018

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

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

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)

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.

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

Cites work

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

Cited in

(23)

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

Describes a project that uses

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)