Menu
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 \(\Delta\), and characterize the corresponding extremal graphs.
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^0_{M_G}(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_{uv})\), which is as follows: \[\begin{aligned} h_{uv}= \begin{cases} e^{\frac{2\pi \bf{i}}{k}}, &\text{if}\ (u,v)\ \text{is an arc from}\ u\ \text{to}\ v;\\ e^{-\frac{2\pi \bf{i}}{k}}, &\text{if}\ (v,u)\ \text{is\ an arc from}\ v\ \text{to}\ u;\\ 1, &\text{if}\ \{u,v\}\ \text{is an undirected edge};\\ 0, &\text{otherwise}, \end{cases} \end{aligned}\] where \(\bf{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_{uv})\) of \(G\) is defined as follows: \[\begin{aligned} a_{uv}= \begin{cases} f(d_u,d_v), &\text{if}\ uv\in E(G);\\ 0, &\text{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}{xy}}\), \(A_f(G)\) is the \(ABC\) 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 \(harmonic\) matrix and was introduced in [8]; When \(f(x,y)=\frac{x^2+y^2}{2xy}\), \(A_f(G)\) is the \(AG\) 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^k_f(M_G)=(h_{uv})\) for a mixed graph \(M_G\), where \[\begin{aligned} h_{uv}= \begin{cases} f(d_u,d_v)\cdot\omega, &\text{if}\ (u,v)\ \text{is an arc from}\ u\ \text{to}\ v;\\ f(d_u,d_v)\cdot\bar{\omega}, &\text{if}\ (v,u)\ \text{is an arc from}\ v\ \text{to}\ u;\\ f(d_u,d_v), &\text{if}\ \{u,v\}\ \text{is an undirected\ edge};\\ 0, &\text{otherwise},\\ \end{cases} \end{aligned}\] \(\omega=cos(\frac{2\pi}{k})+{\bf{i}}sin(\frac{2\pi}{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^k_f(M_G)\) is the matrix \(H^k(M_G)\), which is defined in [3]; when \(k=1\), \(H^k_f(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^k_f(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^k_f(M_G)\) is Hermitian and the eigenvalues of \(H^k_f(M_G)\) are real. With fixed \(f\), \(k\) and a mixed graph \(M_G\), let \(\lambda_1(M_G)\ge\lambda_2(M_G)\ge\cdots\lambda_n(M_G)\) be n eigenvalues of \(H^k_f(M_G)\) with \(|V(M_G)|=n\). The collection \(\{\lambda_1(M_G), \lambda_2(M_G), \cdots,\lambda_n(M_G)\}\) is called the \(H^k_f\)-spectrum of \(M_G\), we say \(M_G\) is \(H^k_f\)-cospectral to its underlying graph if \(H^k_f(M_G)\) and \(H^k_f(G)\) have the same \(H^k_f\)-spectrum. We call the spectral radius of \(H^k_f(M_G)\) the \(H^k_f\)-spectrum radius of \(M_G\), denoted by \(\rho^k_f(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,
When \(k=6\), three partitions can be seen in Figures 1 and 2. By the Definition 2, \(V(M_G)\) has a \(\mathscr{B}\)–\(partition\) only if \(k\) is an even positive integer and it’s easy to check that a \(\mathscr{C}\)–\(partition\) of \(V(M_G)\) is a \(\mathscr{A}\)–\(partition\). The main result of paper is as follows:
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 \(\Delta\), we have \(\rho^k_f(M_G)\leq f(\Delta,\Delta)\Delta\), where equality holds if and only if \(M_G\) such that \(G\) is \(\Delta\)-regular and \(V(M_G)\) admits a \(\mathscr{A}\)–\(partition\) or a \(\mathscr{B}\)–\(partition\).
The structure of the paper is as follows. In Section \(2\) we show a disturbance on \(E(M_G)\) which remains the \(H^k_f\)-spectrum of \(M_G\). In Section \(3\) we characterize a family of mixed graphs which are \(H^k_f\)-cospectral to their underlying graph and in Section \(4\) we prove Theorem 1
In this section, we focus on some sufficient conditions of \(H^k_f\)-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:
We say a mixed graph \(M_G\) is admissible if it has an admissible partition.
For a mixed graph \(M_G\), a \(three\)–\(way\) \(switching\) 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):
Theorem 2. If a mixed graph \(M_G^{'}\) is obtained from an admissible mixed graph \(M_G\) by a \(three\)–\(way\) \(switching\), then \(M_G^{'}\) is \(H^k_f\)-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,\ldots,k\}\) and \(D=diag\{\omega I_{n_1},\omega^2I_{n_2},\ldots,,\omega^kI_{n_k}\}\), let \(H_f^k(M_G)=(h_{ij})_{n\times n}\) and \(H_f^k(M'_{G})=(h'_{ij})_{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}=\omega^{k+j-i}h_{uv}\). If \(u\) is not adjacent to \(v\) in \(M_G\), then \(\omega^{k+j-i}h_{uv}=0=h'_{uv}\) 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'_{uv}=h_{uv}\) 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)\omega^{-1}=\omega^{k+j-i}h_{uv}\). 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}=\omega^{-1}f(d_u,d_v)\omega=\omega^{k+j-i}h_{uv}\).
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)\omega^{-1}=\omega^{-2}f(d_u,d_v)\omega^1=\omega^{k+j-i}h_{uv}\).
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 \(three\)–\(way\) \(switching\) 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^k_f\)-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^k_f\)-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^k_f\)-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)\).
In this section, we focus on the \(H^k_f\)-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^k_f\)-cospectral.
\(\lambda_{1}(G)=\lambda_{1}(M_G)\).
\(M_G\) admits a \(\mathscr{A}\)–\(partition\).
Proof. It’s obvious that (i) implies (ii). Note that \(M_G\) could be changed into \(G\) by a \(three\)–\(way\) \(switching\) if it admits a \(\mathscr{A}\)–\(partition\). 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^k_f(M_G)=(h_{uv})_{n\times n}\) and \(H^k_f(G)=A_f(G)=(a_{uv})_{n\times n}\), let \(Y=(y_1,y_2,\ldots,y_n)^{T}\in C^n\) be a normalized eigenvector of \(H^k_f(M_G)\) corresponding to \(\lambda_1(M_G)\). Note that \(|h_{u,v}|=a_{u,v}\) for every \(u,v\in |V(M_G)|\). Then we have \[ \lambda_1(M_G)=\bar{Y^T}\cdot H^k_f(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\lambda_1(G). \label{eq3.1}\tag{1}\] The equality in (1) must holds since \(\lambda_1(M_G)=\lambda_1(G)\), which require that \[\label{eq3.2}\tag{2} h_{u,v}\bar{y}_uy_v=|h_{u,v}\bar{y}_uy_v|\] for all edges \(uv\) 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|}=\omega^{-1}\) if \(v\in N^+_{M_G}(v_0)\); \(\frac{y_v}{|y_v|}=1\) if \(v\in N^0_{M_G}(v_0)\) and \(\frac{y_v}{|y_v|}=\omega\) 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|}=\omega^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|}=\omega^t,\ where\ t\equiv i(mod\ k)\}\), where \(i\in\{1,2,\ldots,k\}\). it’s easy to check that \(V_1,V_2,\ldots,V_k\) form a \(\mathscr{A}\)–\(partition\) of \(M_G\), which complete the proof. ◻
With Theorem 3, we have following corollary.
Corollary 4. A mixed tree \(M_T\) is \(H^k_f\)-cospectral to its underlying graph.
Proof. We construct a \(\mathscr{A}\)–\(partition\) 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(mod\ k)\}\), where \(i\in\{1,2,\ldots,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(mod\ k)\). It implies that \({V_1}\cup{V_2}\cup\dots\cup{V_k}\) forms a \(\mathscr{A}\)–\(partition\) 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^k_f\)-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,\ldots,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\geq9)\) vertices owns the smallest \(H^k_f\)-spectral radius if and only if its underlying graph is \(P_n\).
Lemma 1. Let \(M_G\) be a mixed graph. Then \(|\lambda_i(M_G)|\leq\lambda_1(G)\) for all \(i\in\{1,2\ldots,n\}\).
Proof. Let \(Y=(y_1,y_2,\ldots,y_n)^{T}\in C^n\) be a normalized eigenvector of \(H^k_f(M_G)\) corresponding to \(\lambda_i(M_G)\). Then we have \[\begin{aligned} |\lambda_i(M_G)|=&|\bar{Y}^T\cdot H^k_f(M_G)\cdot Y|\notag\\ =& |\sum_{u\in V(M_G)}{\sum_{v\in V(M_G)}{\bar{y}_uh_{u,v}y_v}}|\notag\\ \leq& \sum_{u\in V(M_G)}{\sum_{v\in V(M_G)}{|\bar{y}_uy_v|\cdot|h_{u,v}|}}\notag\\ =& \sum_{u\in V(M_G)}{\sum_{v\in V(M_G)}{|y_u||y_v|\cdot a_{u,v}}}\leq\lambda_1(G). \end{aligned}\] Which completes the proof. ◻
Note that \(|\lambda_n(M_G)|>|\lambda_1(M_G)|\) is possible for a mixed graph \(M_G\). By Lemma 1, it follows that \(\rho^k_f(G)=\rho^k_f(M_G)\) if and only if \(\lambda_1(M_G)=\lambda_1(G)\) or \(-\lambda_n(M_G)=\lambda_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 \(-\lambda_n(M_G)=\lambda_1(G)\) if and only if \(V(M_G)\) admits a \(\mathscr{C}\)–\(partition\).
Proof. If \(V(M_G)\) admits a \(\mathscr{C}\)–\(partition\), 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),\ldots,\ (V_k\cup U_k)\) form a \(\mathscr{A}\)–\(partition\) of \(V(M_G)\), by Perron-Frobinius Theorem and Theorem 3 it follows that \(\lambda_n(M_G)=\lambda_n(G)=-\lambda_1(G)\).
If \(-\lambda_n(M_G)=\lambda_1(G)\) holds, Let \(H^k_f(M_G)=(h_{uv})_{n\times n}\) and \(H^k_f(G)=A_f(G)=(a_{uv})_{n\times n}\), let \(Y=(y_1,y_2,\ldots,y_n)^{T}\in C^n\) be a normalized eigenvector of \(H^k_f(M_G)\) corresponding to \(\lambda_n(M_G)\). Then we have \[ -\lambda_n(M_G)=-\bar{Y}^T\cdot H^k_f(M_G)\cdot Y\] \[ = -\sum_{u\in V(M_G)}{\sum_{v\in V(M_G)}{\bar{y_u}h_{uv}y_v}}\notag\] \[ \leq \sum_{u\in V(M_G)}{\sum_{v\in V(M_G)}{|\bar{y_u}y_v|\cdot|h_{uv}|}}\] \[ = \sum_{u\in V(M_G)}{\sum_{v\in V(M_G)}{|y_u||y_v|\cdot a_{uv}}}\leq\lambda_1(G). \label{eq4.1}\tag{3}\] The equality in (3) must holds because \(-\lambda_n(M_G)=\lambda_1(G)\), which requires that \[h_{u,v}\bar{y}_uy_v=-|h_{u,v}\bar{y}_uy_v|,\tag{4}\] for all edges \(uv\) 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|}=-\omega^{-1}\) if \(v\in N^+_{M_G}(v_0)\); \(\frac{y_v}{|y_v|}=-1\) if \(v\in N^0_{M_G}(v_0)\) and \(\frac{y_v}{|y_v|}=-\omega\) 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\ \omega^t,t\in Z\}\) for all \(v\in V(M_G)\). Let \(V_i=\{v\in V(M_G):\frac{y_v}{|y_v|}=\omega^t,\ where\ t\equiv i(mod\ k)\}\) and \(U_i=\{v\in V(M_G):\frac{y_v}{|y_v|}=-\omega^t,\ where\ t\equiv i(mod\ k)\}\) where \(i\in\{1,2,\ldots,k\}\). it’s easy to check that \({V_1}\cup\dots\cup{V_k}\cup{U_1}\cup\dots\cup{U_k}\) form a \(\mathscr{C}\)–\(partition\) of \(V(M_G)\), which complete the proof. ◻
Note that a \(\mathscr{C}\)–\(partition\) \({V_1},\ldots,{V_k},{U_1},\ldots,{U_k}\) of \(V(G)\) forms into a \(\mathscr{A}\)–\(partition\) \((V_1\cup U_1),\ (V_1\cup U_1),\ldots,\ (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 \(\rho(G)=\rho(M_G)\) if and only if \(V(M_G)\) admits a \(\mathscr{A}\)–\(partition\).
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 \(-\lambda_n(M_G)=\lambda_1(G)\) if and only if \(M_G\) admits a \(\mathscr{B}\)–\(partition\).
Proof. Assume that \(G\) is \(\Delta\)-regular, let \(H^k_f(M_G)=(h_{uv})_{n\times n}\) and \(H^k_f(G)=A_f(G)=(a_{uv})_{n\times n}\), let \(X=(x_1,x_2,\ldots,x_n)^{T}\in R^n\) be a normalized eigenvector of \(A_f(G)\) corresponding to \(\lambda_1(G)\) and \(Y=(y_1,y_2,\ldots,y_n)^{T}\in C^n\) be a normalized eigenvector of \(H^k_f(M_G)\) corresponding to \(\lambda_n(M_G)\).
Assume that \(-\lambda_n(M_G)=\lambda_1(G)\), then by the similar proof it follows that \[\label{eq3.3}\tag{5} h_{u,v}\bar{y}_uy_v=-|h_{u,v}\bar{y}_uy_v|,\] for all edges \(uv\) 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|}=-\omega^{-1}=\omega^{\frac{k}{2}-1}\) if \(v\in N^+_{M_G}(v_0)\); \(\frac{y_v}{|y_v|}=-1=\omega^{\frac{k}{2}}\) if \(v\in N^0_{M_G}(v_0)\) and \(\frac{y_v}{|y_v|}=-\omega=\omega^{\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\{\omega^t,t\in Z\}\) for all \(v\in V(M_G)\). Let \(V_i=\{v\in V(M_G):\frac{y_v}{|y_v|}=\omega^t,\ where\ t\equiv i(mod\ k)\}\), where \(i\in\{1,2,\ldots,k\}\). it’s easy to check that \({V_1}\cup\dots\cup{V_k}\) forms a \(\mathscr{B}\)–\(partition\) of \(V(M_G)\).
Assume that \(M_G\) admits a \(\mathscr{B}\)–\(partition\) \({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^k_f(G)\cdot Z)_u=&f(\Delta,\Delta)(\sum_{v\in N^0_{M_G}(u)}{z_v}+\sum_{v\in N^+_{M_G}(u)}\omega{z_v}+\sum_{v\in N^-_{M_G}(u)}\omega^{-1}{z_v})\\ =&f(\Delta,\Delta)(\sum_{v\in N^0_{M_G}(u)}{x_v\omega^{i+\frac{k}{2}}}+\sum_{v\in N^+_{M_G}(u)}{\omega x_v\omega^{i+\frac{k}{2}-1}}\\ &+\sum_{v\in N^-_{M_G}(u)}{\omega^{-1}x_v\omega^{i+\frac{k}{2}+1}})\\ =&-f(\Delta,\Delta)\omega^{i}\sum_{v\in N_{G}(u)}{x_v}\\ =&-\lambda_1(G)\omega^{i}{x_u}=-\lambda_1z_u. \end{aligned}\] It follows that \(H^k_f(G)\cdot Z=-\lambda_1(G)Z\), so \(-\lambda_n(M_G)=\lambda_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 \(\rho^k_f(M_G)=\rho^k_f(G)\) if and only if \(V(G)\) admits a \(\mathscr{A}\)–\(partition\) or a \(\mathscr{B}\)–\(partition\).
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 \(\rho^k_f(H)<\rho^k_f(G)\).
Proof. We have following two claims.
Claim 1. For any proper, spanning and connected subgraph \(H\) of \(G\), \(\rho^k_f(H)<\rho^k_f(G)\).
Let \(y_1>0\), \(y_2>0\) be the Perron vector of \(\rho(G)\) and \(\rho(H)\), respectively. Note that \(A_f(G)-A_f(G')\geq0\) and \(A_f(G)-A_f(G')\neq0\) since \(f(x,y)\) is symmetric, not decreasing in \(x\) and \(H\) is a proper subgraph of \(G\). Then \[(\rho^k_f(G)-\rho^k_f(H)){y_1}'y_2={y_1}'(A_f(G)-A_f(H))y_2>0.\] It follows that \(\rho^k_f(G)>\rho^k_f(H)\).
Claim 2. For any proper, induced subgraph \(H\) of \(G\), \(\rho^k_f(H)<\rho^k_f(G)\).
Let \(y>0\), \(y_1>0\) be the Perron vector of \(\rho^k_f(G)\) and \(\rho^k_f(H)\), respectively. We can assume that \[A_f(G)= \left( \begin{matrix} A_f(H)+K & L\\ L' & M \end{matrix} \right)\] where \(K\geq0\) is symmetric. Then \[A_f(G) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right) = \left( \begin{matrix} (A_f(H)+K)y_1\\ L'y_1 \end{matrix} \right) = \left( \begin{matrix} \rho^k_f(H)y_1+Ky_1\\ L'y_1 \end{matrix} \right) \geq \rho^k_f(H) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right).\] If \[A_f(G) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right) = \rho^k_f(H) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right),\] then \(\left( \begin{matrix} y_1 \\ 0 \\ \end{matrix} \right)\geq0\) is a eigenvector of \(A_f(G)\) corresponding to \(\rho^k_f(G)\), which is contradict to Perron-Frobinius Theorem. So we have \(A_f(G) \left( \begin{matrix} y_1\\ 0\\ \end{matrix} \right) \geq \rho^k_f(H) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right)\) and \(A_f(G) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right) \neq \rho^k_f(H) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right)\). It follows that \((\rho^k_f(G)-\rho^k_f(H))y' \left( \begin{matrix} y_1\\ 0 \end{matrix} \right) = y'(A_f(G) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right) -\rho^k_f(H) \left( \begin{matrix} y_1\\ 0 \end{matrix} \right))\geq0\), so \(\rho^k_f(G)>\rho^k_f(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 \(\rho^k_f(H)<\rho^k_f(H')=\rho^k_f(G)\). If \(H'\neq G\), then by Claim 2 it follows that \(\rho^k_f(H)\leq\rho^k_f(H')<\rho^k_f(G)\). It completes the proof. ◻
Proof of Theorem 1. Note that if \(G\) is a \(\Delta\)-regular graph, then \(A_f(G)=f(\Delta,\Delta)A(G)\) and \(\rho^k_f(G)=f(\Delta,\Delta)\Delta(G)\). Since every graph with maximum degree \(\Delta\) must be a subgraph of a \(\Delta\)-regular graph, by Lemma 4 it follows that \(\rho^k_f(G)\leq f(\Delta,\Delta)\Delta(G)\) for all graphs \(G\) with maximum degree \(\Delta\), where equality holds if and only if \(G\) is \(\Delta\)-regular.
For a mixed graph \(M_G\) with maximum degree \(\Delta\), by Lemma 1 it follows that \(\rho^k_f(M_G)\leq f(\Delta,\Delta)\Delta(G)\), by Corollary 7,8 it follows that equality holds if and only if underlying graph \(G\) is \(\Delta(G)\)-regular and \(M_G\) admits a \(\mathscr{A}\)–\(partition\) or \(M_G\) admits a \(\mathscr{B}\)–\(partition\) when \(k\) is even. ◻
The work was partially supported by the National Natural Science Foundation of China under Grants 11771172, 12061039.
The authors declare no conflict of interest.