The Index Weighted Hermitian Adjacency Matrices for Mixed Graphs

Wang, Zheng; She, Tao; Wang, Chunxiang

doi:10.61091/um119-07

Abstract

1. Introduction and Preliminaries
2. Switching Equivalence for MG
3. Hfk-cospectrality with Underlying Graph
4. Proof of Theorem 1
Acknowledgments
Conflict of Interest

References

Utilitas Mathematica

Volume 119
Pages: 63-71

Research article

The Index Weighted Hermitian Adjacency Matrices for Mixed Graphs

^¹, ^¹, ^¹

¹School of Mathematics and Statistics, Central China Normal University, Wuhan, P.R. China

Received: 22/02/2024
Accepted: 21/03/2024
Published: 31/03/2024

Copyright Link
License

Abstract

Based on the Hermitian adjacency matrices of second kind introduced by Mohar [1] and weighted adjacency matrices introduced in [2], we define a kind of index weighted Hermitian adjacency matrices of mixed graphs. In this paper we characterize the structure of mixed graphs which are cospectral to their underlying graphs, then we determine a upper bound on the spectral radius of mixed graphs with maximum degree $Δ$ , and characterize the corresponding extremal graphs.

Keywords: Mixed graph, Spectral radius, Eigenvalue, Adjacency matrix, Cospectrality

1. Introduction and Preliminaries

In this paper, we consider only simple and finite graphs. Let $G = (V (G), E (G))$ be a graph with vertex set $V (G)$ and edge set $E (G)$ . We say that two vertices $u$ and $v$ are adjacent if they are joined by an edge. A mixed graph $M_{G}$ is obtained from a simple graph $G$ by orienting each edge of some subset $E_{0} \in E (G)$ and we call $G$ the underlying graph of $M_{G}$ . We write an undirected edge as ${u, v}$ and an arc form $u$ to $v$ as $(u, v)$ . For a vertex set $V^{'}$ of $V (M_{G})$ , let $M_{G} [V^{'}]$ be a mixed subgraph of $M_{G}$ induced on $V^{'}$ . We say a mixed graph is connected if its underlying graph is connected. The degree of a vertex in a mixed graph $M_{G}$ is defined to be the degree of this vertex in the underlying graph. We divide the vertices adjacent to $v$ in $M_{G}$ into three sets: $N_{M_{G}}^{0} (v) = {u \in V (M_{G}) : {u, v} \in E (M_{G})}$ ; $N_{M_{G}}^{+} (v) = {u \in V (M_{G}) : (v, u) \in E (M_{G})}$ and $N_{M_{G}}^{-} (v) = {u \in V (M_{G}) : (u, v) \in E (M_{G})}$ .

Recently, Yu, Geng and Zhou [3] defined a kind of new Hermitian adjacency matrix of a mixed graph, written by $H_{k} (M_{G}) = (h_{u v})$ , which is as follows: $\begin{aligned} h_{u v} = {\begin{cases} e^{\frac{2 π i}{k}}, & if (u, v) is an arcfrom u to v; \\ e^{- \frac{2 π i}{k}}, & if (v, u) is\ an arcfrom v to u; \\ 1, & if {u, v} is an undirectededge; \\ 0, & otherwise, \end{cases} \end{aligned}$ where $i$ is the imaginary unit and $k$ is a positive integer. $H_{k} (M_{G})$ unifies some well known matrices. In fact, when $k = 1$ , $H_{1} (M_{G}) = A (G)$ is the adjacency matrix of $G$ ; when when $k = 4$ , $H_{4} (M_{G}) = H (M_{G})$ is the Hermitian adjacency matrix of $M_{G}$ , proposed independently by Guo and Mohar [4], Liu and Li [5]; When $k = 6$ , $H_{6} (M_{G})$ is is the Hermitian adjacency matrix of second kind for $M_{G}$ , proposed by Mohar [1] recently.

The author in [2] gave the following definition of a new weighted adjacency matrix of a graph weighted by its degrees.

Definition 1. Let $G = (V (G), E (G))$ be a graph. Denote by $d_{u}$ the degree of a vertex $u$ in $G$ . Let $f (x, y)$ be a function symmetric in $x$ and $y$ . The weighted adjacency matrix $A_{f} (G) = (a_{u v})$ of $G$ is defined as follows: $\begin{aligned} a_{u v} = {\begin{cases} f (d_{u}, d_{v}), & if u v \in E (G); \\ 0, & otherwise. \end{cases} \end{aligned}$

$A_{f} (G)$ introduced in [2] unifies many matrices weighted by topological index. When $f (x, y) = 1$ , $A_{f} (G)$ is the adjacency matrix of $G$ ; when $f (x, y) = \sqrt{\frac{x + y - 2}{x y}}$ , $A_{f} (G)$ is the $A B C$ matrix and was introduced by Estrada [6] and was studied in [7]; When $f (x, y) = \frac{2}{x + y}$ , $A_{f} (G)$ is the $h a r m o n i c$ matrix and was introduced in [8]; When $f (x, y) = \frac{x^{2} + y^{2}}{2 x y}$ , $A_{f} (G)$ is the $A G$ matrix and was studied in [9], [10] and [11].

In this paper, inspired by [3], we generalize weighted adjacency matrix to mixed graphs and define a index weighted Hermitian matrix $H_{f}^{k} (M_{G}) = (h_{u v})$ for a mixed graph $M_{G}$ , where $\begin{aligned} h_{u v} = {\begin{cases} f (d_{u}, d_{v}) \cdot ω, & if (u, v) is an arc from u to v; \\ f (d_{u}, d_{v}) \cdot \bar{ω}, & if (v, u) is an arcfrom v to u; \\ f (d_{u}, d_{v}), & if {u, v} is anundirected\ edge; \\ 0, & otherwise, \end{cases} \end{aligned}$ $ω = c o s (\frac{2 π}{k}) + i s i n (\frac{2 π}{k})$ for a positive integer $k$ and $f (x, y) > 0$ is a symmetric and real function. It can be seen that when $f (x, y) = 1$ , $H_{f}^{k} (M_{G})$ is the matrix $H^{k} (M_{G})$ , which is defined in [3]; when $k = 1$ , $H_{f}^{k} (M_{G})$ is the matrix $A_{f} (M_{G})$ , introduced in [2]. It’s easy to check that if all edges of $M_{G}$ are undirected edges, then $H_{f}^{k} (M_{G}) = A_{f} (M_{G})$ . Note that When $k$ is a positive integer and $f (x, y) > 0$ is a symmetric and real function, $H_{f}^{k} (M_{G})$ is Hermitian and the eigenvalues of $H_{f}^{k} (M_{G})$ are real. With fixed $f$ , $k$ and a mixed graph $M_{G}$ , let $λ_{1} (M_{G}) \geq λ_{2} (M_{G}) \geq \dots λ_{n} (M_{G})$ be n eigenvalues of $H_{f}^{k} (M_{G})$ with $| V (M_{G}) | = n$ . The collection ${λ_{1} (M_{G}), λ_{2} (M_{G}), \dots, λ_{n} (M_{G})}$ is called the $H_{f}^{k}$ -spectrum of $M_{G}$ , we say $M_{G}$ is $H_{f}^{k}$ -cospectral to its underlying graph if $H_{f}^{k} (M_{G})$ and $H_{f}^{k} (G)$ have the same $H_{f}^{k}$ -spectrum. We call the spectral radius of $H_{f}^{k} (M_{G})$ the $H_{f}^{k}$ -spectrum radius of $M_{G}$ , denoted by $ρ_{f}^{k} (M_{G})$ .

In the following paper, we assume that $k$ is a positive integer and $f (x, y) > 0$ is a symmetric and real function. We define several particular partitions of $V (M_{G})$ which will be used in our proof.

Definition 2. Let $M_{G}$ be a mixed graph,

(i) For a partition $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ (possible empty) of $V (M_{G})$ , we call it a $A$ – $p a r t i t i o n$ of $V (M_{G})$ if every undirected edge ${u, v}$ with $u \in V_{i}$ and $v \in V_{j}$ such that $i - j \equiv 0$ (mod $k$ ) and every arc $(u, v)$ with $u \in V_{i}$ and $v \in V_{j}$ such that $i - j \equiv 1$ (mod $k$ ).

(ii) When $k$ is even. For a partition $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ (possible empty) of $V (M_{G})$ , we call it a $B$ – $p a r t i t i o n$ of $V (M_{G})$ if every undirected edge ${u, v}$ with $u \in V_{i}$ and $v \in V_{j}$ such that $i - j \equiv \frac{k}{2}$ (mod $k$ ) and every arc $(u, v)$ with $u \in V_{i}$ and $v \in V_{j}$ such that $i - j \equiv \frac{k}{2} + 1$ (mod $k$ ).

(iii) When $k$ is odd. For a partition $V_{1} \cup \dots \cup V_{k} \cup U_{1} \cup \dots \cup U_{k}$ (possible empty) of $V (M_{G})$ , we call it a $C$ – $p a r t i t i o n$ of $V (M_{G})$ if every undirected edge ${u, v}$ is between $U_{i}$ and $V_{i}$ for some $i \in {1, 2, \dots, k}$ and every arc $(u, v)$ is between $U_{i}$ , $V_{j}$ or $V_{i}$ , $U_{j}$ , where $i - j \equiv 1$ (mod $k$ ).

When $k = 6$ , three partitions can be seen in Figures 1 and 2. By the Definition 2, $V (M_{G})$ has a $B$ – $p a r t i t i o n$ only if $k$ is an even positive integer and it’s easy to check that a $C$ – $p a r t i t i o n$ of $V (M_{G})$ is a $A$ – $p a r t i t i o n$ . The main result of paper is as follows:

Figure 1: $A$ – $p a r t i t i o n$ (left) and $B$ – $p a r t i t i o n$ (right) when $k$ is Equal to $6$

Figure 2: $C$ – $p a r t i t i o n$ when $k$ is Equal to $6$

Theorem 1. Assume that $k$ is a positive integer and $f (x, y) > 0$ is a symmetric real function, not decreasing in variable $x$ . Then for any connected mixed graph $M_{G}$ with maximum degree $Δ$ , we have $ρ_{f}^{k} (M_{G}) \leq f (Δ, Δ) Δ$ , where equality holds if and only if $M_{G}$ such that $G$ is $Δ$ -regular and $V (M_{G})$ admits a $A$ – $p a r t i t i o n$ or a $B$ – $p a r t i t i o n$ .

The structure of the paper is as follows. In Section $2$ we show a disturbance on $E (M_{G})$ which remains the $H_{f}^{k}$ -spectrum of $M_{G}$ . In Section $3$ we characterize a family of mixed graphs which are $H_{f}^{k}$ -cospectral to their underlying graph and in Section $4$ we prove Theorem 1

2. Switching Equivalence for $M_{G}$

In this section, we focus on some sufficient conditions of $H_{f}^{k}$ -cospectrality of mixed graphs.

Supposed that $V (M_{G})$ can be partitioned into $k$ (possible empty) sets $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ . We say the partition is admissible if it such that:

(i)

i - j \equiv 0

1

2

(mod

k

) for every arc

(u, v)

M_{G}

, where

u \in V_{i}

and

v \in V_{j}

;

(ii)

i - j \equiv 0

1

(mod

k

) for every undirected edge

{u, v}

M_{G}

, where

u \in V_{i}

and

v \in V_{j}

We say a mixed graph $M_{G}$ is admissible if it has an admissible partition.

For a mixed graph $M_{G}$ , a $t h r e e$ – $w a y$ $s w i t c h i n g$ for $M_{G}$ with respect to its admissible partition $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ is a operation of changing $M_{G}$ into $M_{G}^{'}$ by making the changes in what follows (see Figure 3):

(i) replacing each undirected edge

{u, v}

with an arc

(u, v)

, where

u \in V_{i}

v \in V_{j}

and

j - i \equiv 1

(mod

k

);

(ii) replacing each arc

(u, v)

with an undirected edge

{u, v}

, where

u \in V_{i}

v \in V_{j}

and

i - j \equiv 1

(mod

k

);

(iii) replacing each arc

(u, v)

with an arc

(v, u)

, where

u \in V_{i}

v \in V_{j}

and

i - j \equiv 2

(mod

k

Figure 3: Three Way Switching for an Admissible Partition

Theorem 2. If a mixed graph $M_{G}^{^{'}}$ is obtained from an admissible mixed graph $M_{G}$ by a $t h r e e$ – $w a y$ $s w i t c h i n g$ , then $M_{G}^{^{'}}$ is $H_{f}^{k}$ -cospectral to $M_{G}$ .

Proof. Let $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ be an admissible partition of $V (M_{G})$ , Let $n_{i} = | V_{i} |$ for $i = {1, 2, \dots, k}$ and $D = d i a g {ω I_{n_{1}}, ω^{2} I_{n_{2}}, \dots,, ω^{k} I_{n_{k}}}$ , let $H_{f}^{k} (M_{G}) = (h_{i j})_{n \times n}$ and $H_{f}^{k} (M_{G}^{'}) = (h_{i j}^{'})_{n \times n}$ . In order to prove the Theorem, it suffices to prove that $H_{f}^{k} (M_{G}^{'}) = D^{- 1} H_{f}^{k} (M_{G}) D$ .

It’s easy to check that for every vertices pair $u, v$ with $u \in V_{i}$ and $v \in V_{j}$ , where $i \geq j$ , $(D^{- 1} H_{f}^{k} (M_{G}) D)_{u, v} = ω^{k + j - i} h_{u v}$ . If $u$ is not adjacent to $v$ in $M_{G}$ , then $ω^{k + j - i} h_{u v} = 0 = h_{u v}^{'}$ since $M_{G}$ and $M_{G}^{'}$ have the same underlying graph.

When u,v are adjacent, we consider following cases.

Case 1. $i - j \equiv 0$ (mod $k$ ), in this case we have $h_{u v}^{'} = h_{u v}$ since the switching doesn’t change the edges in $[M_{G} (V_{i})]$ .

Case 2. $i - j \equiv 1$ (mod $k$ ), note that in this case, the edge between $u$ , $v$ in $M_{G}$ is a undirected edge ${u, v}$ or a arc $(u, v)$ from $u$ to $v$ . If ${u, v}$ is a undirected edge, then by by the switching, it follows that $(v, u)$ is a arc from $v$ to $u$ in $M_{G}^{'}$ and $h_{u, v}^{'} = f (d_{u}, d_{v}) ω^{- 1} = ω^{k + j - i} h_{u v}$ . If $(u, v)$ is a arc from $u$ to $v$ , then by the switching it follows that ${u, v}$ is a undirected edge in $M_{G}^{'}$ and $h_{u, v}^{'} = ω^{- 1} f (d_{u}, d_{v}) ω = ω^{k + j - i} h_{u v}$ .

Case 3. $i - j \equiv 2$ (mod $k$ ), note that in this case, the edge between $u$ , $v$ in $M_{G}$ must be a arc $(u, v)$ from $u$ to $v$ . Then by the switching it follows that $(v, u)$ is a arc from $v$ to $u$ in $M_{G}^{'}$ and $h_{u, v}^{'} = f (d_{u}, d_{v}) ω^{- 1} = ω^{- 2} f (d_{u}, d_{v}) ω^{1} = ω^{k + j - i} h_{u v}$ .

Together with Case 1, 2 and 3, we complete the proof of Theorem.

Note that $V_{i}$ can be empty for a admissible partition $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ of $M_{G}$ , so the $t h r e e$ – $w a y$ $s w i t c h i n g$ can induces some particular equivalent switchings for $M_{G}$ .

Corollary 1. If $V (M_{G})$ has a partition $V_{1} \cup V_{2}$ such that there exists no arc from $V_{1}$ to $V_{2}$ , then the graph obtained from $M_{G}$ by replacing all undirected edges ${u, v}$ with $u \in V_{1}$ and $v \in V_{2}$ by $(u, v)$ and replacing all arcs $(u, v)$ with $u \in V_{2}$ and $v \in V_{1}$ by ${u, v}$ is $H_{f}^{k}$ -cospectral with $M_{G}$ .

Corollary 2. If $V (M_{G})$ has a partition $V_{1} \cup V_{2}$ such that $[V_{1}, V_{2}]$ only contains arcs from $V_{2}$ to $V_{1}$ , then the graph obtained from $M_{G}$ by replacing all arcs $(u, v)$ with $u \in V_{2}$ and $v \in V_{1}$ by $(v, u)$ is $H_{f}^{k}$ -cospectral with $M_{G}$ .

Corollary 3. If $k = 3$ and $M_{G}$ has a partition $V_{1} \cup V_{2}$ ,then the graph obtained from $M_{G}$ by following changes is $H_{f}^{k}$ -cospectral with $M_{G}$ :

replacing all arcs $(u, v)$ with $u \in V_{2}$ and $v \in V_{1}$ by ${u, v}$ ;
replacing all undirected edges ${u, v}$ with $u \in V_{2}$ and $V \in v_{1}$ by $(v, u)$ ;
replacing all arcs $(u, v)$ with $u \in V_{1}$ and $V \in v_{2}$ by $(v, u)$ .

3. $H_{f}^{k}$ -cospectrality with Underlying Graph

In this section, we focus on the $H_{f}^{k}$ -cospectrality of $M_{G}$ and its underlying graph $G$ .

Theorem 3. Let $M_{G}$ be a connected mixed graph. Then the following statements are equivalent:

$G$ and $M_{G}$ are $H_{f}^{k}$ -cospectral.
$λ_{1} (G) = λ_{1} (M_{G})$ .
$M_{G}$ admits a $A$ – $p a r t i t i o n$ .

Proof. It’s obvious that (i) implies (ii). Note that $M_{G}$ could be changed into $G$ by a $t h r e e$ – $w a y$ $s w i t c h i n g$ if it admits a $A$ – $p a r t i t i o n$ . So (iii) implies (i) by Theorem 2. In order to complete the proof, it suffices to prove that (ii) implies (iii). Assume that (ii) holds. Let $H_{f}^{k} (M_{G}) = (h_{u v})_{n \times n}$ and $H_{f}^{k} (G) = A_{f} (G) = (a_{u v})_{n \times n}$ , let $Y = (y_{1}, y_{2}, \dots, y_{n})^{T} \in C^{n}$ be a normalized eigenvector of $H_{f}^{k} (M_{G})$ corresponding to $λ_{1} (M_{G})$ . Note that $| h_{u, v} | = a_{u, v}$ for every $u, v \in | V (M_{G}) |$ . Then we have $λ_{1} (M_{G}) = \bar{Y^{T}} \cdot H_{f}^{k} (M_{G}) \cdot Y$ $= \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} \bar{y_{u}} h_{u, v} y_{v}$ $\leq \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} | \bar{y_{u}} y_{v} | \cdot | h_{u, v} |$ $\begin{matrix} (1) & = \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} | y_{u} | | y_{v} | \cdot a_{u, v} \leq λ_{1} (G) . \end{matrix}$ The equality in (1) must holds since $λ_{1} (M_{G}) = λ_{1} (G)$ , which require that $\begin{matrix} (2) & h_{u, v} {\bar{y}}_{u} y_{v} = | h_{u, v} {\bar{y}}_{u} y_{v} | \end{matrix}$ for all edges $u v$ in $G$ . Without loss of generality, we can assume that a vertex $v_{0} \in V (M_{G})$ such that $y_{v_{0}} \in R^{+}$ , then $\frac{| {\bar{y}}_{v_{0}} |}{{\bar{y}}_{v_{0}}} = 1$ and $h_{v_{0}, v} y_{v} = | h_{v_{0}, v} y_{v} |$ for all $y \in N_{G} (v_{0})$ by (4), it follows that $\frac{y_{v}}{| y_{v} |} = ω^{- 1}$ if $v \in N_{M_{G}}^{+} (v_{0})$ ; $\frac{y_{v}}{| y_{v} |} = 1$ if $v \in N_{M_{G}}^{0} (v_{0})$ and $\frac{y_{v}}{| y_{v} |} = ω$ if $v \in N_{M_{G}}^{-} (v_{0})$ .

Note that $G$ is connected, by repeating the above steps, it follows that $\frac{y_{v}}{| y_{v} |} = ω^{t}$ with $t \in Z$ for all $v \in V (M_{G})$ . Let $V_{i} = {v \in V (M_{G}) : \frac{y_{v}}{| y_{v} |} = ω^{t}, w h e r e t \equiv i (m o d k)}$ , where $i \in {1, 2, \dots, k}$ . it’s easy to check that $V_{1}, V_{2}, \dots, V_{k}$ form a $A$ – $p a r t i t i o n$ of $M_{G}$ , which complete the proof.

With Theorem 3, we have following corollary.

Corollary 4. A mixed tree $M_{T}$ is $H_{f}^{k}$ -cospectral to its underlying graph.

Proof. We construct a $A$ – $p a r t i t i o n$ of $V (M_{T})$ to prove this corollary. Choose a vertex $v_{0} \in V (M_{T})$ and denote by $P (u)$ the unique $(v_{0}, u)$ -path in $T$ for all $u \in V (M_{T})$ , then we define a function $f$ on $V (G)$ , where the value of $f (u)$ equals to the number of arcs toward $v_{0}$ in $P (u)$ minus the number of arcs toward $u$ in $P (u)$ .

Let $V_{i} = {u \in V (M_{T}) : f (u) \equiv i (m o d k)}$ , where $i \in {1, 2, \dots, k}$ . Obviously $V (M_{T}) = V_{1} \cup V_{2} \cup \dots \cup V_{k}$ and it’s easy to check that for every undirected edge ${u, v}$ with $u \in V_{i}$ and $v \in V_{j}$ , $f (u) - f (v) = 0$ so $i = j$ ; for every arc $(u, v)$ with $u \in V_{i}$ and $v \in V_{j}$ , $f (u) - f (v) = 1$ so $i - j \equiv 1 (m o d k)$ . It implies that $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ forms a $A$ – $p a r t i t i o n$ of $V (M_{T})$ and complete the proof.

Then the main Theorem in [12] can be directly generalized to mixed trees.

Corollary 5. Assume that $f (x, y)$ is increasing and convex in variable $x$ , Then the mixed trees in $n$ vertices owns largest $H_{f}^{k}$ -spectral radius if and only if its underlying graph is $S_{n}$ or a double star $S_{d, n - d}$ for some $d \in {2, \dots, n - 2}$ .

Corollary 6. Assume that $f (x, y)$ has the form $P (x, y)$ or $\sqrt{P (x, y)}$ , where $P (x, y)$ is a symmetric polynomial with nonnegative coefficients and zero constant term. Then the mixed tree on $n (n \geq 9)$ vertices owns the smallest $H_{f}^{k}$ -spectral radius if and only if its underlying graph is $P_{n}$ .

4. Proof of Theorem 1

Lemma 1. Let $M_{G}$ be a mixed graph. Then $| λ_{i} (M_{G}) | \leq λ_{1} (G)$ for all $i \in {1, 2 \dots, n}$ .

Proof. Let $Y = (y_{1}, y_{2}, \dots, y_{n})^{T} \in C^{n}$ be a normalized eigenvector of $H_{f}^{k} (M_{G})$ corresponding to $λ_{i} (M_{G})$ . Then we have $\begin{aligned} | λ_{i} (M_{G}) | = & | {\bar{Y}}^{T} \cdot H_{f}^{k} (M_{G}) \cdot Y | \\ = & | \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} {\bar{y}}_{u} h_{u, v} y_{v} | \\ \leq & \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} | {\bar{y}}_{u} y_{v} | \cdot | h_{u, v} | \\ = & \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} | y_{u} | | y_{v} | \cdot a_{u, v} \leq λ_{1} (G) . \end{aligned}$ Which completes the proof.

Note that $| λ_{n} (M_{G}) | > | λ_{1} (M_{G}) |$ is possible for a mixed graph $M_{G}$ . By Lemma 1, it follows that $ρ_{f}^{k} (G) = ρ_{f}^{k} (M_{G})$ if and only if $λ_{1} (M_{G}) = λ_{1} (G)$ or $- λ_{n} (M_{G}) = λ_{1} (G)$ . In the following two lemmas we focus on the condition of the second equality.

Lemma 2. Let $k$ be an odd positive integer and $M_{G}$ be a connected mixed graph, then $- λ_{n} (M_{G}) = λ_{1} (G)$ if and only if $V (M_{G})$ admits a $C$ – $p a r t i t i o n$ .

Proof. If $V (M_{G})$ admits a $C$ – $p a r t i t i o n$ , say $V_{1} \cup \dots \cup V_{k} \cup U_{1} \cup \dots \cup U_{k}$ . Then $G$ is a bipartite graph and $(V_{1} \cup U_{1}), (V_{1} \cup U_{1}), \dots, (V_{k} \cup U_{k})$ form a $A$ – $p a r t i t i o n$ of $V (M_{G})$ , by Perron-Frobinius Theorem and Theorem 3 it follows that $λ_{n} (M_{G}) = λ_{n} (G) = - λ_{1} (G)$ .

If $- λ_{n} (M_{G}) = λ_{1} (G)$ holds, Let $H_{f}^{k} (M_{G}) = (h_{u v})_{n \times n}$ and $H_{f}^{k} (G) = A_{f} (G) = (a_{u v})_{n \times n}$ , let $Y = (y_{1}, y_{2}, \dots, y_{n})^{T} \in C^{n}$ be a normalized eigenvector of $H_{f}^{k} (M_{G})$ corresponding to $λ_{n} (M_{G})$ . Then we have $- λ_{n} (M_{G}) = - {\bar{Y}}^{T} \cdot H_{f}^{k} (M_{G}) \cdot Y$ $\begin{matrix} = - \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} \bar{y_{u}} h_{u v} y_{v} \end{matrix}$ $\leq \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} | \bar{y_{u}} y_{v} | \cdot | h_{u v} |$ $\begin{matrix} (3) & = \sum_{u \in V (M_{G})} \sum_{v \in V (M_{G})} | y_{u} | | y_{v} | \cdot a_{u v} \leq λ_{1} (G) . \end{matrix}$ The equality in (3) must holds because $- λ_{n} (M_{G}) = λ_{1} (G)$ , which requires that $\begin{matrix} (4) & h_{u, v} {\bar{y}}_{u} y_{v} = - | h_{u, v} {\bar{y}}_{u} y_{v} |, \end{matrix}$ for all edges $u v$ in $G$ . Without loss of generality, we can assume that a vertex $v_{0} \in V (M_{G})$ such that $y_{v_{0}} \in R^{+}$ , then $\frac{| {\bar{y}}_{v_{0}} |}{{\bar{y}}_{v_{0}}} = 1$ and $h_{v_{0}, v} y_{v} = | h_{v_{0}, v} y_{v} |$ for all $y \in N_{G} (v_{0})$ by (4), it follows that $\frac{y_{v}}{| y_{v} |} = - ω^{- 1}$ if $v \in N_{M_{G}}^{+} (v_{0})$ ; $\frac{y_{v}}{| y_{v} |} = - 1$ if $v \in N_{M_{G}}^{0} (v_{0})$ and $\frac{y_{v}}{| y_{v} |} = - ω$ if $v \in N_{M_{G}}^{-} (v_{0})$ .

Note that $G$ is connected, by repeating the above steps, it follows that $\frac{y_{v}}{| y_{v} |} \in {\pm ω^{t}, t \in Z}$ for all $v \in V (M_{G})$ . Let $V_{i} = {v \in V (M_{G}) : \frac{y_{v}}{| y_{v} |} = ω^{t}, w h e r e t \equiv i (m o d k)}$ and $U_{i} = {v \in V (M_{G}) : \frac{y_{v}}{| y_{v} |} = - ω^{t}, w h e r e t \equiv i (m o d k)}$ where $i \in {1, 2, \dots, k}$ . it’s easy to check that $V_{1} \cup \dots \cup V_{k} \cup U_{1} \cup \dots \cup U_{k}$ form a $C$ – $p a r t i t i o n$ of $V (M_{G})$ , which complete the proof.

Note that a $C$ – $p a r t i t i o n$ $V_{1}, \dots, V_{k}, U_{1}, \dots, U_{k}$ of $V (G)$ forms into a $A$ – $p a r t i t i o n$ $(V_{1} \cup U_{1}), (V_{1} \cup U_{1}), \dots, (V_{k} \cup U_{k})$ . So we have following corollary.

Corollary 7. Let $k$ be an odd positive integer and $M_{G}$ be a connected mixed graph, then $ρ (G) = ρ (M_{G})$ if and only if $V (M_{G})$ admits a $A$ – $p a r t i t i o n$ .

Lemma 3. Let $k$ be an even positive integer and $G$ be a connected, regular graph, then a mixed graph $M_{G}$ with underlying graph $G$ such that $- λ_{n} (M_{G}) = λ_{1} (G)$ if and only if $M_{G}$ admits a $B$ – $p a r t i t i o n$ .

Proof. Assume that $G$ is $Δ$ -regular, let $H_{f}^{k} (M_{G}) = (h_{u v})_{n \times n}$ and $H_{f}^{k} (G) = A_{f} (G) = (a_{u v})_{n \times n}$ , let $X = (x_{1}, x_{2}, \dots, x_{n})^{T} \in R^{n}$ be a normalized eigenvector of $A_{f} (G)$ corresponding to $λ_{1} (G)$ and $Y = (y_{1}, y_{2}, \dots, y_{n})^{T} \in C^{n}$ be a normalized eigenvector of $H_{f}^{k} (M_{G})$ corresponding to $λ_{n} (M_{G})$ .

Assume that $- λ_{n} (M_{G}) = λ_{1} (G)$ , then by the similar proof it follows that $\begin{matrix} (5) & h_{u, v} {\bar{y}}_{u} y_{v} = - | h_{u, v} {\bar{y}}_{u} y_{v} |, \end{matrix}$ for all edges $u v$ in $G$ . Without loss of generality, we can assume that a vertex $v_{0} \in V (M_{G})$ such that $y_{v_{0}} \in R^{+}$ , then $\frac{| {\bar{y}}_{v_{0}} |}{{\bar{y}}_{v_{0}}} = 1$ and $h_{v_{0}, v} y_{v} = | h_{v_{0}, v} y_{v} |$ for all $y \in N_{G} (v_{0})$ by (5), it follows that $\frac{y_{v}}{| y_{v} |} = - ω^{- 1} = ω^{\frac{k}{2} - 1}$ if $v \in N_{M_{G}}^{+} (v_{0})$ ; $\frac{y_{v}}{| y_{v} |} = - 1 = ω^{\frac{k}{2}}$ if $v \in N_{M_{G}}^{0} (v_{0})$ and $\frac{y_{v}}{| y_{v} |} = - ω = ω^{\frac{k}{2} + 1}$ if $v \in N_{M_{G}}^{-} (v_{0})$ .

Note that $G$ is connected, by repeating the above steps, it follows that $\frac{y_{v}}{| y_{v} |} \in {ω^{t}, t \in Z}$ for all $v \in V (M_{G})$ . Let $V_{i} = {v \in V (M_{G}) : \frac{y_{v}}{| y_{v} |} = ω^{t}, w h e r e t \equiv i (m o d k)}$ , where $i \in {1, 2, \dots, k}$ . it’s easy to check that $V_{1} \cup \dots \cup V_{k}$ forms a $B$ – $p a r t i t i o n$ of $V (M_{G})$ .

Assume that $M_{G}$ admits a $B$ – $p a r t i t i o n$ $V_{1} \cup V_{2} \cup \dots \cup V_{k}$ , we construct a vector $Z \in C^{n}$ with $z_{u} = x_{u} \cdot w^{i}$ , where $u \in V_{i}$ . Then for any $u \in V (M_{G})$ with $u \in V_{i}$ , $\begin{aligned} (H_{f}^{k} (G) \cdot Z)_{u} = & f (Δ, Δ) (\sum_{v \in N_{M_{G}}^{0} (u)} z_{v} + \sum_{v \in N_{M_{G}}^{+} (u)} ω z_{v} + \sum_{v \in N_{M_{G}}^{-} (u)} ω^{- 1} z_{v}) \\ = & f (Δ, Δ) (\sum_{v \in N_{M_{G}}^{0} (u)} x_{v} ω^{i + \frac{k}{2}} + \sum_{v \in N_{M_{G}}^{+} (u)} ω x_{v} ω^{i + \frac{k}{2} - 1} \\ + \sum_{v \in N_{M_{G}}^{-} (u)} ω^{- 1} x_{v} ω^{i + \frac{k}{2} + 1}) \\ = & - f (Δ, Δ) ω^{i} \sum_{v \in N_{G} (u)} x_{v} \\ = & - λ_{1} (G) ω^{i} x_{u} = - λ_{1} z_{u} . \end{aligned}$ It follows that $H_{f}^{k} (G) \cdot Z = - λ_{1} (G) Z$ , so $- λ_{n} (M_{G}) = λ_{1} (G)$ .

Combined with Theorem 3 we have following corollary.

Corollary 8. Let $k$ be a even integer positive and $G$ be a connected, regular graph, then a mixed graph $M_{G}$ such that $ρ_{f}^{k} (M_{G}) = ρ_{f}^{k} (G)$ if and only if $V (G)$ admits a $A$ – $p a r t i t i o n$ or a $B$ – $p a r t i t i o n$ .

Lemma 4. Let $k$ be a positive integer and $f (x, y) > 0$ be a symmetric real function, not decreasing in variable $x$ , then for any proper subgraph $H$ of $G$ , we have $ρ_{f}^{k} (H) < ρ_{f}^{k} (G)$ .

Proof. We have following two claims.

Claim 1. For any proper, spanning and connected subgraph $H$ of $G$ , $ρ_{f}^{k} (H) < ρ_{f}^{k} (G)$ .

Let $y_{1} > 0$ , $y_{2} > 0$ be the Perron vector of $ρ (G)$ and $ρ (H)$ , respectively. Note that $A_{f} (G) - A_{f} (G^{'}) \geq 0$ and $A_{f} (G) - A_{f} (G^{'}) \neq 0$ since $f (x, y)$ is symmetric, not decreasing in $x$ and $H$ is a proper subgraph of $G$ . Then $(ρ_{f}^{k} (G) - ρ_{f}^{k} (H)) {y_{1}}^{'} y_{2} = {y_{1}}^{'} (A_{f} (G) - A_{f} (H)) y_{2} > 0.$ It follows that $ρ_{f}^{k} (G) > ρ_{f}^{k} (H)$ .

Claim 2. For any proper, induced subgraph $H$ of $G$ , $ρ_{f}^{k} (H) < ρ_{f}^{k} (G)$ .

Let $y > 0$ , $y_{1} > 0$ be the Perron vector of $ρ_{f}^{k} (G)$ and $ρ_{f}^{k} (H)$ , respectively. We can assume that $A_{f} (G) = (\begin{matrix} A_{f} (H) + K & L \\ L^{'} & M \end{matrix})$ where $K \geq 0$ is symmetric. Then $A_{f} (G) (\begin{matrix} y_{1} \\ 0 \end{matrix}) = (\begin{matrix} (A_{f} (H) + K) y_{1} \\ L^{'} y_{1} \end{matrix}) = (\begin{matrix} ρ_{f}^{k} (H) y_{1} + K y_{1} \\ L^{'} y_{1} \end{matrix}) \geq ρ_{f}^{k} (H) (\begin{matrix} y_{1} \\ 0 \end{matrix}) .$ If $A_{f} (G) (\begin{matrix} y_{1} \\ 0 \end{matrix}) = ρ_{f}^{k} (H) (\begin{matrix} y_{1} \\ 0 \end{matrix}),$ then $(\begin{matrix} y_{1} \\ 0 \end{matrix}) \geq 0$ is a eigenvector of $A_{f} (G)$ corresponding to $ρ_{f}^{k} (G)$ , which is contradict to Perron-Frobinius Theorem. So we have $A_{f} (G) (\begin{matrix} y_{1} \\ 0 \end{matrix}) \geq ρ_{f}^{k} (H) (\begin{matrix} y_{1} \\ 0 \end{matrix})$ and $A_{f} (G) (\begin{matrix} y_{1} \\ 0 \end{matrix}) \neq ρ_{f}^{k} (H) (\begin{matrix} y_{1} \\ 0 \end{matrix})$ . It follows that $(ρ_{f}^{k} (G) - ρ_{f}^{k} (H)) y^{'} (\begin{matrix} y_{1} \\ 0 \end{matrix}) = y^{'} (A_{f} (G) (\begin{matrix} y_{1} \\ 0 \end{matrix}) - ρ_{f}^{k} (H) (\begin{matrix} y_{1} \\ 0 \end{matrix})) \geq 0$ , so $ρ_{f}^{k} (G) > ρ_{f}^{k} (H)$ .

For any proper subgraph $H$ of $G$ , we can assume that $H$ is connected. Then $H$ must be a spanning subgraph of some induced subgraph $H^{'}$ of $G$ . If $H^{'} = G$ , then by Claim 1 it follows that $ρ_{f}^{k} (H) < ρ_{f}^{k} (H^{'}) = ρ_{f}^{k} (G)$ . If $H^{'} \neq G$ , then by Claim 2 it follows that $ρ_{f}^{k} (H) \leq ρ_{f}^{k} (H^{'}) < ρ_{f}^{k} (G)$ . It completes the proof.

Proof of Theorem 1. Note that if $G$ is a $Δ$ -regular graph, then $A_{f} (G) = f (Δ, Δ) A (G)$ and $ρ_{f}^{k} (G) = f (Δ, Δ) Δ (G)$ . Since every graph with maximum degree $Δ$ must be a subgraph of a $Δ$ -regular graph, by Lemma 4 it follows that $ρ_{f}^{k} (G) \leq f (Δ, Δ) Δ (G)$ for all graphs $G$ with maximum degree $Δ$ , where equality holds if and only if $G$ is $Δ$ -regular.

For a mixed graph $M_{G}$ with maximum degree $Δ$ , by Lemma 1 it follows that $ρ_{f}^{k} (M_{G}) \leq f (Δ, Δ) Δ (G)$ , by Corollary 7,8 it follows that equality holds if and only if underlying graph $G$ is $Δ (G)$ -regular and $M_{G}$ admits a $A$ – $p a r t i t i o n$ or $M_{G}$ admits a $B$ – $p a r t i t i o n$ when $k$ is even.

Acknowledgments

The work was partially supported by the National Natural Science Foundation of China under Grants 11771172, 12061039.

Conflict of Interest

The authors declare no conflict of interest.

References:

Mohar, B., 2020. A new kind of Hermitian matrices for digraphs. Linear Algebra and its Applications, 584, pp.343-352.
Das, K.C., Gutman, I., Milovanović, I., Milovanović, E. and Furtula, B., 2018. Degree-based energies of graphs. Linear Algebra and its Applications, 554, pp.185-204.
Yu, Y., Geng, X. and Zhou, Z., 2023. The k-generalized Hermitian adjacency matrices for mixed graphs. Discrete Mathematics, 346(2), p.113254.
Guo, K. and Mohar, B., 2017. Hermitian adjacency matrix of digraphs and mixed graphs. Journal of Graph Theory, 85(1), pp.217-248.
Liu, J. and Li, X., 2015. Hermitian-adjacency matrices and Hermitian energies of mixed graphs. Linear Algebra and its Applications, 466, pp.182-207.
Estrada, E., 2017. The ABC matrix. Journal of Mathematical Chemistry, 55, pp.1021-1033.
Chen, X., 2019. On extremality of ABC spectral radius of a tree. Linear Algebra and Its Applications, 564, pp.159-169.
Hosamani, S.M., Kulkarni, B.B., Boli, R.G. and Gadag, V.M., 2017. QSPR analysis of certain graph theocratical matrices and their corresponding energy. Applied Mathematics and Nonlinear Sciences, 2(1), pp.131-150.
Ghorbani, M., Li, X., Zangi, S. and Amraei, N., 2021. On the eigenvalue and energy of extended adjacency matrix. Applied Mathematics and Computation, 397, p.125939.
Guo, X. and Gao, Y., 2020. Arithmetic-geometric spectral radius and energy of graphs. MACTH Commun. Math. Comput. Chem, 83, pp.651-660.
Zheng, L., Tian, G.X. and Cui, S.Y., 2020. On spectral radius and energy of arithmetic-geometric matrix of graphs. MATCH Commun. Math. Comput. Chem, 83, pp.635-650.
Li, X. and Wang, Z., 2021. Trees with extremal spectral radius of weighted adjacency matrices among trees weighted by degree-based indices. Linear Algebra and Its Applications, 620, pp.61-75.

[1] Mohar, B., 2020. A new kind of Hermitian matrices for digraphs. Linear Algebra and its Applications, 584, pp.343-352.

[2] Das, K.C., Gutman, I., Milovanović, I., Milovanović, E. and Furtula, B., 2018. Degree-based energies of graphs. Linear Algebra and its Applications, 554, pp.185-204.

[3] Yu, Y., Geng, X. and Zhou, Z., 2023. The k-generalized Hermitian adjacency matrices for mixed graphs. Discrete Mathematics, 346(2), p.113254.

[4] Guo, K. and Mohar, B., 2017. Hermitian adjacency matrix of digraphs and mixed graphs. Journal of Graph Theory, 85(1), pp.217-248.

[5] Liu, J. and Li, X., 2015. Hermitian-adjacency matrices and Hermitian energies of mixed graphs. Linear Algebra and its Applications, 466, pp.182-207.

[6] Estrada, E., 2017. The ABC matrix. Journal of Mathematical Chemistry, 55, pp.1021-1033.

[7] Chen, X., 2019. On extremality of ABC spectral radius of a tree. Linear Algebra and Its Applications, 564, pp.159-169.

[8] Hosamani, S.M., Kulkarni, B.B., Boli, R.G. and Gadag, V.M., 2017. QSPR analysis of certain graph theocratical matrices and their corresponding energy. Applied Mathematics and Nonlinear Sciences, 2(1), pp.131-150.

[9] Ghorbani, M., Li, X., Zangi, S. and Amraei, N., 2021. On the eigenvalue and energy of extended adjacency matrix. Applied Mathematics and Computation, 397, p.125939.

[10] Guo, X. and Gao, Y., 2020. Arithmetic-geometric spectral radius and energy of graphs. MACTH Commun. Math. Comput. Chem, 83, pp.651-660.

[11] Zheng, L., Tian, G.X. and Cui, S.Y., 2020. On spectral radius and energy of arithmetic-geometric matrix of graphs. MATCH Commun. Math. Comput. Chem, 83, pp.635-650.

[12] Li, X. and Wang, Z., 2021. Trees with extremal spectral radius of weighted adjacency matrices among trees weighted by degree-based indices. Linear Algebra and Its Applications, 620, pp.61-75.

Contents

Utilitas Mathematica