اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRelation between the H-rank of a mixed graph and the rank of its underlying graph
113
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 c
alled 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.
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 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.
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.
A complex unit gain graph (or ${mathbb T}$-gain graph) is a triple $Phi=(G, {mathbb T}, varphi)$ (or $(G, varphi)$ for short) consisting of a simple graph $G$, as the underlying graph of $(G, varphi)$, the set of unit complex numbers $mathbb{T}= { z
in C:|z|=1 }$ and a gain function $varphi: overrightarrow{E} rightarrow mathbb{T}$ with the property that $varphi(e_{i,j})=varphi(e_{j,i})^{-1}$. In this paper, we prove that $2m(G)-2c(G) leq r(G, varphi) leq 2m(G)+c(G)$, where $r(G, varphi)$, $m(G)$ and $c(G)$ are the rank of the Hermitian adjacency matrix $H(G, varphi)$, the matching number and the cyclomatic number of $G$, respectively. Furthermore, the complex unit gain graphs $(G, mathbb{T}, varphi)$ with $r(G, varphi)=2m(G)-2c(G)$ and $r(G, varphi)=2m(G)+c(G)$ are characterized. These results generalize the corresponding known results about undirected graphs, mixed graphs and signed graphs. Moreover, we show that $2m(G-V_{0}) leq r(G, varphi) leq 2m(G)+b(G)$ holds for any subset $V_0$ of $V(G)$ such that $G-V_0$ is acyclic and $b(G)$ is the minimum integer $|S|$ such that $G-S$ is bipartite for $S subset V(G)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
