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

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} i g m a

is a digraph without loops or multiple arcs whose underlying graph is

G

. Let

S l e f t (G^{s} i g m a i g h t)

be the skew-adjacency matrix of

G^{s} i g m a

and

a l p h a (G)

be the independence number of

G

. The rank of

S (G^{s} i g m a)

is called the skew-rank of

G^{s} i g m a

, denoted by

s r (G^{s} i g m a)

. 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

s r (G^{s} i g m a) + 2 a l p h a (G) g e q s l a n t 2 | V_{G} | - 2 d (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

s r (G^{s} i g m a) + a l p h a (G),, s r (G^{s} i g m a) - a l p h a (G)

,

s r (G^{s} i g m a) / a l p h a (G)

and characterize all corresponding extremal graphs.

Review text

Let \(G^{\sigma}\) be an oriented graph for which its underlying graph is \(G\). The skew-adjacency matrix associated to \(G^{\sigma}\), denoted by \(S(G^{\sigma})\), is defined to be an \(n\times n\) matrix \([s_{x,y}]\) such that \(s_{x,y}=1\) if there is an arc from \(x\) to \(y\), \(s_{x,y}=-1\) if there is an arc from \(y\) to \(x\) and \(s_{x,y}=0\), otherwise. The rank of \(S(G^{\sigma})\) is called the skew-rank of \(G^{\sigma}\), denoted by \(\operatorname{sr}(G^{\sigma})\). The value \(d(G):=|E(G)|-|V(G)|+\omega(G)\) is called the dimension of cycle space of \(G\), where \(\omega(G)\) is the number of the components of \(G\). As usual the independence number of graph \(G\) is denoted by \(\alpha(G)\). The authors prove that \(\operatorname{sr}(G^{\sigma}))+2\alpha(G)\geq 2|V(G)|-2d(G)\) and also established sharp lower bounds for \(\operatorname{sr}(G^{\sigma})+\alpha(G)\), \(\operatorname{sr}(G^{\sigma})-\alpha(G)\), \(\operatorname{sr}(G^{\sigma})/\alpha(G)\) and characterize all corresponding extremal graphs.

Recommendations

Cites work

Cited in

(24)

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)