Affordable Access

Access to the full text

Skew-rank of an oriented graph and independence number of its underlying graph

Authors
  • Li, Xueliang1, 2
  • Xia, Wen1
  • 1 Nankai University, Center for Combinatorics and LPMC, Tianjin, 300071, China , Tianjin (China)
  • 2 Qinghai Normal University, School of Mathematics and Statistics, Xining, Qinghai, 810008, China , Xining (China)
Type
Published Article
Journal
Journal of Combinatorial Optimization
Publisher
Springer-Verlag
Publication Date
Jan 14, 2019
Volume
38
Issue
1
Pages
268–277
Identifiers
DOI: 10.1007/s10878-019-00382-5
Source
Springer Nature
Keywords
License
Yellow

Abstract

An oriented graph Gσ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G^\sigma $$\end{document} is a digraph which is obtained by orienting every edge of a simple graph G, where G is called the underlying graph of Gσ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G^\sigma $$\end{document}. Let S(Gσ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S(G^\sigma )$$\end{document} denote the skew-adjacency matrix of Gσ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G^\sigma $$\end{document} and α(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (G)$$\end{document} be the independence number of G. The rank of S(Gσ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S(G^\sigma )$$\end{document} is called the skew-rank of Gσ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G^\sigma $$\end{document}, denoted by sr(Gσ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$sr(G^\sigma )$$\end{document}. Wong et al. studied the relation between the skew-rank of an oriented graph and the rank of its underlying graphs. Huang et al. recently studied the relationship between the skew-rank of an oriented graph and the independence number of its underlying graph, by giving some lower bounds for the sum, difference and quotient etc. They left over some questions for further studying the upper bounds of these parameters. In this paper, we extend this study by showing that sr(Gσ)+2α(G)≤2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$sr(G^\sigma )+ 2\alpha (G) \le 2n$$\end{document}, where n is the order of G, and two classes of oriented graphs are given to show that the upper bound 2n can be achieved. Furthermore, we answer some open questions by obtaining sharp upper bounds for sr(Gσ)+α(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$sr(G^\sigma ) + \alpha (G)$$\end{document}, sr(Gσ)-α(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$sr(G^\sigma ) - \alpha (G)$$\end{document} and sr(Gσ)/α(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$sr(G^\sigma ) / \alpha (G)$$\end{document}.

Report this publication

Statistics

Seen <100 times