اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRelation between the skew-rank of an oriented graph and the independence number of its underlying graph
66
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
An oriented graph $G^sigma$ is a digraph without loops or multiple arcs whose underlying graph is $G$. Let $Sleft(G^sigmaright)$ be the skew-adjacency matrix of $G^sigma$ and $alpha(G)$ be the independence number of $G$. The rank of $S(G^sigma)$ is called the skew-rank of $G^sigma$, denoted by $sr(G^sigma)$. 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^sigma)+2alpha(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^sigma)+alpha(G),, sr(G^sigma)-alpha(G)$, $sr(G^sigma)/alpha(G)$ and characterize all corresponding extremal graphs.
قيم البحث
اقرأ أيضاً
Given a simple graph $G=(V_G, E_G)$ with vertex set $V_G$ and edge set $E_G$, the mixed graph $widetilde{G}$ is obtained from $G$ by orienting some of its edges. Let $H(widetilde{G})$ denote the Hermitian adjacency matrix of $widetilde{G}$ and $A(G)$
be the adjacency matrix of $G$. The $H$-rank (resp. rank) of $widetilde{G}$ (resp. $G$), written as $rk(widetilde{G})$ (resp. $r(G)$), is the rank of $H(widetilde{G})$ (resp. $A(G)$). Denote by $d(G)$ the dimension of cycle spaces of $G$, that is $d(G) = |E_G|-|V_G|+omega(G)$, where $omega(G),$ denotes the number of connected components of $G$. In this paper, we concentrate on the relation between the $H$-rank of $widetilde{G}$ and the rank of $G$. We first show that $-2d(G)leqslant rk(widetilde{G})-r(G)leqslant 2d(G)$ for every mixed graph $widetilde{G}$. Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in cite{004,1} may be deduced consequently.
A signed graph $(G, sigma)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $(G, sigma)$. Let $c(G)$, $alpha(G)$ and $r(G, sigma)$ be the cyclomatic number, the independence number and the rank of the adjace
ncy matrix of $(G, sigma)$, respectively. In this paper, we study the relation among the independence number, the rank and the cyclomatic number of a signed graph $(G, sigma)$ with order $n$, and prove that $2n-2c(G) leq r(G, sigma)+2alpha(G) leq 2n$. Furthermore, the signed graphs that reaching the lower bound are investigated.
Let $Phi=(G, varphi)$ be a complex unit gain graph (or $mathbb{T}$-gain graph) and $A(Phi)$ be its adjacency matrix, where $G$ is called the underlying graph of $Phi$. The rank of $Phi$, denoted by $r(Phi)$, is the rank of $A(Phi)$. Denote by $theta(
G)=|E(G)|-|V(G)|+omega(G)$ the dimension of cycle spaces of $G$, where $|E(G)|$, $|V(G)|$ and $omega(G)$ are the number of edges, the number of vertices and the number of connected components of $G$, respectively. In this paper, we investigate bounds for $r(Phi)$ in terms of $r(G)$, that is, $r(G)-2theta(G)leq r(Phi)leq r(G)+2theta(G)$, where $r(G)$ is the rank of $G$. As an application, we also prove that $1-theta(G)leqfrac{r(Phi)}{r(G)}leq1+theta(G)$. All corresponding extremal graphs are characterized.
A complex unit gain graph (or $mathbb{T}$-gain graph) is a triple $Phi=(G, mathbb{T}, varphi)$ ($(G, varphi)$ for short) consisting of a graph $G$ as the underlying graph of $(G, varphi)$, $mathbb{T}= { z in C:|z|=1 } $ is a subgroup of the multiplic
ative group of all nonzero complex numbers $mathbb{C}^{times}$ and a gain function $varphi: overrightarrow{E} rightarrow mathbb{T}$ such that $varphi(e_{ij})=varphi(e_{ji})^{-1}=overline{varphi(e_{ji})}$. In this paper, we investigate the relation among the rank, the independence number and the cyclomatic number of a complex unit gain graph $(G, varphi)$ with order $n$, and prove that $2n-2c(G) leq r(G, varphi)+2alpha(G) leq 2n$. Where $r(G, varphi)$, $alpha(G)$ and $c(G)$ are the rank of the Hermitian adjacency matrix $A(G, varphi)$, the independence number and the cyclomatic number of $G$, respectively. Furthermore, the properties of the complex unit gain graph that reaching the lower bound are characterized.
We establish a lower bound for the energy of a complex unit gain graph in terms of the matching number of its underlying graph, and characterize all the complex unit gain graphs whose energy reaches this bound.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
