The row left rank of a quaternion unit gain graph in terms of maximum degree

Yong Lu, Qi Shen · 2025

Read The row left rank of a quaternion unit gain graph in terms of maximum degree by Yong Lu, Qi Shen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06674.txt.

Introduction

Yong Lu and Qi Shen present a mathematics paper, published in 2025, bounding a rank measure for graphs whose edges carry quaternion labels. Gain graphs attach group values to edges, and here the labels are unit quaternions, the four dimensional numbers used for rotations. The row left rank of such a graph's adjacency matrix is the quantity under study, set against the graph's maximum degree, its busiest vertex.

The authors prove the rank is at least the number of vertices divided by that maximum degree. For connected graphs they sharpen the bound further. Every graph that meets the bounds exactly is then characterized, closing the problem completely. The results extend a line of work tying matrix rank to plain graph structure.

Catalog record

CREATORYong Lu, Qi Shen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-06674

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The row left rank of a quaternion unit gain graph in terms of maximum degree Yong Lu, Qi Shen Abstract This work is supported by the National Natural Science Foundations of China (No. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2024XKT1702). Abstract Let \Phi=(G,U(\mathbb{Q}),\varphi) be a quaternion unit gain graph (or U(\mathbb{Q}) -gain graph) of order n , A(\Phi) be the adjacency matrix of \Phi and r(\Phi) be the row left rank of \Phi . Let \Delta be the maximum degree of \Phi . In this paper, we prove that r(\Phi)\geq\frac{n}{\Delta} . Moreover, if \Phi is connected, we obtain that r(\Phi)\geq\frac{n-2}{\Delta-1} . All the corresponding extremal graphs are characterized. Key Words : Quaternion unit gain graph; Row left rank; Maximum degree. AMS Subject Classification (2010) : 05C35; 05C50. 1 Introduction Let G=(V(G),E(G)) be a simple graph, where V(G)=\{v_{1},v_{2},\ldots,v_{n}\} and E(G) are the vertex set and the edge set of G , respectively. The adjacency matrix A(G) of G is the symmetric n\times n matrix with entries a_{ij}=1 if v_{i} is adjacent to v_{j} and a_{ij}=0 otherwise. The rank (resp., nullity ) of G is the rank (resp., nullity) of A(G) , denoted by r(\Phi) (resp., \eta(G) ). In 1957 , Collatz et al. [ 7 ] first wanted to characterize all graphs of order n with \eta(G)>0 . This question has strong chemical background, because \eta(G)=0 is a necessary condition for a so-called conjugated molecule to be chemically stable, where G is the graph representing the carbon-atom skeleton of this molecule. Up to the present day, the problem has not been solved. In recent years, researchers have focused on the bounds for the rank (or nullity) of a simple graph in terms of some known graph parameters, such as: the matching number (see [ 10 , 17 , 25 , 28 , 31 , 36 ] ); the number of pendant vertices (see [ 2 , 8 , 26 , 34 ] ); the maximum degree (see [ 5 , 6 , 30 , 35 , 37 , 43 ] ); the girth (see [ 4 , 44 ] ) and so on. Let e_{ij} be the oriented edge from v_{i} to v_{j} , \overrightarrow{E}(G) be the set of oriented edges and e_{ij},e_{ji}\in\overrightarrow{E}(G) . Even though e_{ij} stands for an edge and an oriented edge simultaneously, it will always be clear in the content. A gain graph is a triple \Phi=(G,\Omega,\varphi) consisting of an underlying graph G=(V,E) , the gain group \Omega and the gain function \varphi:\overrightarrow{E}(G)\rightarrow\Omega such that \varphi(e_{ij})=\varphi(e_{ji})^{-1}=\overline{\varphi(e_{ji})} . The adjacency matrix A(\Phi) of \Phi is the Hermitian n\times n matrix with entries h_{ij}=\varphi(e_{ij})=\varphi_{v_{i}v_{j}} if e_{ij}\in\overrightarrow{E}(G) and h_{ij}=0 otherwise. The rank of \Phi is the rank of A(\Phi) , denoted by r(\Phi) . If \Omega=\{1\} , then \Phi is a simple graph. If \Omega=\{1,-1\} , then \Phi is a signed graph. If \Omega=\{T\in\mathbb{C}:|T|=1\} , then \Phi is a complex unit gain graph. Recently, researchers have turned to extend the research of the rank (or nullity) of simple graphs to signed graphs (see [ 12 , 20 , 22 , 33 , 38 ] ) and complex unit gain graphs (see [ 11 , 13 , 14 , 18 , 19 , 21 , 23 , 24 , 27 , 39 , 40 ] ). Let \mathbb{R} and \mathbb{C} be the fields of the real numbers and complex numbers, respectively. Let \mathbb{Q} be a four-dimensional vector space over \mathbb{R} with an ordered basis, denoted by 1 , i , j , and k . A real quaternion , simply called quaternion , is a vector q=x_{0}+x_{1}i+x_{2}j+x_{3}k\in\mathbb{Q}, where x_{0},x_{1},x_{2},x_{3} are real numbers and i,j,k satisfy the following conditions: i^{2}=j^{2}=k^{2}=-1; ij=-ji=k,jk=-kj=i,ki=-ik=j. From [ 41 ] , we know that if x,y and z are three different quaternions, then (xy)^{-1}=y^{-1}x^{-1} and (xy)z=x(yz) (Note that xy\neq yx , in general). Let q=x_{0}+x_{1}i+x_{2}j+x_{3}k\in\mathbb{Q} . The conjugate \bar{q} (or q^{\ast} ) of q is \bar{q}=x_{0}-x_{1}i-x_{2}j-x_{3}k . The modulus of q is |q|=\sqrt{q\bar{q}}=\sqrt{x_{0}^{2}+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}} . If q\neq 0 , then the inverse of q is q^{-1}=\frac{\bar{q}}{|q|^{2}} . The real part of q is Re(q)=x_{0} . The imaginary part of q is Im(q)=x_{1}i+x_{2}j+x_{3}k . The row left (right) rank of a quaternion matrix A\in\mathbb{Q}^{m\times n} is the maximum number of rows of A that are left (right) linearly independent. The column left (right) rank of a quaternion matrix A\in\mathbb{Q}^{m\times n} is the maximum number of columns of A that are left (right) linearly independent. Note that quaternions do not satisfy the commutative law of multiplication. By the following lemma and example, we know that the row left rank of a quaternion matrix is not necessarily equal to the row right rank (the same as column left rank and column right rank). Lemma 1.1 . [ 16 ] The row left rank of a quaternion matrix A equals the column right rank of A . The row right rank of a quaternion matrix A equals the column left rank of A . When calculating the row left (right) rank of a quaternion matrix by elementary row operations, we only can multiply a non-zero quaternion on the left (right) side of a row and add it to other rows. Similarly, when calculating the column left (right) rank of a quaternion matrix by elementary column operations, we only can multiply a non-zero quaternion on the left (right) side of a column and add it to other columns. Example 1.2 . [ 42 ] Let \displaystyle A^{{}^{\prime}}=\left(\begin{array}[]{cccc}1&i\\ -i&1\\ \end{array}\right). Then the row left, the row right, the column left and the column right ranks of A^{{}^{\prime}} are equal to 1. Consider now the matrix A obtained by multiply j on the left side of 2-th row of A^{{}^{\prime}} and add it to 1-th row of A^{{}^{\prime}} . That is \displaystyle A=\left(\begin{array}[]{cccc}1-ji&j+i\\ -i&1\\ \end{array}\right). The row left rank \displaystyle r(A)=r\left(\begin{array}[]{cccc}1-ji+(j+i)i&j+i-(j+i)\\ -i&1\\ \end{array}\right)=r\left(\begin{array}[]{cccc}0&0\\ -i&1\\ \end{array}\right)=1. The row right rank \displaystyle r(A)=r\left(\begin{array}[]{cccc}1-ji+i(j+i)&j+i-(j+i)\\ -i&1\\ \end{array}\right)=r\left(\begin{array}[]{cccc}2ij&0\\ -i&1\\ \end{array}\right)=2. The column left rank \displaystyle r(A)=r\left(\begin{array}[]{cccc}1-ji+i(j+i)&j+i\\ -i+i&1\\ \end{array}\right)=r\left(\begin{array}[]{cccc}2ij&j+i\\ 0&1\\ \end{array}\right)=2. The column right rank \displaystyle r(A)=r\left(\begin{array}[]{cccc}1-ji+(j+i)i&j+i\\ -i+i&1\\ \end{array}\right)=r\left(\begin{array}[]{cccc}0&j+i\\ 0&1\\ \end{array}\right)=1. From the example above, we can know that when we multiply a non-zero quaternion on left side of a row of a quaternion matrix A , the row left rank of A maintains unchanged, however, the row right rank of A may be various. If the gain group is U(\mathbb{Q})=\{q\in\mathbb{Q}:|q|=1\} , then \Phi=(G,U(\mathbb{Q}),\varphi) (or G^{\varphi} for short) is a quaternion unit gain graph (or U(\mathbb{Q}) -gain graph). In this paper, the rank r(G^{\varphi}) of a quaternion matrix A(G^{\varphi})\in\mathbb{Q}^{n\times n} is defined to be the row left rank of A(G^{\varphi}) . Belardo et al. [ 1 ] studied quaternion unit gain graphs and their associated spectral theories. Zhou and Lu [ 42 ] obtained the relationship between the row left rank of a quaternion unit gain graph and the rank of its underlying graph. Kyrchei et al. [ 15 ] provided a combinatorial description of the determinant of the Laplacian matrix of a quaternion unit gain graph. We use P^{\varphi}_{n} and C^{\varphi}_{n} to denote a U(\mathbb{Q}) -gain path and a U(\mathbb{Q}) -gain cycle on n vertices. Denoted by K_{|V_{1}|,|V_{2}|}^{\varphi} a U(\mathbb{Q}) -gain complete bipartite graph, where V_{1},V_{2}\subseteq V(G^{\varphi}) , V_{1}\cup V_{2}=V(G^{\varphi}) and V_{1}\cap

Read the complete text