Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBounds for the rank of a complex unit gain graph in terms of the independence number
141
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 multiplicative 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.
rate research
Read More
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)$.
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.
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 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 adjacency 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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
