The concept of the integrated adjacency matrix for mixed graphs was first introduced in [9], where its spectral properties were analyzed in relation to the structural characteristics of the mixed graph. Building upon this foundation, this paper introduces the integrated Laplacian matrix, the integrated signless Laplacian matrix, and the normalized integrated Laplacian matrix for mixed graphs. We further explore how the spectra of these matrices relate to the structural properties of the mixed graph.
All graphs (directed graphs) considered in this paper may contain multiple loops and multiple edges (multiple directed loops and multiple arcs). A mixed graph generalizes both graphs and directed graphs. That is, a mixed graph may contain multiple loops, multiple edges, multiple directed loops and multiple arcs.
A fundamental problem in spectral theory of mixed graphs is assigning an appropriate matrix to a mixed graph and analyzing the mixed graph’s properties through the eigenvalues of that matrix. To achieve this, researchers have introduced various matrices that capture the spectral properties of mixed graphs.
In the literature, various matrices have been associated with mixed graphs under specific constraints. For mixed graphs without multiple edges, loops, multiple arcs, directed loops, or digons (pairs of arcs with the same endpoints but opposite directions), the Hermitian adjacency matrix was independently introduced by Liu and Li [10] and Guo and Mohar [8]. Additionally, several other matrices for this specific case have been explored, as seen in [1, 2, 3, 13, 14, 15, 16, 17, 18]. For mixed graphs without directed loops, the matrix in [5] was proposed. For mixed graphs without loops, directed loops, and digons, a matrix has been defined in [8]. In cases where an edge is treated as a digon, a matrix is defined in [12]. Lastly, for mixed graphs without digons, loops, and directed loops, a matrix is presented in [19].
There are, however, certain limitations: (i) the matrix defined in [2] is not symmetric, leading to eigenvalues that may include complex numbers; (ii) some matrices are only applicable to specific types of mixed graphs; and (iii) in some matrices, undirected edges are represented as digons, making it unclear from the matrix entries whether two vertices are connected by an edge or a digon, even when the index set of the matrix is provided. Furthermore, the entries of the matrix defined in [5] do not clearly convey the number of edges, loops, arcs, or the orientation of arcs. As a result, not all mixed graphs can be uniquely determined from their associated matrices.
To overcome these limitations, the integrated adjacency matrix for mixed graphs was introduced in [9]. Using this matrix, we introduce three additional matrices for mixed graphs in this paper: the integrated Laplacian matrix, the integrated signless Laplacian matrix, and the normalized integrated Laplacian matrix. We show that (i) each loopless mixed graph can be uniquely determined from its integrated Laplacian matrix, (ii) each mixed graph can be uniquely determined from its integrated signless Laplacian matrix, and (iii) each simple mixed graph can be uniquely determined from its normalized integrated Laplacian matrix.
Since these matrices are defined using the integrated adjacency matrix, we will refer to [9] as Part I in the following discussion. While we maintain the terminology and notation from Part I, some key definitions will be restated here for the reader’s convenience.
The rest of the paper is organized as follows:we begin by presenting some preliminary definitions and notations in Section 2, which serve as the foundation for subsequent discussions. In Subsection 2.1, we provide the definition of the integrated adjacency matrix for mixed graphs [9]. Additionally, we include relevant definitions and results associated with this matrix that are utilized in later sections.
In Sections 3, 4 and 5, we introduce the integrated Laplacian matrix, the integrated signless Laplacian matrix and the normalized integrated Laplacian matrix, respectively of a mixed graph and study the interplay between the eigenvalues of these matrices with the structural properties of mixed graphs
In this section, we present some notations and definitions of graphs, directed graphs and mixed graphs. A mixed graph \(G\) is an ordered triple \(G=(V_G,E_G,\vec{E}_G)\), where \(V_G\) is the vertex set, \(E_G\) is the edge set (a multiset of unordered pairs of vertices from \(V_G\)), and \(\vec{E}_G\) is the arc set (a multiset of ordered pairs of vertices from \(V_G\)).Let \(V_G=\{v_1,v_2,\ldots,v_n\}\). If there is an edge joining \(v_i\) and \(v_j\) in \(G\), we denote it as \(v_i \sim v_j\). To specify the number of edges joining \(v_i\) and \(v_j\), we write \(v_i\overset{k}{\sim} v_j\), provided there are \(k\) such edges in \(G\). If \(v_i\overset{l}{\sim} v_i\), this indicates that there are \(l\) loops at \(v_i\) in \(G\). If there is an arc from \(v_i\) to \(v_j\) in \(G\), we denote it as \(v_i \rightarrow v_j\). To indicate the number of arcs from \(v_i\) to \(v_j\), we write \(v_i\overset{k}{\rightarrow} v_j\), provided there are \(k\) such arcs in \(G\). If \(v_i\overset{l}{\rightarrow} v_i\), this means there are \(l\) directed loops at \(v_i\) in \(G\).Two vertices \(u\) and \(v\) in \(G\) are said to be adjacent if at least one of \(u\sim v\), \(u\rightarrow v\) or \(v\rightarrow u\) holds. A vertex \(u\) and an edge \(e\) in \(G\) are said to be incident if \(e=\{u,v\}\) for some \(v\) in \(G\). A vertex \(u\) and an arc \(a\) in \(G\) are said to be incident if \(a=(u,v)\) or \(a=(v,u)\) for some \(v\) in \(G\).
The undirected degree \(d(u)\) of a vertex \(u\) in \(G\) is the sum of the number of edges incident with \(u\) and the number of loops at \(u\), where each loop at \(u\) is counted twice. The out-degree \(d^+(u)\) of \(u\) in \(G\) is the number of arcs start at \(u\) (which includes the number of directed loops at \(u\)). The in-degree \(d^-(u)\) of \(u\) in \(G\) is the number of arcs end at \(u\) (which includes the number of directed loops at \(u\)). \(l(u)\) denotes the number of loops at \(u\). \(e(G),a(G)\) and \(l(G)\) denote the number of edges (excluding loops), arcs (including directed loops) and loops in \(G\), respectively. \(G\) is said to be \((r,s)\)-regular if \(d(u)=r\) and \(d^+(u)=s=d^-(u)\) for all \(u\in V_G\). A walk in \(G\) is a sequence \(W:v_{n_1},e_1,v_{n_2},e_2,…,e_{k-1},v_{n_k}\), where \(v_{n_i}\in V_G\), \(e_j=\{v_{n_j},v_{n_{j+1}}\}\) or \(e_j=(v_{n_j},v_{n_{j+1}})\) or \(e_j=(v_{n_{j+1}},v_{n_j})\) for \(i=1,2,\ldots,k\), \(j=1,2,\ldots,k-1\). In this case, we say that \(W\) is a walk from \(v_{n_1}\) to \(v_{n_k}\). The total number of edges and arcs in \(W\) (with each repeated edge or arc counted as many times as it appears), i.e., \(k-1\) is said to be the length of \(W\). The walk \(W\) is said to be closed if \(v_1=v_k\). A mixed graph \(G_1\) is said to be a submixed graph of \(G\) if \(V_{G_1}\subseteq V_G\), \(E_{G_1}\subseteq E_G\) and \(\vec{E}_{G_1}\subseteq \vec{E}_G\). A submixed graph \(G_1\) of \(G\) is said to be a spanning submixed graph of \(G\) if \(V_{G_1}=V_G\).
A mixed graph \(G=(V_G,E_G,\vec{E}_G)\) is said to be a graph if \(\vec{E}_G=\emptyset\). In this case, it is simply denoted as \(G=(V_G,E_G)\). Let \(G=(V_G,E_G)\) with \(V_G=\{v_1,v_2,\ldots,v_n\}\). The adjacency matrix of \(G\), denoted by \(A(G)\), is defined as follows: The rows and the columns of \(A(G)\) are indexed by the vertices of \(G\), and for \(i,j=1,2,\ldots,n\), \[\text{the }(v_i,v_j)\text{-th entry of } A(G) =\begin{cases} k, & \text{if}~i\neq j\text{ and} ~v_i\overset{k}{\sim} v_j;\\ 2l, & \text{if}~i=j\text{ and} ~v_i\overset{l}{\sim} v_i;\\ 0, & \text{otherwise}. \end{cases}\] The degree matrix of \(G\), denoted by \(D(G)\), is defined as \(D(G)=diag(d(v_1),d(v_2),\ldots,d(v_n))\). The Laplacian matrix of \(G\), denoted by \(L(G)\), is defined as \(L(G)=D(G)+A(G)\). The signless Laplacian matrix of \(G\), denoted by \(Q(G)\), is defined as \(Q(G)=D(G)+A(G)\). The normalized Laplacian matrix of \(G\), denoted by \(\widehat{L}(G)\), is defined as \(n\times n\) matrix whose rows and columns are indexed by \(V_G\) and \[\text{the }(v_i,v_j)\text{-th entry of }\widehat{L}(G) =\begin{cases} 1-\frac{2l(v_i)}{d(v_i)}, & \text{if}~i= j\text{ and } d(v_i)\neq 0;\\ -\frac{k}{\sqrt{d(v_{i})d(v_{j})}}, & \text{if}~i\neq j\text{ and} ~v_i\overset{k}{\sim} v_i;\\ 0, & \text{otherwise}. \end{cases}\]
In particular, if \(G\) has no isolated vertices, we have \(\widehat{L}(G)=D(G)^{-\frac{1}{2}}L(G)D(G)^{-\frac{1}{2}}\).
Since \(A(G),L(G),Q(G)\) and \(\widehat{L}(G)\) are real symmetric matrices, we denote their eigenvalues respectively as \(\lambda_1(G)\geq\lambda_2(G)\geq\cdots\geq\lambda_{n}(G)\), \(\nu_1(G)\geq\nu_2(G)\geq\cdots\geq\nu_{n}(G)\), \(\xi_1(G)\geq\xi_2(G)\geq\cdots\geq\xi_{n}(G)\) and \(\hat{\nu}_1(G)\geq\hat{\nu}_2(G)\geq\cdots\geq\hat{\nu}_{n}(G)\). The path graph and the cycle graph on \(n\) vertices are denoted by \(P_n\) and \(C_n\), respectively. The disjoint union of \(m\) copies of a graph \(G\) is denoted by \(mG\). For \(S\subseteq V_G\), volume of \(S\) denoted by \(\text{vol}(S)\) which is defined as \(\text{vol}(S)=\sum\limits_{v\in S} d(v)\). If \(G\) is connected and \(u,v\in V_G\) \((u\neq v)\), then the distance \(d(u,v)\) between \(u\) and \(v\) is the length of a shortest path between \(u\) and \(v\) in \(G\) and \(d(u,u)=0\). If \(G\) is connected and \(X,Y\subseteq V_G\), then the distance between \(X\) and \(Y\), denoted by \(d(X,Y)\), defined as \(d(X,Y)=\min\{d(u,v)\mid u\in X\text{ and }v\in Y\}\).
A mixed graph \(G=(V_G,E_G,\vec{E}_G)\) is said to be a directed graph if \(E_G=\emptyset\). In this case, it is simply denoted as \(G=(V_G,\vec{E}_G)\). Let \(G=(V_G,\vec{E}_G)\) with \(V_G=\{v_1,v_2,\ldots,v_n\}\). The adjacency matrix of \(G\), denoted by \(\vec{A}(G)\), is defined as follows [4]: The rows and the columns of \(\vec{A}(G)\) are indexed by the vertices of \(G\), and for \(i,j=1,2,\ldots,n\), \[\text{the }(v_i,v_j)\text{-th entry of } \vec{A}(G) =\begin{cases} k, & \text{if}~v_i\overset{k}{\rightarrow} v_j;\\ 0, & \text{otherwise}. \end{cases}\]
A simple graph (resp. simple directed graph) is a graph (resp. directed graph) which has no loops (resp. directed loops) and no multiple edges (resp. multiple arcs). A simple mixed graph is a mixed graph which has no loops, directed loops, multiple edges or multiple arcs. A complete graph is a simple graph in which every pair of distinct vertices is adjacent. A complete directed graph is a simple directed graph in which, for every pair of distinct vertices \(u\) and \(v\), both \(u\rightarrow v\) and \(v\rightarrow u\) exist. A complete mixed graph is a simple mixed graph in which, for every pair of distinct vertices \(u\) and \(v\), the following relationship hold: \(u\sim v\), \(u\rightarrow v\) and \(v\rightarrow u\). We denote the complete graph, the complete directed graph and the complete mixed graph on \(n\) vertices as \(K_n\), \(K^D_n\) and \(K^M_n\), respectively. An oriented graph of a graph \(G\) is the directed graph obtained from \(G\) by replacing each edge in \(G\) by an arc.
An independent set in a mixed graph \(G\) is a set of vertices of \(G\) in which no two vertices are adjacent. A \(k\)-partite graph (or \(k\)-partite directed graph, or \(k\)-partite mixed graph, resp.) is a graph (or directed graph, or mixed graph, resp.) whose vertices can be partitioned into \(k\) independent sets. If \(k=2\), then we say that it is a bipartite graph (or bipartite directed graph, or bipartite mixed graph, resp.). Let \(G\) be a \(k\)-partite graph with vertex partition \(V_G=V_1\overset{.}{\cup}V_2\overset{.}{\cup}\cdots\overset{.}{\cup}V_k\) and \(|V_i|=n_i\) for \(i=1,2,\ldots,k\). Then \(G\) is said to be complete \(k\)-partite if \(u\sim v\) for every \(u\in V_i\) and \(v\in V_j\) with \(i\neq j\). We denote it by \(K_{n_1,n_2,\ldots,n_k}\). In particular, \(K_{k(m)}\) is used when \(n_1=n_2=\cdots=n_k=m\).
Let \(G\) be a \(k\)-partite directed graph with vertex partition \(V_G=V_1\overset{.}{\cup}V_2\overset{.}{\cup}\ldots\overset{.}{\cup}V_k\) and \(|V_i|=n_i\) for \(i=1,2,\ldots,k\). Then \(G\) is said to be complete \(k\)-partite if \(u\rightarrow v\) and \(v\rightarrow u\) for every \(u\in V_i\) and \(v\in V_j\) with \(i\neq j\). We denote it by \(K^D_{n_1,n_2,\ldots,n_k}\). In particular, \(K^D_{k(m)}\) is used when \(n_1=n_2=\cdots=n_k=m\).
Let \(G\) be a \(k\)-partite mixed graph with vertex partition \(V_G=V_1\overset{.}{\cup}V_2\overset{.}{\cup}\ldots\overset{.}{\cup}V_k\) and \(|V_i|=n_i\) for \(i=1,2,\ldots,k\). Then \(G\) is said to be complete \(k\)-partite if \(u\sim v\), \(u\rightarrow v\), and \(v\rightarrow u\) for every \(u\in V_i\) and \(v\in V_j\) with \(i\neq j\). We denote it by \(K^M_{n_1,n_2,\ldots,n_k}\). In particular, \(K^M_{k(m)}\) is used when \(n_1=n_2=\cdots=n_k=m\).
Throughout this paper, \(I_n\) denotes the \(n\times n\) identity matrix, \(J_{n\times m}\) denotes the all-ones \(n\times m\) matrix, \(\mathbf{0}_{n\times m}\) denotes the all-zero \(n\times m\) matrix, and \(\mathbf{1}_n\) denotes the all-ones matrix of size \(n\times 1\). These matrices are simply referred to as \(I\), \(J\), \(\mathbf{0}\), and \(\mathbf{1}\), when their sizes are evident from the context. The characteristic polynomial of a square matrix \(M\) is denoted as \(P_M(x)\), and the spectrum of \(M\) is the multi-set of all the eigenvalues of \(M\). For an \(n \times n\) real matrix \(M\) with real eigenvalues, we denote its eigenvalues by \(\lambda_i(M)\) for \(i = 1,2,\dots,n\), arranged in non-increasing order as \(\lambda_1(M) \geq \lambda_2(M) \geq \dots \geq \lambda_n(M)\). If \(\lambda\) is an eigenvalue of \(M\) with multiplicity \(m\), then we write it as \(\lambda^{(m)}\). Let \(M=[m_{ij}]\) and \(N\) be matrices of order \(m\times n\) and \(p\times q\), respectively. The Kronecker product of \(M\) and \(N\), denoted by \(M\otimes N\), is the \(mp\times nq\) block matrix \([m_{ij}N]\).
In the rest of the paper we consider only mixed graphs having finite number of vertices.
Let \(G\) be a mixed graph. The undirected part (resp. the directed part) of \(G\) is the spanning submixed graph of \(G\) whose edge set is \(E_G\) and arc set is \(\emptyset\) (resp. edge set is \(\emptyset\) and arc set is \(\vec{E}_G\)). The undirected part and the directed part of \(G\) are denoted as \(G_u\) and \(G_d\), respectively. Clearly, every mixed graph can be viewed as the union of its undirected part and directed part.
Let \(G\) be a mixed graph with
\(V_G=\{v_1,v_2,\ldots,v_n\}\). For
\(i=1,2,\ldots,n\), let \(v'_i\) and \(v''_i\) be two copies of \(v_i\). The integrated adjacency
matrix of \(G\), denoted by \(\mathcal{I}(G)\), is defined as the square
matrix of order \(2n\) whose rows and
columns are indexed by the elements of the set \(\{v'_1,v'_2,\ldots,v'_n,v''_1,v''_2,\ldots,v''_n\}\).
For \(i,j=1,2,\ldots,n\),
the \((v'_i,v'_j)\)-th entry of
\(\mathcal{I}(G)=\text{the
}(v''_i,v''_j)\)-th entry of \(\mathcal{I}(G)=\begin{cases}
2\alpha, & \text{if}~i= j\text{ and}~
v_{i}\overset{\alpha}{\sim} v_{j};\\
\beta, & \text{if}~i\neq j\text{ and}~
v_{i}\overset{\beta}{\sim} v_{j};\\
0, & \text{otherwise};
\end{cases}\)
the \((v'_i,v''_j)\)-th
entry of \(\mathcal{I}(G)=\text{the
}(v''_j,v'_i)\)-th entry of \(\mathcal{I}(G)=\begin{cases}
\gamma, & \text{if}~ v_{i}\overset{\gamma}{\rightarrow} v_{j};\\
0, & \text{otherwise}.
\end{cases}\)
The spectrum of \(\mathcal{I}(G)\) is called the \(\mathcal{I}\)–spectrum of \(G\). The eigenvalues of \(\mathcal{I}(G)\) are called the \(\mathcal{I}\)–eigenvalues of \(G\). Since \(\mathcal{I}(G)\) is real symmetric, it’s eigenvalues are real and so they can be arranged in a non-increasing order. We denote them as \( {\lambda}_1(G), {\lambda}_2(G),\ldots, {\lambda}_{2n}(G)\) and without loss of generality we assume that \( {\lambda}_1(G)\geq {\lambda}_2(G)\geq\cdots\geq {\lambda}_{2n}(G)\).
By arranging the rows and columns of \(\mathcal{I}(G)\) in the order \(v'_1,v'_2,\ldots,v'_n,v''_1,v''_2,\ldots,v''_n\), \(\mathcal{I}(G)\) can be viewed as a \(2\times 2\) block matrix \[\label{adjmatrix block} \mathcal{I}(G)=\begin{bmatrix} A(G_u) & \vec{A}(G_d)\\ \vec{A}(G_d)^T & A(G_u) \end{bmatrix}. \tag{1}\]
The associated graph of \(G\), denoted by \(G^A\), is a graph, which is defined as follows. Let \(V_{G^A}=\{v'_1,v'_2,\ldots,v'_n,v''_1,v''_2,\ldots,v''_n\}\). Make adjacency among the vertices of \(G^A\) using the following rules: For \(i,j=1,2,\ldots,n\),
(i) \(v'_i\overset{k}{\sim} v'_j\) and \(v''_i\overset{k}{\sim} v''_j\) in \(G^A\) if and only if \(v_i\overset{k}{\sim} v_j\) in \(G\);
(ii) \(v'_i\overset{k}{\sim} v''_j\) in \(G^A\) if and only if \(v_i\overset{k}{\rightarrow} v_j\) in \(G\).
It is clear that \(A(G^A)=\mathcal{I}(G)\). So the \(\mathcal{I}\)-spectrum of \(G\) is the same as the spectrum of \(A(G^A)\). From the construction of \(G^A\) it is easy to observe that if \(G\) is simple, then \(G^A\) is a simple graph.
A mixed graph \(G\) is said to be \(r\)-regular if \(d^+(u)=d^-(u)\) and \(d(u)+d^+(u)=r\) for all \(u\in V_G\). It is easy to verify that \(G\) is \(r\)-regular if and only if \(r\) is an eigenvalue of \(\mathcal{I}(G)\) with corresponding eigenvector \(\boldsymbol{1}_{2n}\).
A mixed graph \(G\) is said to have the associated-bipartite property (shortly, AB property), if it has no cycle of odd length and no alternating cycle of odd length with even number of arcs.
Let \(G\) be a mixed graph with at least one arc. A walk in \(G\) is said to be an alternating walk if starting from the first arc it’s subsequent arcs are in alternating directions irrespective of the edges. An alternating walk \(W\) in \(G\) is said to be an alternating path if it satisfies the following conditions:
(i) Each vertex in \(W\) occurs at most twice.
(ii) If a vertex in \(W\) occurs twice, then in between them there must be an odd number of arcs.
(iii) Each edge in \(W\) occurs at most twice.
(iv) If an edge in \(W\) occurs twice, then in between them there must be an odd number of arcs.
(v) Each arc in \(W\) occurs exactly once.
An alternating walk in \(G\) is said to be an alternating cycle if it satisfies the above conditions (iii)-(v) and it’s starting vertex and it’s ending vertex are the same.
A submixed graph \(G'\) of a mixed graph \(G\) having at least one arc is said to be a special submixed graph of \(G\), if it satisfies the following conditions.
(i) Any two distinct vertices of \(G'\) are joined by an alternating walk;
(ii) If a component \(H\) of \(G'_u\) has at least one vertex having in-arc in \(G'\) and at least one vertex having out-arc in \(G'\), then for each vertex \(v\) of \(H\), there exists a closed alternating walk in \(G'\) which starts and ends at \(v\) and containing odd number of arcs.
A submixed graph \(G'\) of a mixed graph \(G\) is said to be a mixed component of \(G\) if it satisfies one of the following three conditions.
(i) \(G'\) is a component of \(G_u\) and each vertex of \(G'\) has out-degree zero in \(G\).
(ii) \(G'\) is a component of \(G_u\) and each vertex of \(G'\) has in-degree zero in \(G\).
(iii) \(G'\) is a maximal special submixed graph of \(G\).
It is shown in [9, Theorem 6.1. ] that there is a 1-1 correspondence between the multiset of all mixed components of a mixed graph \(G\) and the set of all components of \(G^A\). The unique component of \(G^A\) associated to each mixed component \(H\) of \(G\), which we henceforth refer to as the corresponding component of \(H\).
Let \(G\) be a mixed graph and let \(H\) be a mixed component of \(G\). Let \(B_H=\{v\in V_H\mid \text{there exits an alternating path in }H\text{ which contains }v\text{ twice}\}\) and \(C_H=\{e\in E_H\mid \text{there exits an alternating path in }H\text{ which contains }e\text{ twice}\}\). \(H\) is said to have the associated path property (shortly AP property) if \(H\) is either a path or \(H\) has an alternating path which contains (i) each vertex \(v\) of \(H\) exactly twice if \(v\in B_H\), otherwise exactly once, (ii) all the arcs of \(H\), and (iii) each edge \(e\) of \(H\) exactly twice if \(e\in C_H\), otherwise exactly once.
A mixed graph \(G\) is said to be uniconnected if \(G\) has exactly one mixed component.
Lemma 2.1. ([9, Lemma 6.2]) A mixed graph \(G\) is uniconnected if and only if \(G^A\) is a connected graph.
In this section, we introduce the integrated Laplacian matrix of a mixed graph, explore its properties, and examine the connection between its eigenvalues and the structural characteristics of the mixed graph.
Definition 3.1. Let \(G\) be a mixed graph with \(V_G=\{v_1,v_2,\ldots,v_n\}\). For \(i=1,2,\ldots,n\), let \(v'_i\) and \(v''_i\) be two copies of \(v_i\). We define the integrated degree matrix of \(G\), denoted by \(\mathcal{I}^D(G)\), as the diagonal matrix of order \(2n\), with rows and columns are indexed by the elements of the set \(\{v'_1,v'_2,\ldots,v'_n,v''_1,v''_2,\ldots,v''_n\}\). For \(i=1,2,\ldots,n\), the \((v'_i,v'_i)\)-th entry of \(\mathcal{I}^D(G)= d(v_i)+d^{+}(v_i)\), and the \((v''_i,v''_i)\)-th entry of \(\mathcal{I}^D(G)= d(v_i)+d^{-}(v_i)\).
Definition 3.2. The integrated Laplacian matrix of a mixed graph \(G\), denoted by \(\mathcal{I}^L(G)\), is defined as \(\mathcal{I}^L(G)=\mathcal{I}^D(G)-\mathcal{I}(G)\).
Notice that each loopless mixed graph can be determined from its integrated Laplacian matrix. The eigenvalues of \(\mathcal{I}^L(G)\) are called the \(\mathcal{I}^L\)–eigenvalues of \(G\). These eigenvalues are denoted by \( {\nu}_i(G)\) for \(i=1,2,\ldots,2n\). Since \(\mathcal{I}^L(G)\) is real symmetric, its eigenvalues can be arranged, without loss of generality, as \( {\nu}_1(G)\geq {\nu}_2(G)\geq\cdots\geq {\nu}_{2n}(G)\).The spectrum of \(\mathcal{I}^L(G)\) is called the \(\mathcal{I}^L\)–spectrum of \(G\). Notice that \(\mathcal{I}^D(G)=D(G^A)\) and therefore \(\mathcal{I}^L(G)=L(G^A)\). This implies that the \(\mathcal{I}^L\)-spectrum of \(G\) is identical to the spectrum of \(L(G^A)\).
Using (1), \(\mathcal{I}^L(G)\) can be viewed as a \(2\times 2\) block matrix \[\label{laplacianblock} \mathcal{I}^L(G)=\begin{bmatrix} L(G_u)+D_1 & -\vec{A}(G_d)\\ -\vec{A}(G_d)^T & L(G_u)+D_2 \end{bmatrix}, \tag{2}\] where \(D_1=diag(d^+(v_1),d^+(v_2),\ldots,d^+(v_n))\) and \(D_2=diag(d^-(v_1),d^-(v_2),\ldots,d^-(v_n))\).
We start with the following.
Observation 3.3. If \(G\) is a graph, then \(\mathcal{I}^L(G)=I_2\otimes L(G)\). The eigenvalues of \(\mathcal{I}^L(G)\) are identical to those of \(L(G)\), but each appears with twice their multiplicities.
Theorem 3.4. Let \(G\) be a simple mixed graph with \(V_G=\{v_1,v_2,\ldots,v_n\}\). Then the following assertions hold:
(i) \(\mathcal{I}^L(G)\) is positive semi-definite.
(ii) The rank of \(\mathcal{I}^L(G)\) equals \(2n-k\), where \(k\) is the number of mixed components of \(G\).
(iii) The row sum and the column sum of \(\mathcal{I}^L(G)\) are zero, so zero is an eigenvalue of \(\mathcal{I}^L(G)\).
(iv) \(\mathcal{I}^L(G)\) is a singular matrix.
(v) The cofactor matrix of \(\mathcal{I}^L(G)\) has identical entries throughout.
Proof. Part (iii) follows directly from the definition of \(\mathcal{I}^L(G)\), and part (iv) follows from part (iii). Since \(\mathcal{I}^L(G)=L(G^A)\), parts (i) and (v) follow directly from the properties of the Laplacian matrix of a simple graph (c.f. [4, Lemma 4.3]). Finally, part (ii) follows from [9, Corollary 6.1]: “The number of mixed components of a mixed graph \(G\) is equal to the number of components of \(G^A\)”. ◻
Theorem 3.5. For a mixed graph \(G\) on \(n\) vertices, \(\sum\limits_{i=1}^{2n} {\nu}_i(G)=4e(G)+2a(G)\).
Proof. “‘latex Since \(\sum\limits_{i=1}^{2n} {\nu}_i(G) =\operatorname{tr}(\mathcal{I}^L(G)) =\operatorname{tr}(\mathcal{I}^D(G)-\mathcal{I}(G)) =\operatorname{tr}(\mathcal{I}^D(G))-\operatorname{tr}(\mathcal{I}(G))\), we have \[\begin{aligned} \label{laplaciansum} \sum\limits_{i=1}^{2n} {\nu}_i(G) =&\sum\limits_{i=1}^{n}[d^{+}(v_i)+d(v_i)] +\sum\limits_{i=n+1}^{2n}[d^{-}(v_{i-n})+d(v_{i-n})] -\sum\limits_{i=1}^{n}4l(v_i)\nonumber\\ =&\sum\limits_{i=1}^{n}[2d(v_i)+d^{+}(v_i)+d^{-}(v_i)]-4l(G). \end{aligned} \tag{3}\]
By substituting the values \(\sum\limits_{i=1}^{n}d(v_i)=2e(G)+2l(G)\), and \(\sum\limits_{i=1}^{n}d^+(v_i)=a(G)=\sum\limits_{i=1}^{n}d^-(v_i)\) (c.f. [9, Proposition 4.1]) in (3), we obtain the result. ◻
Let \(G\) be a mixed graph. For \(a\in \vec{E}_G\), \(G-a\) denotes the mixed graph obtained by deleting the arc \(a\) from \(G\).
Theorem 3.6. Let \(G\) be a simple mixed graph on \(n\) vertices. Let \(H=G-a\) for some \(a\in \vec{E}_G\). Then \(0= {\nu}_{2n}(H)= {\nu}_{2n}(G)\leq {\nu}_{2n-1}(H)\leq {\nu}_{2n-1}(G)\leq\cdots\leq {\nu}_{2}(G)\leq {\nu}_{1}(H)\leq {\nu}_{1}(G)\).
Proof. Notice that \(H^A=G^A-e\), where \(e\) is the edge of \(G^A\) corresponding to the arc \(a\) in \(G\). Since \( {\nu}_i(G)=\nu_i(G^A)\) and \( {\nu}_i(H)=\nu_i(H^A)\) for \(i=1,2,\ldots,2n\), the result follows from an interlacing relation between the Laplacian spectra of a graph and its subgraph (c.f. [7, Theorem 7.1.5.]). ◻
Theorem 3.7. The Laplacian spectrum of an \(r\)-regular mixed graph \(G\) on \(n\) vertices is given by \(0=r- {\lambda}_1(G)\leq r- {\lambda}_2(G)\leq\cdots\leq r- {\lambda}_{2n}(G)\).
Proof. Since \(G\) is \(r\)-regular, we have \(\mathcal{I}^L(G)=rI_{2n}-\mathcal{I}(G)\) and \( {\lambda}_1(G)=r\). Hence the result follows. ◻
Theorem 3.8.
(i) The \(\mathcal{I}^L\)-spectrum of \(K^M_{k(m)}\) is \(0^{(1)}\), \((2mk)^{(k-1)}\), \((2mk-2m)^{(2mk-k)}\).
(ii) The \(\mathcal{I}^L\)-spectrum of \(K^D_{k(m)}\) is \((2mk-2m)^{(1)}\), \(0^{(1)}\), \((mk)^{(k-1)}\), \((mk-2m)^{(k-1)}\), \((mk-m)^{(2km-2k)}\).
Proof. It is clear that \(K^M_{k(m)}\) and \(K^D_{k(m)}\) are \(2m(k-1)\) and \(m(k-1)\)-regular, respectively. Therefore, the results follow from Theorem 3.7 and [9, Theorem 5.3]: “The \(\mathcal{I}\)-spectrum of \(K^M_{k(m)}\) is \((2mk-2m)^{(1)}\), \((-2m)^{(k-1)}\), \(0^{(2mk-k)}\), and the \(\mathcal{I}\)-spectrum of \(K^D_{k(m)}\) is \((mk-m)^{(1)}\), \((m-mk)^{(1)}\), \(m^{(k-1)}\), \((-m)^{(k-1)}\), and \(0^{(2km-2k)}\)”. ◻
Corollary 3.9. (i) The \(\mathcal{I}^L\)-spectrum of \(K^M_n\) is \(0^{(1)}\), \(2n^{(n-1)}\), \((2n-2)^{(n)}\).
(ii) The \(\mathcal{I}^L\)-spectrum of \(K^D_n\) is \((2n-2)^{(1)}\), \(0^{(1)}\), \(n^{(n-1)}\), \((n-2)^{(n-1)}\).
Proof. By taking \(k=n\) and \(m=1\) in Theorem 3.8, the result follows. ◻
Theorem 3.10.
(i) If \(G\) is the oriented graph of \(P_n~(n\geq2)\) with all its arcs have the same direction, then the \(\mathcal{I}^L\)-spectrum of \(G\) is \(2^{(n-1)}\), \(0^{(n+1)}\).
(ii) If \(G\) is the oriented graph of \(C_n~(n\geq3)\) with all its arcs have the same direction, then the \(\mathcal{I}^L\)-spectrum of \(G\) is \(2^{(n)}\), \(0^{(n)}\).
(iii) If \(G\) is the oriented graph of \(C_n~(n\geq4)\) with all its arcs have the alternating direction, then the \(\mathcal{I}^L\)-spectrum of \(G\) is \(0^{(n)}\), and \((2-2\cos\frac{2\pi k}{n})^{(1)}\) for \(k=1,2,\ldots,n\).
Proof. (i) Here \(G^A\) is the union of \((n-1)K_2\), and two isolated vertices. Therefore, the spectrum of \(L(G^A)\) is \(2^{(n-1)}\), \(0^{(n+1)}\).
(ii) Here \(G^A=nK_2\) and so the spectrum of \(L(G^A)\) is \(2^{(n)}\), \(0^{(n)}\).
(iii) Here \(G^A\) is the union of \(C_n\), and \(n\) isolated vertices. So the spectrum of \(L(G^A)\) is \(0^{(n)}\), and \((2-2\cos\frac{2\pi k}{n})^{(1)}\) for \(k=1,2,\ldots,n\).
Since the spectrum of \(\mathcal{I}^L(G)\) and \(L(G^A)\) are the same, we get the results. ◻
Theorem 3.11. Let \(G\) be a uniconnected mixed graph on \(n\) vertices. If \(G\) has an alternating cycle of length \(2n\) that includes all vertices, all arcs, and each edge of \(G\) exactly twice, then the \(\mathcal{I}^L\)-spectrum of \(G\) is \(2-2\cos\frac{\pi k}{n}\) for \(k=1,2,\ldots,2n\).
Proof. Notice that \(G^A\) is \(2\)-regular. Therefore, by [9, Lemma 6.1]: “Let \(G\) be a mixed graph. Then \(G\) is \(r\)-regular if and only if \(G^A\) is \(r\)-regular”, it follows that \(G\) is also \(2\)-regular. Under the assumptions given, it is shown in [9, Theorem 6.3(iii)] that the \(\mathcal{I}\)-spectrum of \(G\) is \(2\cos\frac{\pi k}{n}\) for \(k=1,2,\ldots,2n\). Consequently, the result follows directly from Theorem 3.7. ◻
Theorem 3.12. For a simple mixed graph \(G\) on \(n\) vertices, \[ {\nu}_{2n-1}(G)\leq\frac{4e(G)+2a(G)}{2n-1}\leq {\nu}_{1}(G).\]
Proof. Since \( {\nu}_{2n}(G)=0\), it follows from Theorem 3.5 that \(\sum\limits_{i=1}^{2n-1} {\nu}_i(G)=4e(G)+2a(G)\). Additionally, since \( {\nu}_{2n-1}(G)\leq {\nu}_i(G)\leq {\nu}_1(G)\) for \(i=1,2,\ldots,2n-1\), we have the inequality \((2n-1) {\nu}_{2n-1}(G)\leq\sum\limits_{i=1}^{2n-1} {\nu}_i(G)\leq(2n-1) {\nu}_1(G)\). Thus, the result follows. ◻
Let \(G\) be a mixed graph with \(V_G=\{v_1,v_2,\ldots,v_n\}\). Consider the multiset \[\{x\mid x=d(v_i)+d^+(v_i) ~\text{or}~ x=d(v_i)+d^-(v_i) ~\text{for}~i=1,2,\ldots,n\}\] If we arrange the elements of this multiset in decreasing order, denoted as \[d_1\geq d_2\geq \cdots\geq d_{2n},\] then we have the following:
Theorem 3.13. For a simple mixed graph \(G\) on \(n\) vertices, \(\sum\limits_{i=1}^{k} {\nu}_i(G)\geq\sum\limits_{i=1}^{k}d_i\) for \(k=1,2,\ldots,2n\) with equality hold when \(k=2n\).
Proof. Notice that \(d_1\geq d_2\geq \cdots\geq d_{2n}\) is the decreasing sequence of the vertex degrees of \(G^A\). Since \( {\nu}_i(G)=\nu_i(G^A)\) for \(i=1,2,\ldots,2n\), the result follows from [7, Theorem 7.1.3] which states: ◻
Theorem 3.14. Let \(G\) be a simple mixed graph on \(n\) vertices. Then \[ {\nu}_1(G)\leq 2\nu_1(G_u)+\underset{u\in V_G}{\max}~d^+(u)+\underset{u\in V_G}{\max}~d^-(u).\]
Proof. We consider \(\mathcal{I}^L(G)\) as mentioned in (2). Setting \(M=\mathcal{I}^L(G)\), \(P=L(G_u)+D_1\), \(Q=-\vec{A}(G_d)\) and \(R=L(G_u)+D_2\) in [7, Proposition 1.3.16], we obtain \( {\nu}_1(G)+ {\nu}_{2n}(G)\leq \lambda_1(L(G_u)+D_1)+\lambda_1(L(G_u)+D_2)\). Using [4, Lemma 3.19]: “If \(A\) and \(B\) are symmetric \(n\times n\) matrices with real entries, then \(\lambda_1(A+B)\leq\lambda_1(A)+\lambda_1(B)\)”, we derive \[\displaystyle\lambda_1(L(G_u)+D_1)\leq \nu_1(L(G_u))+\underset{i=1}{\overset{n}{\max}}~d^+(v_i),\] and \[\displaystyle\lambda_1(L(G_u)+D_2)\leq \nu_1(L(G_u))+\underset{i=1}{\overset{n}{\max}}~d^-(v_i).\]
Since \( {\nu}_{2n}(G)=0\), the result follows. ◻
Theorem 3.15. Let \(G\) be a mixed graph on \(n\) vertices. Then \[ {\nu}_{2n-1}(G)\leq\displaystyle\frac{2a(G)}{n}\leq {\nu}_1(G).\]
Proof. We consider \(\mathcal{I}^L(G)\) as mentioned in (2). The sums of the entries of \(L(G_u)+D_1\), \(L(G_u)+D_2\) and \(-\vec{A}(G_d)\) are \(a(G)\), \(a(G)\) and \(-a(G)\), respectively. From [7, Corollary 1.3.13], the eigenvalues \(\frac{2}{n}a(G)\) and \(0\) of the matrix \(\frac{1}{n}a(G)(2I_2-J_2)\) interlace the eigenvalues of \(\mathcal{I}^L(G)\). This completes the proof. ◻
If \(G_1\) and \(G_2\) are two simple mixed graphs, then the union of \(G_1\) and \(G_2\), denoted by \(G_1\cup G_2\), is the mixed graph with \(V_{G_1\cup G_2}=V_{G_1}\cup V_{G_2}\), \(E_{G_1\cup G_2}=E_{G_1}\cup E_{G_2}\), and \(\vec{E}_{G_1\cup G_2}=\vec{E}_{G_1}\cup \vec{E}_{G_2}\).
Definition 3.16. A simple mixed graph \(G\) is said to be a factorization of its two spanning submixed graphs \(G_1\) and \(G_2\) if \(G = G_1 \cup G_2\), with \(E_{G_1} \cap E_{G_2} = \emptyset\) and \(\vec{E}_{G_1} \cap \vec{E}_{G_2} = \emptyset\). This is denoted as \(G = G_1 \oplus G_2\).
Theorem 3.17. If \(G=G_1\oplus G_2\) is a factorization of a simple mixed graph \(G\), then
(i) \( {\nu}_{2n-1}(G)\geq {\nu}_{2n-1}(G_1)+ {\nu}_{2n-1}(G_2)\),
(ii) \(\max\{ {\nu}_{1}(G_1), {\nu}_{1}(G_2)\}\leq {\nu}_{1}(G)\leq {\nu}_{1}(G_1)+ {\nu}_{1}(G_2)\).
Proof. Since \(G=G_1\oplus G_2\), we have \(G^A=G_1^A\oplus G_2^A\). Since \( {\nu}_{i}(G)=\nu_{i}(G^A)\), \( {\nu}_{i}(G_1)=\nu_{i}(G_1^A)\) and \( {\nu}_{i}(G_2)=\nu_{i}(G_2^A)\) for \(i=1,2n-1\), the proof follows from [11, Theorem 3.3], which states: “Let \(G=G_1\oplus G_2\) be a factorization of a graph \(G\). Then \(\nu_{n-1}(G)\geq\nu_{n-1}(G_1)+\nu_{n-1}(G_2)\) and \(\max\{\nu_{1}(G_1),\nu_{1}(G_2)\}\leq\nu_{1}(G)\leq\nu_{1}(G_1)+\nu_{1}(G_2)\)”. ◻
Corollary 3.18. Let \(G\) be a simple mixed graph on \(n\) vertices. If \(H\) is a spanning submixed graph of \(G\), then \( {\nu}_{2n-1}(H)\leq {\nu}_{2n-1}(G)\) and \( {\nu}_{1}(H)\leq {\nu}_{1}(G)\).
Proof. Let \(G=H\oplus H'\), where \(H'\) is the spanning submixed graph of \(G\) with \(E_{H'}=E_G\setminus E_H\) and \(\vec{E}_{H'}=\vec{E}_G\setminus\vec{E}_H\). Then by Theorem 3.17, we have \( {\nu}_{2n-1}(H)+ {\nu}_{2n-1}(H')\leq {\nu}_{2n-1}(G)\) and \(\max\{ {\nu}_{1}(H), {\nu}_{1}(H')\}\leq {\nu}_{1}(G)\). Since \( {\nu}_{2n-1}(H)\leq {\nu}_{2n-1}(H)+ {\nu}_{2n-1}(H')\) and \( {\nu}_{1}(H)\leq\max\{ {\nu}_{1}(H), {\nu}_{1}(H')\}\), the result follows. ◻
Corollary 3.19. If \(G_1\) and \(G_2\) are two simple mixed graphs having the same vertex set, then \(\max\{ {\nu}_{1}(G_1), {\nu}_{1}(G_2)\}\leq {\nu}_{1}(G_1\cup G_2)\leq {\nu}_{1}(G_1)+ {\nu}_{1}(G_2)\).
Proof. We can write \(G_1\cup G_2=G_1\oplus G'_1\), where \(G'_1\) is the spanning submixed graph of \(G_2\) with \(E_{G'_1}=E_{G_2}\setminus E_{G_1}\) and \(\vec{E}_{G'_1}=\vec{E}_{G_2}\setminus \vec{E}_{G_1}\). Since \(G_1\) and \(G_2\) are spanning submixed graphs of \(G_1\cup G_2\), from Corollary 3.18, we have \( {\nu}_{1}(G_1)\leq {\nu}_{1}(G_1\cup G_2)\) and \( {\nu}_{1}(G_2)\leq {\nu}_{1}(G_1\cup G_2)\). So, the first inequality of the result holds. By Theorem 3.17, we have \( {\nu}_{1}(G_1\cup G_2)\leq {\nu}_{1}(G_1)+ {\nu}_{1}(G'_1)\leq {\nu}_{1}(G_1)+ {\nu}_{1}(G_2)\). Thus, the second inequality of the result holds. ◻
Let \(G\) be a mixed graph and let \(u,v\in V_G\). If there is no edge joining \(u\) and \(v\) in \(G\), then we denote this by \(u\not\sim v\). Similarly, if there is no arc from \(u\) to \(v\) in \(G\), then we denote this by \(u\not\rightarrow v\).
Theorem 3.20. Let \(G\) be a simple mixed graph on \(n\) vertices, and let \(u,v\in V_G\). Then we have the following.
(i) If \(u\not\sim v\) in \(G\), then \( {\nu}_{2n-1}(G)\leq\frac{1}{2}(d(u)+d(v)+d^+(u)+d^+(v))\) and \( {\nu}_{2n-1}(G)\leq\frac{1}{2}(d(u)+d(v)+d^-(u)+d^-(v))\).
(ii) If \(u\not\rightarrow v\) in \(G\), then \( {\nu}_{2n-1}(G)\leq\frac{1}{2}(d(u)+d(v)+d^+(u)+d^-(v))\).
Proof. (i) If \(u\not\sim v\) in \(G\), then \(u'\not\sim v'\) and \(u''\not\sim v''\) in \(G^A\), where \(u'\) and \(u''\) (resp. \(v'\) and \(v''\)) are the vertices of \(G^A\) corresponding to the vertex \(u\) (resp. \(v\)) of \(G\). By [7, Theorem 7.4.4] , we have \(\nu_{2n-1}(G^A)\leq\frac{1}{2}(d(u')+d(v'))\) and \(\nu_{2n-1}(G^A)\leq\frac{1}{2}(d(u'')+d(v''))\). Since \(\nu_{2n-1}(G^A)= {\nu}_{2n-1}(G)\) and \(d(u')=d(u)+d^+(u)\), \(d(v')=d(v)+d^+(v)\), \(d(u'')=d(u)+d^-(u)\) and \(d(v'')=d(v)+d^-(v)\), the result follows.
(ii) If \(u\not\rightarrow v\) in \(G\), then \(u'\not\sim v''\) in \(G^A\). From [7, Theorem 7.4.4], we have \(\nu_{2n-1}(G^A)\leq\frac{1}{2}(d(u')+d(v''))\). Since \(\nu_{2n-1}(G^A)= {\nu}_{2n-1}(G)\) and \(d(u')=d(u)+d^+(u)\) and \(d(v'')=d(v)+d^-(v)\), the result follows. ◻
Theorem 3.21. Let \(G\) be a simple mixed graph on \(n\) vertices. Then for any \(U\subset V_G\), we have \( {\nu}_{2n-1}(G)\leq {\nu}_{2k-1}(G-U)+2|U|\), where \(k=|V_G|-|U|\).
Proof. Let \(V_G=\{v_1,v_2,\ldots,v_n\}\). Without loss of generality, let \(U=\{v_1,v_2,\ldots,v_k\}\), where \(k\in\{1,2,\ldots,n-1\}\). Then \(U'=\{v'_1,v'_2,\ldots,v'_k,v''_1,v''_2,\ldots,v''_k\}\) is the set of vertices in \(G^A\) corresponding to \(U\). Since \(U'\subset V_{G^A}\), from [7, Theorem 7.4.5]: we have \(\nu_{2n-1}(G^A)\leq\nu_{2k-1}(G^A-U')+|U'|\), where \(k=|V_G|-|U|\). Since \( {\nu}_{2n-1}(G)=\nu_{2n-1}(G^A)\), \( {\nu}_{2k-1}(G-U)=\nu_{2k-1}(G^A-U')\), and \(|U'|=2|U|\), the result follows. ◻
Theorem 3.22. Let \(G\) be a simple mixed graph with \(E_G\neq \emptyset\) or \(\vec{E}_G\neq\emptyset\). Then \( {\nu}_1(G)\geq \max\{\Delta_1(G),\Delta_2(G)\}+1.\)
Proof. Since \(E_G\neq \emptyset\) or \(\vec{E}_G\neq\emptyset\), the graph \(G^A\) has at least one edge. Since \( {\nu}_1(G)=\nu_1(G^A)\) and \(\max\{\Delta_1(G),\Delta_2(G)\}=\Delta(G^A)\), the proof follows from [4, Theorem 4.12]: “ \(\nu_1(G)\geq\Delta(G)+1\) for any simple graph \(G\) having at least one edge”. ◻
We refer to a mixed graph \(G\) as plain if it has no multiple edges and no multiple arcs.
Lemma 3.23. A loopless mixed graph \(G\) is plain if and only if \(G^A\) is simple.
Proof. Let \(G\) be a loopless plain mixed graph. Since \(G\) has no loops, \(G^A\) also has no loops. Moreover, since \(G\) has no multiple edges and no multiple arcs, the construction of \(G^A\) ensures that \(G^A\) has no multiple edges. Therefore, \(G^A\) is simple. By retracing the argument, we can prove the converse of this result. ◻
Theorem 3.24. For a loopless plain mixed graph \(G\) with \(n\) vertices, the bound \( {\nu}_1(G) \leq 2n\) holds. Equality is attained if and only if \(G\) is a uniconnected mixed graph whose adjacency graph complement is disconnected.
Proof. Under the assumptions, it follows from Lemma 3.23 that \(G^A\) is a simple graph on \(2n\) vertices. Since \( {\nu}_1(G)=\nu_1(G^A)\), the result can be derived using Lemma 2.1 and [7, Proposition 7.3.3]. ◻
Theorem 3.25. For any simple mixed graph \(G\), \( {\nu}_1(G)\leq \max A\), where \(A=\{x\mid x=d(u)+d(v)+d^+(u)+d^+(v) \text{ or }x=d(u)+d(v)+d^-(u)+d^-(v) \text{ for } u,v\in V_G\text{ and } u \sim v\}\cup\{x\mid x=d(u)+d(v)+d^+(u)+d^-(v)\text{ for }u,v\in V_G\text{ and }u\rightarrow v\}\).
Proof. From [7, Theorem 7.3.4], we have \(\nu_1(G^A)\leq \max\{d(u)+d(v)\mid u,v\in V_{G^A}\text{ and } u \sim v \}\). Since \( {\nu}_1(G)=\nu_1(G^A)\), and the set \(\{d(u)+d(v)\mid u,v\in V_{G^A}\text{ and } u \sim v \}\) coincides with the set \(A\) defined in the theorem, the result follows. ◻
Theorem 3.26. Let \(G\) be a simple mixed graph with \(V_G=\{v_1,v_2,\ldots,v_n\}\). Let \(\mathcal{I}(G)=(a_{ij})\). Then \[\begin{aligned} {\nu}_1(G)\geq & \max\left(\left\{\sqrt{(d(v_i)+d^+(v_i)-d(v_j)-d^+(v_j))^2+4a_{ij}}\mid 1\leq i,j\leq n, i\neq j\right\}\right.\\ ~&\cup \left\{\sqrt{(d_{v_i}+d^+(v_i)-d(v_{j-n})-d^-(v_{j-n}))^2+4a_{ij}}\mid 1\leq i\leq n, n+1\leq j\leq 2n\right\}\\ ~&\cup \left\{\sqrt{(d(v_{i-n})+d^-(v_{i-n})-d(v_{j})-d^+(v_{j}))^2+4a_{ij}}\mid n+1\leq i\leq 2n, 1\leq j\leq n\right\}\\ ~&\cup \left.\left\{\sqrt{(d(v_{i-n})+d^-(v_{i-n})-d(v_{j-n})-d^-(v_{j-n}))^2+4a_{ij}}\mid n+1\leq i,j\leq 2n,i\neq j\right\}\right). \end{aligned}\]
Proof. The vertex degrees of \(G^A\) are \(d(v_1)+d^+(v_1)\), \(d(v_2)+d^+(v_2)\), \(\dots\), \(d(v_n)+d^+(v_n)\), \(d(v_1)+d^-(v_1)\), \(d(v_2)+d^-(v_2)\), \(\dots\), \(d(v_n)+d^-(v_n)\). If we denote the maximum in the right hand side of the inequality of this theorem as \(m\), then from [7, Theorem 7.3.6], we have \(\nu_1(G^A)\geq m\). Since \( {\nu}_1(G)=\nu_1(G^A)\), the result follows. ◻
Let \(G\) be a mixed graph on \(n\) vertices \(v_1,v_2,\ldots,v_n\). We denote for \(i=1,2,\ldots,n\), \[\begin{aligned} m_i:=avg\left\{\left\{d(v_k)+d^+(v_k)\mid v_i\sim v_k\right\}\cup\left\{d(v_k)+d^-(v_k)\mid v_i\rightarrow v_k\right\}\right\},\\ M_i:=avg\left\{\left\{d(v_k)+d^-(v_k)\mid v_i\sim v_k\right\}\cup\left\{d(v_k)+d^+(v_k)\mid v_i\leftarrow v_k\right\}\right\}, \end{aligned}\] where \(avg~S\) denotes the average of the numbers in the set S.
Theorem 3.27. If \(G\) is a simple mixed graph with \(V(G)=\{v_1,v_2,\ldots,v_n\}\), then \[\begin{aligned} & {\nu}_1(G)\leq \max\left(\left\{x\mid x=\frac{(d_i+d_i^+)(d_i+d_i^++m_i)+(d_j+d_j^+)(d_j+d_j^++m_j)}{d_i+d_i^++d_j+d_j^+}\right.\right. \text{~or~}\\ &\left. x=\frac{(d_i+d_i^-)(d_i+d_i^-+M_i)+(d_j+d_j^-)(d_j+d_j^-+M_j)}{d_i+d_i^-+d_j+d_j^-} \text{~for~}v_i\sim v_j\right\}\\ &\qquad \cup \left.\left\{x\mid x=\frac{(d_i+d_i^+)(d_i+d_i^++m_i)+(d_j+d_j^-)(d_j+d_j^-+M_j)}{d_i+d_i^++d_j+d_j^-} \text{~for~}v_i\rightarrow v_j\right\}\right), \end{aligned}\] where \(d_i=d(v_i)\), \(d^+_i=d^+(v_i)\), and \(d^-_i=d^-(v_i)\) for \(i=1,2,\ldots,n\).
Proof. The vertex degrees of \(G^A\) are \(d_{1}+d_{1}^+, d_{2}+d_{2}^+, \ldots, d_{n}+d_{n}^+, d_{1}+d_{1}^-, d_{2}+d_{2}^-, \dots\), \(d_{_n}+d_{n}^-\). Observe that \(m_i\) and \(M_i\) represent the average degrees of the neighbors of the vertices \(v'_i\) and \(v''_i\) in \(G^A\), respectively. Let \(s\) denotes the maximum value on the right hand side of the inequality stated in the theorem. Then from [7, Theorem 7.3.5], we conclude that \(\nu_1(G^A)\leq s\). Since \( {\nu}_1(G)=\nu_1(G^A)\), the result follows. ◻
In this section, we define the integrated signless Laplacian matrix of a mixed graph, investigate its properties, and analyze the relationship between its eigenvalues and the structural features of the mixed graph.
Definition 4.1. The integrated signless Laplacian matrix of a mixed graph \(G\), denoted by \(\mathcal{I}^Q(G)\), is defined as \(\mathcal{I}^Q(G)=\mathcal{I}^D(G)+\mathcal{I}(G)\).
Notice that each mixed graph can be determined from its integrated signless Laplacian matrix. The eigenvalues of \(\mathcal{I}^Q(G)\) are referred to as the \(\mathcal{I}^Q\)–eigenvalues of \(G\). We denote them by \( {\xi}_i(G)\) for \(i=1,2,\ldots,2n\). Since \(\mathcal{I}^Q(G)\) is real symmetric, its eigenvalues can be arranged, without loss of generality as \( {\xi}_1(G)\geq {\xi}_2(G)\geq\cdots\geq {\xi}_{2n}(G)\). The spectrum of \(\mathcal{I}^Q(G)\) is called the \(\mathcal{I}^Q\)–spectrum of \(G\). Observe that \(\mathcal{I}^Q(G)=Q(G^A)\), which implies that the spectrum of \(\mathcal{I}^Q(G)\) is identical to the spectrum of \(Q(G^A)\). Moreover, \(\mathcal{I}^Q(G)\) is positive semi-definite because \(Q(G^A)\) is positive semi-definite.
Observe that using (1), \(\mathcal{I}^Q(G)\) can be viewed as a \(2\times 2\) block matrix \[\label{signlessblock} \mathcal{I}^Q(G)=\begin{bmatrix} Q(G_u)+D_1 & \vec{A}(G_d)\\ \vec{A}(G_d)^T & Q(G_u)+D_2 \end{bmatrix}, \tag{4}\] where \(D_1=diag(d^+(v_1),d^+(v_2),\ldots,d^+(v_n))\) and \(D_2=diag(d^-(v_1),d^-(v_2),\ldots,d^-(v_n))\).
Observation 4.2. Let \(G\) be a mixed graph on \(n\) vertices. Then we have the following.
(i) \(G\) is \(r\)-regular if and only if \(2r\) is an eigenvalue of \(\mathcal{I}^Q(G)\) with corresponding eigenvector \(\boldsymbol{1}_{2n}\).
(ii) If \(G\) is a graph, then \(\mathcal{I}^Q(G)=I_2\otimes Q(G)\). The eigenvalues of \(\mathcal{I}^Q(G)\) are identical to those of \(Q(G)\) but with twice their multiplicities.
Theorem 4.3. Let \(G\) be a mixed graph on \(n\) vertices. Then \[\sum\limits_{i=1}^{2n} {\xi}_i(G)=4e(G)+8l(G)+2a(G).\]
Proof. Let \(V_G=\{v_1,v_2,\ldots,v_n\}\). Then \(\sum\limits_{i=1}^{2n} {\xi}_i(G)=tr(\mathcal{I}^Q(G))=tr(\mathcal{I}^D(G)+\mathcal{I}(G))=tr(\mathcal{I}^D(G))+tr(\mathcal{I}(G))=\sum\limits_{i=1}^{n}(2d(v_i)+d^+(v_i)+d^-(v_i))+\sum\limits_{i=1}^{n}4l(v_i)\). In this equations, by substituting the values \(\sum\limits_{i=1}^{n}d(v_i)=2e(G)+2l(G)\), and \(\sum\limits_{i=1}^{n}d^+(v_i)=a(G)=\sum\limits_{i=1}^{n}d^-(v_i)\) (c.f [9, Proposition 4.1]), the result follows. ◻
Theorem 4.4. Let \(G\) be a simple mixed graph having AB property. Then the characteristic polynomial of \(\mathcal{I}^Q(G)\) coincides with the characteristic polynomial of \(\mathcal{I}^L(G)\).
Proof. Since \(\mathcal{I}^Q(G)=Q(G^A)\) and \(\mathcal{I}^L(G)=L(G^A)\), the result follows from [9, Lemma 4.1]: “Let \(G\) be a mixed graph. \(G\) has AB property if and only if \(G^A\) is bipartite” and [7, Proposition 7.8.4]. ◻
As an immediate consequence of the previous theorem, we get the following.
Corollary 4.5. For any simple bipartite mixed graph \(G\), the characteristic polynomial of \(\mathcal{I}^Q(G)\) coincides with the characteristic polynomial of \(\mathcal{I}^L(G)\).
Theorem 4.6. If \(G\) is a simple mixed graph that is \(r\)-regular, then \(r\) is given by \(r = \frac{1}{2} {\xi}_1(G)\). Furthermore, the multiplicity of \( {\xi}_1(G)\) equals the number of mixed components in \(G\).
Proof. From [9, Lemma 6.1]: “Let \(G\) be a mixed graph. Then \(G\) is \(r\)-regular if and only if \(G^A\) is \(r\)-regular”, we know that \(G^A\) is an \(r\)-regular simple graph. According to [7, Theorem 7.8.6], we conclude that \(r=\frac{1}{2}\xi_1(G^A)=\frac{1}{2} {\xi}_1(G)\), and the multiplicity of \(\xi_1(G^A)\) equals the number of components of \(G^A\). Thus, the result follows from [9, Corollary 6.1]: “The number of mixed components of a mixed graph \(G\) is equal to the number of components of \(G^A\)”. ◻
Corollary 4.7. If \(G\) is an \(r\)-regular simple uniconnected mixed graph, then \( {\xi}_2(G)< {\xi}_1(G)=2r\).
Proof. Since \(G\) is uniconnected, it contains exactly one mixed component. Therefore, from Theorem 4.6, we know that \( {\xi}_1(G)=2r\) with multiplicity \(1\). This implies that \( {\xi}_1(G)\neq {\xi}_2(G)\), so we can conclude that \( {\xi}_2(G)< {\xi}_1(G)\). ◻
Theorem 4.8. The \(\mathcal{I}^Q\)-spectrum of an \(r\)-regular mixed graph \(G\) on \(n\) vertices is given by \(2r=r+ {\lambda}_1(G)\geq r+ {\lambda}_2(G)\geq\cdots\geq r+ {\lambda}_{2n}(G)\).
Proof. Since \(G\) is \(r\)-regular, we have \(\mathcal{I}^Q(G)=rI_{2n}+\mathcal{I}(G)\) and \( {\lambda}_1(G)=r\). Hence the result follows. ◻
Theorem 4.9. Let \(G\) be a mixed graph on \(n\) vertices. Then \(G\) is \((r,s)\)-regular if and only if \(2(r+s)\) and \(2r\) are \(\mathcal{I}^Q\)-eigenvalues of \(G\) with corresponding eigenvectors \(\boldsymbol{1}_{2n}\) and \(\begin{bmatrix} \boldsymbol{1}_n^T& -\boldsymbol{1}_n^T \end{bmatrix}^T\), respectively.
Proof. Suppose that \(G\) is \((r,s)\)-regular. Then by [9, Theorem 5.1], \(r+s\) and \(r-s\) are eigenvalues of \(\mathcal{I}(G)\) with corresponding eigenvectors \(\boldsymbol{1}_{2n}\) and \(\begin{bmatrix} \boldsymbol{1}_n^T& -\boldsymbol{1}_n^T \end{bmatrix}^T\), respectively. Observe that \(\mathcal{I}^Q(G)=(r+s)I_{2n}+\mathcal{I}(G)\). Therefore, \(2(r+s)\) and \(2r\) are eigenvalues of \(\mathcal{I}^Q(G)\) with corresponding eigenvectors \(\boldsymbol{1}_{2n}\) and \(\begin{bmatrix} \boldsymbol{1}_n^T& -\boldsymbol{1}_n^T \end{bmatrix}^T\), respectively.
Conversely, we assume that \(2(r+s)\) and \(2r\) are eigenvalues of \(\mathcal{I}^Q(G)\) with corresponding eigenvectors \(\boldsymbol{1}_{2n}\) and \(\begin{bmatrix} \boldsymbol{1}_{n}^T& -\boldsymbol{1}_n^T \end{bmatrix}^T\), respectively. Then \(d(u)+d^+(u)=r+s\), \(d(u)+d^-(u)=r+s\) and \(d(u)=r\) for all \(u\in V_G\). These implies that \(d(u)=r\) and \(d^+(u)=d^-(u)=s\) for all \(u\in V_G\). So \(G\) is \((r,s)\)-regular. ◻
Theorem 4.10.
(i) The \(\mathcal{I}^Q\)-spectrum of \(K^M_{k(m)}\) is \((4mk-4m)^{(1)}\), \((2mk-4m)^{(k-1)}\), \((2mk-2m)^{(2mk-k)}\).
(ii) The \(\mathcal{I}^Q\)-spectrum of \(K^D_{k(m)}\) is \((2mk-2m)^{(1)}\), \(0^{(1)}\), \((mk)^{(k-1)}\), \((mk-2m)^{(k-1)}\), \((mk-m)^{(2km-2k)}\).
Proof. From Theorem 4.8, the result can be proved similar to the proof of Theorem 3.8. ◻
Corollary 4.11. (i) The \(\mathcal{I}^Q\)-spectrum of \(K^M_{n}\) is \((4n-4)^{(1)}\), \((2n-4)^{(n-1)}\), \((2n-2)^{(n)}\).
(ii) The \(\mathcal{I}^Q\)-spectrum of \(K^D_n\) is \((2n-2)^{(1)}\), \(0^{(1)}\), \(n^{(n-1)}\), \((n-2)^{(n-1)}\).
Proof. By taking \(k=n\) and \(m=1\) in Theorem 4.10, the result follows. ◻
Theorem 4.12. (i) If \(G\) is an oriented graph of \(P_n\) \((n\geq 2)\) with all its arcs have the same direction, then the signless Laplacian spectrum of \(G\) is \(2^{(n-1)}\), \(0^{(n+1)}\).
(ii) If \(G\) is an oriented graph of \(C_n\) \((n\geq 3)\) with all its arcs have the same direction, then the signless Laplacian spectrum of \(G\) is \(2^{(n)}\), \(0^{(n)}\).
(iii) If \(G\) is an oriented graph of \(C_n\) \((n\geq 4)\) with all its arcs have the alternating direction, then the signless Laplacian spectrum of \(G\) is \(0^{(n)}\), and \((2+2\cos\frac{2\pi k}{n})^{(1)}\) for \(k=1,2,\ldots,n\).
Proof. Proof is similar to the proof of Theorem 3.10. ◻
Theorem 4.13. Let \(G\) be a uniconnected mixed graph on \(n\) vertices. If \(G\) has an alternating cycle of length \(2n\) such that it contains all the vertices, all the arcs and two times all the edges of \(G\), then the \(\mathcal{I}^Q\)-spectrum of \(G\) is \(2-2\cos\frac{\pi k}{n}\) for \(k=1,2,\ldots,2n\).
Proof. From Theorem 4.8, the result can be proved similar to the proof of Theorem 3.11. ◻
Theorem 4.14. Let \(G\) be a uniconnected simple mixed graph on \(n\) vertices. Then \(G\) has AB property if and only if \( {\xi}_{2n}(G)=0\), and is a simple eigenvalue.
Proof. By Lemma 2.1, \(G^A\) is a non-trivial, simple, connected graph on \(2n\) vertices. Since, \( {\xi}_{2n}(G)=\xi_{2n}(G^A)\) with the same multiplicity, the proof follows from [9, Lemma 4.1]: “Let \(G\) be a mixed graph. \(G\) has AB property if and only if \(G^A\) is bipartite” and [7, Theorem 7.8.1]. ◻
Lemma 4.15. Let \(G\) be a mixed graph. Then a non-trivial mixed component of \(G\) has the AB property if and only if \(G^A\) has a bipartite component.
Proof. Let \(H\) be a non-trivial mixed component of \(G\) that possesses the AB property, and let \(H'\) denote the associated component of \(H\) in \(G^A\). Then \(H'\) is non-trivial. By [9, Lemma 4.1]: “Let \(G\) be a mixed graph. \(G\) has AB property if and only if \(G^A\) is bipartite”, \(H^A\) is bipartite. As \(H'\) is a subgraph of \(H^A\), it is also bipartite. Thus, \(H'\) is a bipartite component of \(G^A\).
Conversely, suppose \(G^A\) has a bipartite component \(H'\). Let \(H\) be the mixed component in \(G\) corresponding to \(H'\). Then \(H\) is non-trivial. The bipartiteness of \(H'\) implies it has no odd cycles. Consequently, \(H\) has no odd cycles and no odd alternating cycles with an even number of arcs. This ensures that \(H\) has AB property. Therefore, \(G\) has a non-trivial mixed component having the AB property. ◻
Theorem 4.16. For any simple mixed graph \(G\), the multiplicity of \(0\) as an \(\mathcal{I}^Q\)-eigenvalue of \(G\) is equal to the number of mixed components of \(G\) that possess AB property.
Proof. From Lemma 4.15, the number of trivial mixed components of \(G\) having the AB property is the same as the number of bipartite components of \(G^A\). Additionally, the number of trivial mixed components of \(G\) matches the number of trivial components of \(G^A\). It is evident that trivial mixed components of \(G\) exhibit the AB property. Since \(\mathcal{I}^Q(G)=Q(G^A)\), the result follows directly from [7, Corollary 7.8.2]. ◻
Corollary 4.17. For a simple bipartite mixed graph \(G\) with \(n\) vertices, the eigenvalue \( {\xi}_{2n}(G)\) is zero, and its multiplicity corresponds to the number of mixed components in \(G\).
Proof. Since \(G\) is a simple bipartite mixed graph on \(n\) vertices, each mixed component of \(G\) has AB property. So, the result follows from Theorem 4.16. ◻
Theorem 4.18. Let \(G\) be a simple mixed graph on \(n\) vertices and let \(a\in \vec{E}_G\). If \(H=G-a\), then \(0\leq {\xi}_{2n}(G')\leq {\xi}_{2n}(G)\leq\cdots\leq {\xi}_{2}(H)\leq {\xi}_{2}(G)\leq {\xi}_{1}(H)\leq {\xi}_{1}(G)\).
Proof. Since \(H=G-a\), we have \({H}^A=G^A-e\), where \(e\) is the edge in \(G^A\) corresponding to the arc \(a\) in \(G\). Since \( {\xi}_{i}(G)=\xi_{i}(G^A)\) and \( {\xi}_{i}(H)=\xi_{i}(H^A)\) for \(i=1,2,\ldots,2n\), the proof follows from [7, Theorem 7.8.13]. ◻
Theorem 4.19. For a mixed graph \(G\) on \(n\) vertices, \[ {\xi}_{2n}(G)\leq\frac{2e(G)+4l(G)+a(G)}{n}\leq {\xi}_{1}(G).\]
Proof. By Theorem 4.3, \(\sum\limits_{i=1}^{2n} {\xi}_i(G)=4e(G)+8l(G)+2a(G\). Since \( {\xi}_{2n}(G)\leq {\xi}_i(G)\leq {\xi}_1(G)\) for \(i=1,2,\ldots,2n\), it follows that \(2n {\xi}_{2n}(G)\leq\sum\limits_{i=1}^{2n} {\xi}_i(G)\leq2n {\xi}_1(G)\). Therefore, the inequalities in this theorem are satisfied. ◻
Theorem 4.20. For any simple mixed graph \(G\), we have \[\min\{\delta_1(G),\delta_2(G)\}\leq\frac{1}{2} {\xi}_1(G)\leq\max\{\Delta_1(G),\Delta_2(G)\}.\]
For a uniconnected mixed graph \(G\), equality is achieved in either case if and only if \(G\) is regular.
Proof. Since \( {\xi}_1(G)=\xi_1(G^A)\), \(\min\{\delta_1(G),\delta_2(G)\}=\delta(G^A)\) and \(\max\{\Delta_1(G),\Delta_2(G)\}=\Delta(G^A)\), the inequalities in this theorem hold from [7, Proposition 7.8.14].
From [9, Lemma 6.1]: “Let \(G\) be a mixed graph. Then \(G\) is \(r\)-regular if and only if \(G^A\) is \(r\)-regular” and Lemma 2.1, the remaining assertion of this theorem holds. ◻
Let \(G\) be a mixed graph with \(V_G=\{v_1,v_2,\ldots,v_n\}\). Consider the multiset of values \[\{x\mid x=d(v_i)+d^+(v_i)+2l(v_i) ~\text{or}~ x=d(v_i)+d^-(v_i)+2l(v_i) ~\text{for}~i=1,2,\ldots,n\}.\]
Arrange these values in decreasing order to form the sequence \(d_1\geq d_2\geq \cdots\geq d_{2n}\). Observe that \(d_i\)s are the diagonal entries of the matrix \(\mathcal{I}^Q(G)\). Then the following result holds:
Theorem 4.21. For a mixed graph \(G\) with \(n\) vertices, the inequality \(\sum\limits_{i=1}^{k} {\xi}_i(G) \geq \sum\limits_{i=1}^{k} d_i\) holds for \(k = 1,2, \dots, 2n\), with equality attained when \(k = 2n\).
Proof. Applying [7, Theorem 1.3.2] to the positive semi-definite matrix \(\mathcal{I}^Q(G)\), we deduce that the sum of the \(k\) largest diagonal entries of \(\mathcal{I}^Q(G)\) is a lower bound of \(\sum\limits_{i=1}^{k} {\xi}_i(G)\). Moreover, \(\sum\limits_{i=1}^{2n} {\xi}_i(G)=tr(\mathcal{I}^Q(G))=\sum\limits_{i=1}^{2n}d_i\). This completes the proof. ◻
Theorem 4.22. Let \(G\) be a simple mixed graph on \(n\) vertices. Then \[ {\xi}_1(G)+ {\xi}_{2n}(G)\leq 2\xi_1(G_u)+\underset{u\in V_G}{\max}~d^+(u)+\underset{u\in V_G}{\max}~d^-(u).\]
Proof. We consider \(\mathcal{I}^Q(G)\) as mentioned in (4). By taking \(M=\mathcal{I}^Q(G)\), \(P=Q(G_u)+D_1\), \(Q=\vec{A}(G_d)\) and \(R=Q(G_u)+D_2\) in [7, Proposition 1.3.16], we get \[\label{thm-LaplacianQeq1} {\xi}_1(G)+ {\xi}_{2n}(G)\leq \lambda_1(Q(G_u)+D_1)+\lambda_1(Q(G_u)+D_2). \tag{5}\]
From [4, Lemma 3.19], it follows that \[\label{thm-LaplacianQeq2} \displaystyle\lambda_1(Q(G_u)+D_1)\leq \xi_1(Q(G_u))+\underset{v_i\in V_G}{\max}~d^+(v_i) \tag{6}\] and \[\label{thm-LaplacianQeq3} \displaystyle\lambda_1(Q(G_u)+D_2)\leq \xi_1(Q(G_u))+\underset{v_i\in V_G}{\max}~d^-(v_i). \tag{7}\]
The result follows by substituting (6) and (7) into (5). ◻
Theorem 4.23. Let \(G\) be a mixed graph on \(n\) vertices. Then \( {\xi}_{2n}(G)\leq\displaystyle\frac{4}{n}(e(G)+l(G))\leq {\xi}_2(G)\) and \( {\xi}_{2n-1}(G)\leq\displaystyle\frac{2}{n}(2e(G)+2l(G)+a(G))\leq {\xi}_1(G)\).
Proof. Consider \(\mathcal{I}^Q(G)\) as mentioned in (4). The sums of the entries of \(Q(G_u)+D_1\), \(Q(G_u)+D_2\), and \(\vec{A}(G_d)\) are \(4e(G)+4l(G)+a(G)\), \(4e(G)+4l(G)+a(G)\), and \(a(G)\), respectively. From [7, Corollary 1.3.13], the eigenvalues \(\frac{2}{n}(2e(G)+2l(G)+a(G))\) and \(\frac{4}{n}(e(G)+l(G))\) of the matrix \(\frac{4}{n}(e(G)+l(G))I_2+\frac{1}{n}a(G)J_2\) interlace the eigenvalues of \(\mathcal{I}^Q(G)\). This concludes the proof. ◻
Theorem 4.24. If a simple mixed graph \(G\) on \(n\) vertices has a factorization \(G=G_1\oplus G_2\), then the following hold:
(i) \(\max\{ {\xi}_{1}(G_1), {\xi}_{1}(G_2)\}\leq {\xi}_{1}(G)\leq {\xi}_{1}(G_1)+ {\xi}_{1}(G_2)\),
(ii) \( {\xi}_{2n}(G_1)+ {\xi}_{2n}(G_2)\leq {\xi}_{2n}(G)\).
Proof. Since \(G=G_1\oplus G_2\), we have \(\mathcal{I}^Q(G)=\mathcal{I}^Q(G_1)+\mathcal{I}^Q(G_2)\). Let \(X\) be a column vector in \(\mathbb{R}^{2n}\) with the usual Euclidean norm. Then by extremal representation of eigenvalues: \[\begin{aligned} {\xi}_1(G)=&\underset{||X||=1}{\max}X^T\mathcal{I}^Q(G)X\\ =&\underset{||X||=1}{\max}(X^T\mathcal{I}^Q(G_1)X+X^T\mathcal{I}^Q(G_2)X)\\ \leq&\underset{||X||=1}{\max}X^T\mathcal{I}^Q(G_1)X+\underset{||X||=1}{\max}X^T\mathcal{I}^Q(G_2)X\\ =& {\xi}_1(G_1)+ {\xi}_1(G_2). \end{aligned}\]
Moreover, since \[ {\xi}_1(G)=\underset{||X||=1}{\max}(X^T\mathcal{I}^Q(G_1)X+X^T\mathcal{I}^Q(G_2)X),\] and both \(\mathcal{I}^Q(G_1)\) and \(\mathcal{I}^Q(G_2)\) are positive semi-definite, we also have \[ {\xi}_1(G)\geq\underset{||X||=1}{\max}X^T\mathcal{I}^Q(G_1)X= {\xi}_1(G_1),\] and \[ {\xi}_1(G)\geq\underset{||X||=1}{\max}X^T\mathcal{I}^Q(G_2)X= {\xi}_1(G_2).\]
Thus, part (i) is established.
For part (ii), using the extremal representation of the smallest eigenvalue, we have: \[\begin{aligned} {\xi}_{2n}(G)=&\underset{||X||=1}{\min}X^T\mathcal{I}^Q(G)X\\ =&\underset{||X||=1}{\min}(X^T\mathcal{I}^Q(G_1)X+X^T\mathcal{I}^Q(G_2)X)\\ \geq&\underset{||X||=1}{\min}X^T\mathcal{I}^Q(G_1)X+\underset{||X||=1}{\min}X^T\mathcal{I}^Q(G_2)X\\ =& {\xi}_{2n}(G_1)+ {\xi}_{2n}(G_2). \end{aligned}\]
This completes the proof of part (ii). ◻
Corollary 4.25. Let \(G\) be a simple mixed graph on \(n\) vertices. If \(H\) is a spanning submixed graph of \(G\), then \( {\xi}_{1}(H)\leq {\xi}_{1}(G)\) and \( {\xi}_{2n}(H)\leq {\xi}_{2n}(G)\).
Proof. We can express \(G=H\oplus H'\), where \(H'\) is the spanning submixed graph of \(G\) with \(E_{H'}=E_G\setminus E_H\) and \(\vec{E}_{H'}=\vec{E}_G\setminus \vec{E}_H\). The result then follows directly from Theorem 2.24. ◻
Corollary 4.26. If \(G_1\) and \(G_2\) are two simple mixed graphs having the same vertex set, then \[\max\{ {\xi}_{1}(G_1), {\xi}_{1}(G_2)\}\leq {\xi}_{1}(G_1\cup G_2)\leq {\xi}_{1}(G_1)+ {\xi}_{1}(G_2).\]
Proof. Since \(G_1\) and \(G_2\) are spanning submixed graphs of \(G_1\cup G_2\), it follows from Corollary 4.25 that \( {\xi}_{1}(G_1)\leq {\xi}_{1}(G_1\cup G_2)\) and \( {\xi}_{2}(G_1)\leq {\xi}_{1}(G_1\cup G_2)\). Thus, the first inequality in the result holds. We can write \(G_1\cup G_2=G_1\oplus G'_1\), where \(G'_1\) is the spanning submixed graph of \(G_2\) with \(E_{G'_1}=E_{G_2}\setminus E_{G_1}\) and \(\vec{E}_{G'_1}=\vec{E}_{G_2}\setminus \vec{E}_{G_1}\). From Theorem 4.24, we have \( {\xi}_{1}(G_1\cup G_2)\leq {\xi}_{1}(G_1)+ {\xi}_{1}(G'_1)\leq {\xi}_{1}(G_1)+ {\xi}_{1}(G_2)\). Hence, the second inequality of the result also holds. ◻
Theorem 4.27. Let \(G\) be a simple mixed graph. Then we have the following.
(i)\( {\xi}_1(G)=0\) if and only if \(G\) has no edges and arcs;
(ii) \( {\xi}_1(G)<4\) if and only if each mixed component of \(G\) has AP property;
(iii) for a uniconnected mixed graph \(G\), \( {\xi}_1(G)=4\) if and only if \(G\) has an alternating cycle with even number of arcs such that it contains all the vertices, all the arcs and two times all the edges of \(G\).
Proof. From [7, (i), (ii), (iii) of Proposition 7.8.16], the following results hold:
(i) \(G^A\) has no edges if and only if \(\xi_1(G^A)=0\).
(ii) All the components of \(G^A\) are paths if and only if \(\xi_1(G^A)<4\).
(iii) When \(G^A\) is connected, \(G^A\) is a cycle or \(K_{1,3}\) if and only if \(\xi_1(G^A)=4\).
Since \( {\xi}_1(G)=\xi_1(G^A)\) and \(G\) has no edges and arcs if and only if \(G^A\) has no edges, part (i) follows.
From [9, Lemma 7.2]: “Let \(G\) be a mixed graph. A mixed component of \(G\) has AP property if and only if the corresponding component of \(G^A\) is a path”, part (ii) follows.
Nowsuppose \(G\) is uniconnected. By Lemma 2.1, \(G^A\) is connected. This implies that \(G\) has an alternating cycle with an even number of arcs that includes all vertices, all arcs, and two instances of every edge of \(G\) if and only if \(G^A\) is a cycle. Additionally, for any mixed graph \(G\), it can be verified that \(G^A\neq K_{1,3}\). Thus, part (iii) follows. ◻
Definition 4.28. A mixed graph \(G\) is said to be directed loop complete if for any two distinct vertices \(u,v\in V_G\), \(u\overset{1}{\sim}v\), \(u\overset{1}{\rightarrow}v\) and \(v\overset{1}{\rightarrow}u\), and for each vertex \(u\in V_G\), \(u\overset{1}{\rightarrow}u\).
Lemma 4.29. A mixed graph \(G\) is directed loop complete if and only if \(G^A\) is complete.
Proof. Let \(G\) be a directed loop complete mixed graph with \(V_G=\{v_1,v_2,\ldots,v_n\}\). It is clear that \(E_G\) and \(\vec{E}_G\) are sets and so, \(G\) is plain. As \(G\) is loopless, from Lemma 3.23, \(G^A\) is simple. For \(i=1,2,\ldots,n\), we have \(d(v_i)=n-1\), \(d^+(v_i)=n\) and \(d^-(v_i)=n\). This implies that for \(i=1,2,\ldots,n\), \(d(v'_i)=d(v_i)+d^+(v_i)=2n-1\) and \(d(v''_i)=d(v_i)+d^+(v_i)=2n-1\) in \(G^A\). That is each vertex of \(G^A\) has degree \(2n-1\). Thus \(G^A\) is complete. By retracing the above arguments, the converse of this theorem can be proved. ◻
Theorem 4.30. For a uniconnected loopless plain mixed graph \(G\) on \(n\) vertices, \(2+2\cos{\frac{\pi}{2n}}\leq {\xi}_1(G)\leq 4n-2\). Equality in the lower bound occurs if \(G\) satisfies the AP property, while the upper bound is reached when \(G\) is a directed loop-complete graph.
Proof. Since \( {\xi}_1(G)=\xi_1(G^A)\), the inequalities in this theorem hold from Lemma 2.1 and [7, Proposition 7.8.17]. From [9, Lemma 7.2]: “Let \(G\) be a mixed graph. A mixed component of \(G\) has AP property if and only if the corresponding component of \(G^A\) is a path” and Lemma 4.29, the remaining assertion of this theorem hold. ◻
In this section, we introduce the normalized integrated Laplacian matrix of a mixed graph, study its properties, and analyze the relationship between its eigenvalues and the structural characteristics of the mixed graph.
Definition 5.1. Let \(G\) be a mixed graph with \(V_G=\{v_1,v_2,\ldots,v_n\}\). For \(i=1,2,\ldots,n\), let \(v'_i\) and \(v''_i\) be two copies of \(v_i\). We define the normalized integrated Laplacian matrix of \(G\), denoted by \(\mathcal{I}^{\mathcal{L}}(G)\), as the square matrix of order \(2n\), with rows and columns are indexed by the elements of the set \(\{v'_1,v'_2,\ldots,v'_n,v''_1,v''_2,\ldots,v''_n\}\). For \(i,j=1,2,\ldots,n\),
the \((v'_i,v'_j)\)-th entry of \(\mathcal{I}^{\mathcal{L}}(G)=\begin{cases} 1-\frac{2l(v_i)}{d_i+d^+_i}, & \text{if~} i=j \text{~and~} d_i+d^{+}_i\neq 0;\\ \frac{-\beta}{\sqrt{(d^{+}_{i}+d_{i})(d^{+}_{j}+d_{j})}}, & \text{if}~i\neq j\text{ and}~ v_{i}\overset{\beta}{\sim} v_{j};\\ 0, & \text{otherwise}; \end{cases}\)
the \((v''_i,v''_j)\)-th entry of \(\mathcal{I}^{\mathcal{L}}(G)=\begin{cases} 1-\frac{2l(v_i)}{d_i+d^-_i}, & \text{if~} i=j \text{~and~} d_i+d^{-}_i\neq 0;\\ \frac{-\beta}{\sqrt{(d^{-}_{i}+d_{i})(d^{-}_{j}+d_{j})}}, & \text{if}~i\neq j\text{ and}~ v_{i}\overset{\beta}{\sim} v_{j};\\ 0, & \text{otherwise}; \end{cases}\)
where \(d_i=d(v_i)\), \(d^+_i=d^+(v_i)\), \(d^-_i=d^-(v_i)\).
Let \(G\) be a mixed graph on \(n\) vertices \(v_1,v_2,\ldots,v_n\). Note that \(G\) has no trivial mixed components if and only if, for each \(i=1,2,\ldots,n\), at least one of the following holds:
(i) \(d(v_i)\neq 0\); or
(ii) \(d^+(v_i)\neq 0\) and \(d^-(v_i)\neq 0\).
Since the diagonal entries of \(\mathcal{I}^D(G)\) are \(d(v_i)+d^+(v_i)\) and \(d(v_i)+d^-(v_i)\) for \(i=1,2,\ldots,n\), it follows that \(G\) has no trivial mixed components if and only if \(\mathcal{I}^D(G)\) is non-singular. Therefore, for a mixed graph \(G\) having no trivial mixed components, by maintaining the same order in the indices of \(\mathcal{I}^D(G)\) and \(\mathcal{I}^L(G)\), the normalized integrated Laplacian matrix of \(G\) can be written as: \[\mathcal{I}^{\mathcal{L}}(G)=\mathcal{I}^D(G)^{-\frac{1}{2}}\mathcal{I}^L(G)\mathcal{I}^D(G)^{-\frac{1}{2}}.\]
Notice that each simple mixed graph can be determined from its normalized integrated Laplacian matrix. The eigenvalues of \(\mathcal{I}^{\mathcal{L}}(G)\) are referred to as the \(\mathcal{I}^{\mathcal{L}}\)–eigenvalues of \(G\). These eigenvalues are denoted by \(\hat{ {\nu}}_1(G)\) for \(i=1,2,\ldots,2n\). Since \(\mathcal{I}^{\mathcal{L}}(G)\) is a real symmetric matrix, its eigenvalues can be arranged, without loss of generality, in non-increasing order as: \(\hat{ {\nu}}_1(G)\geq\hat{ {\nu}}_2(G)\geq\cdots\geq\hat{ {\nu}}_{2n}(G)\). The spectrum of \(\mathcal{I}^{\mathcal{L}}(G)\) is called the \(\mathcal{I}^{\mathcal{L}}\)–spectrum of \(G\). Observe that \(\mathcal{I}^{\mathcal{L}}(G)=\widehat{L}(G^A)\) and therefore, the spectrum of \(\mathcal{I}^{\mathcal{L}}(G)\) is identical to the spectrum of \(\widehat{L}(G^A)\).
Observation 5.2. Let \(G\) be a mixed graph. Then we have the following.
(i) \(\mathcal{I}^{\mathcal{L}}(G)\) is positive semi-definite, since \(\widehat{L}(G^A)\) is positive semi-definite.
(ii) The least eigenvalue of \(\mathcal{I}^{\mathcal{L}}(G)\) is \(0\), since the least eigenvalue of \(\widehat{L}(G^A)\) is \(0\).
(iii) If \(G\) is a graph, then \(\mathcal{I}^{\mathcal{L}}(G)=I_2\otimes\widehat{L}(G)\). The eigenvalues of \(\mathcal{I}^{\mathcal{L}}(G)\) are the same as those of \(\widehat{L}(G)\), with each eigenvalue having twice its algebraic multiplicity.
(iv) If \(G\) is \(r\)-regular, then \(0\) is an eigenvalue of \(\mathcal{I}^{\mathcal{L}}(G)\), with corresponding eigenvector \(\boldsymbol{1}\).
Theorem 5.3. Let \(G\) be a loopless plain mixed graph on \(n\) vertices. Then the following statements hold:
(i) \(\sum\limits_{i=1}^{2n}\hat{ {\nu}}_i(G)\leq2n\), with equality if and only if \(G\) has no trivial mixed component.
(ii) \(\sum\limits_{i=1}^{2n}\hat{ {\nu}}_i(G)=2n-k\), where \(k\) is the number of trivial mixed components of \(G\).
(iii) If \(G\) is not directed loop complete, then \(\hat{ {\nu}}_{2n-1}(G)\leq 1\).
(iv) If \(G\) has no trivial mixed component, then \(\hat{ {\nu}}_{2n-1}(G)\leq\frac{2n}{2n-1}\), with equality occurring if and only if \(G\) is directed loop complete.
(v) If \(G\) has no trivial mixed component, then \(\hat{ {\nu}}_{1}(G)\geq\frac{2n}{2n-1}\), with equality is achieved if and only if \(G\) is directed loop complete.
(vi) \(\hat{ {\nu}}_1(G)\leq 2\), with equality if and only if \(G\) has a non-trivial mixed component, which has the AB property. In this case, the multiplicity of \(\hat{ {\nu}}_1(G)= 2\) equals the number of non-trivial mixed components of \(G\) having the AB property.
Proof. Notice that \(G\) has no trivial mixed component if and only if \(G^A\) has no isolated vertices. From [7, Theorem 7.7.2(i)], we have \(\sum\limits_{i=1}^{2n}\hat{\nu}_i(G^A)\leq2n\) with equality holds if and only if \(G^A\) has no isolated vertices. Since \(\mathcal{I}^{\mathcal{L}}(G)\) and \(\widehat{L}(G^A)\) have the same spectrum, part (i) follows.
To prove (ii), let \(G\) has \(k\geq 0\) trivial mixed components. This implies that \(G^A\) has \(k\) isolated vertices. By removing these \(k\) isolated vertices from \(G^A\), we obtain a subgraph \(G'\) of \(G^A\), having \(2n-k\) vertices. From [7, Theorem 7.7.2(i)], we have \(\sum\limits_{i=1}^{2n-k}\hat{\nu}_i(G')=2n-k\). Also, \[\sum\limits_{i=1}^{2n}\hat{ {\nu}}_i(G)=\sum\limits_{i=1}^{2n}\hat{\nu}_i(G^A)=\sum\limits_{i=1}^{2n-k}\hat{\nu}_i(G').\]
Hence part (ii) follows.
From Lemma 4.29 and [7, parts (ii), (iii), (iv) of Theorem 7.7.2], we have the following:
(i) If \(G^A\) is not complete, \(\hat{\nu}_{2n-1}(G^A)\leq 1\).
(ii) \(\hat{\nu}_{2n-1}(G^A)\leq\frac{2n}{2n-1}\), with equality holds if and only if \(G^A\) is complete.
(iii) \(\hat{\nu}_1(G^A)\geq\frac{2n}{2n-1}\), with equality holds if and only if \(G^A\) is complete.
Since \(\hat{ {\nu}}_{2n-1}(G)=\hat{\nu}_{2n-1}(G^A)\) and \(\hat{ {\nu}}_{1}(G)=\hat{\nu}_{1}(G^A)\), parts (iii), (iv) and (v) follows.
From [7, Theorem 7.7.2(v)], \(\hat{\nu}_1(G^A)\leq 2\), with equality is achieved if and only if \(G^A\) has a non-trivial component which is bipartite. Since \(\hat{ {\nu}}_1(G)=\hat{\nu}_1(G^A)\), from Lemma 4.15, first assertion of part (vi) follows.
From [7, Theorem 7.7.2(v)], \(2\) is a simple eigenvalue of \(\widehat{L}(H)\), for a connected bipartite graph \(H\). Therefore, if \(G^A\) has a non-trivial bipartite component, then \(2\) is an eigenvalue of \(\widehat{L}(G^A)\), with multiplicity equal to the number of non-trivial bipartite components of \(G^A\) which is the same as the number of non-trivial mixed components of \(G\) having the AB property. This completes the proof of part (vi). ◻
Corollary 5.4. If \(G\) is a loopless plain bipartite mixed graph having at least one edge or arc, then \(\hat{ {\nu}}_1(G)=2\) with multiplicity equal to the number of non-trivial mixed components of \(G\).
Proof. If \(G\) is a bipartite mixed graph with at least one edge or arc, then each non-trivial mixed component of \(G\)possesses the AB property. Consequently, the result follows directly from part (vi) of Theorem 5.3. ◻
Theorem 5.5. If \(G\) is a loopless plain mixed graph on \(n\) vertices, then \[\hat{ {\nu}}_{2n-1}(G)\leq\frac{2n-k}{2n-1}\leq\hat{ {\nu}}_{1}(G),\] where \(k\) is the number of trivial mixed components of \(G\).
Proof. Given that \(\hat{ {\nu}}_{2n-1}(G)\leq\hat{ {\nu}}_i(G)\leq\hat{ {\nu}}_1(G)\) for \(i=1,2,\ldots,2n-1\), we deduce \[(2n-1)\hat{ {\nu}}_{2n-1}(G)\leq\sum\limits_{i=1}^{2n-1}\hat{ {\nu}}_i(G)\leq(2n-1)\hat{ {\nu}}_1(G).\]
Since \(\hat{ {\nu}}_{2n}(G)=0\), part (ii) of Theorem 5.3 implies that \(\sum\limits_{i=1}^{2n-1}\hat{ {\nu}}_i(G)=2n-k\). Substituting this in the above inequality completes the proof. ◻
Theorem 5.6. Let \(G\) be a simple mixed graph. Then, the number of mixed components in \(G\) is equal to the multiplicity of \(0\) as an eigenvalue of \(\mathcal{I}^{\mathcal{L}}(G)\).
Proof. Since the spectrum of \(\mathcal{I}^{\mathcal{L}}(G)\) is identical to the spectrum of \(\widehat{L}(G^A)\), the result follows from [9, Corollary 6.1]: “The number of mixed components of a mixed graph \(G\) is equal to the number of components of \(G^A\)” and [7, Theorem 7.7.3]. ◻
Corollary 5.7. Let \(G\) be a simple mixed graph on \(n\) vertices with no trivial mixed components. Then \(G\) has the AB property if and only if \(\hat{ {\nu}}_1(G)=2\), with the same multiplicity as \(\hat{ {\nu}}_{2n}(G)=0\).
Proof. Since \(G\) has no trivial mixed components, it has the AB property if and only if each mixed component of \(G\) has the AB property. So from Theorems 5.6 and 5.3(vi), the result follows. ◻
Theorem 5.8. Let \(G\) be an \(r\)-regular simple mixed graph on \(n\) vertices.
(i) If \( {\lambda}_1(G)\geq {\lambda}_{2}(G)\geq\cdots\geq {\lambda}_{2n}(G)\) is the \(\mathcal{I}\)-spectrum of \(G\) with corresponding eigenvectors \(X_1,X_2,\ldots,X_{2n}\), then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \(1-\frac{ {\lambda}_1(G)}{r}\leq 1-\frac{ {\lambda}_2(G)}{r}\leq \cdots\leq 1-\frac{ {\lambda}_{2n}(G)}{r}\) with corresponding eigenvectors \(X_1,X_2,\ldots,X_{2n}\).
(ii) If \( {\mu}_1(G)\geq {\mu}_{2}(G)\geq\cdots\geq {\mu}_{2n}(G)\) is the \(\mathcal{I}^L\)-spectrum of \(G\) with corresponding eigenvectors \(X_1,X_2,\ldots,X_{2n}\), then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \(\frac{ {\mu}_1(G)}{r}\geq \frac{ {\mu}_2(G)}{r}\geq \cdots\geq \frac{ {\mu}_{2n}(G)}{r}\) with corresponding eigenvectors \(X_1,X_2,\ldots,X_{2n}\).
(iii) If \(G\) is a directed graph such that \((u,v)\in\vec{E}_G\) if and only if \((v,u)\in\vec{E}_G\), and the spectrum of \(\vec{A}(G)\) is \(\lambda_1\geq\lambda_{2}\geq\cdots\geq\lambda_n\) with corresponding eigenvectors \(X_1,X_2,\ldots,X_n\), then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \(1-\frac{2\lambda_i}{r}\) with corresponding eigenvector \(\begin{bmatrix} X_i^T& X_i^T \end{bmatrix}^T\) for \(i=1,2,\ldots,n\), and \(1^{(n)}\) with corresponding eigenvectors \(\begin{bmatrix} X_i^T& -X_i^T \end{bmatrix}^T\) for \(i=1,2,\ldots,n\).
(iv) If \(G\) is a graph and the spectrum of \(A(G)\) is \(\lambda_1(G)\geq\lambda_{2}(G)\geq\cdots\geq\lambda_n(G)\) with corresponding eigenvectors \(X_1,X_2,\ldots,X_n\), then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \((1-\frac{\lambda_i(G)}{r})^{(2)}\) with corresponding eigenvectors \(\begin{bmatrix} X_i^T& \mathbf{0}_{1\times n} \end{bmatrix}^T\) and \(\begin{bmatrix} \mathbf{0}_{1\times n}& X_i^T \end{bmatrix}^T\) for \(i=1,2,\ldots,n\).
(v) If \(G\) is a graph and the spectrum of \(L(G)\) is \(\mu_1(G)\geq\mu_{2}(G)\geq\cdots\geq\mu_n(G)\) with corresponding eigenvectors \(X_1,X_2,\ldots,X_n\), then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \((\frac{\mu_i(G)}{r})^{(2)}\) with corresponding eigenvectors \(\begin{bmatrix} X_i^T& \mathbf{0}_{1\times n} \end{bmatrix}^T\) and \(\begin{bmatrix} \mathbf{0}_{1\times n}& X_i^T \end{bmatrix}^T\) for \(i=1,2,\ldots,n\).
Proof. Since \(G\) is \(r\)-regular, we have \(\mathcal{I}^D(G)=rI_{2n}\), which implies \(\mathcal{I}^D(G)^{\frac{1}{2}}=\displaystyle\frac{1}{\sqrt{r}}I_{2n}\). Therefore, \(\mathcal{I}^{\mathcal{L}}(G)=I_{2n}-\displaystyle\frac{1}{r}\mathcal{I}(G)\). Hence part (i) follows. The remaining parts can be established in a similar manner. ◻
Theorem 5.9. (i) The \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(K^M_{k(m)}\) is \(0^{(1)}\), \((\frac{k}{k-1})^{(k-1)}\), \(1^{(2mk-k)}\).
(ii) The \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(K^D_{k(m)}\) is \(2^{(1)}\), \(0^{(1)}\), \((\frac{k}{k-1})^{(k-1)}\), \((\frac{k-2}{k-1})^{(k-1)}\), and \(1^{(2km-2k)}\).
Proof. From Theorem 5.8(i), the results can be proved similar to the proof of Theorem 3.8. ◻
Corollary 5.10. (i) The \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(K^M_n\) is \(0^{(1)}\), \((\frac{n}{n-1})^{(n-1)}\), \(1^{(n)}\).
(ii) The \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(K^D_n\) is \(0^{(2)}\), \((\frac{n}{n-1})^{(n-1)}\), \((\frac{n-2}{n-1})^{(n-1)}\).
Proof. By taking \(k=n\) and \(m=1\) in Theorem 5.9, the result follows. ◻
Theorem 5.11. (i) If \(G\) is the oriented graph of \(P_n\) \((n\geq 2)\) with all its arcs have the same direction, then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \(2^{(n-1)}\), \(0^{(n+1)}\).
(ii) If \(G\) is the oriented graph of \(C_n\) \((n\geq 3)\) with all its arcs have the same direction, then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \(2^{(n)}\), \(0^{(n)}\).
(iii) If \(G\) is the oriented graph of \(C_n\) \((n\geq 4)\) with all its arcs have the alternating direction, then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \(0^{(n)}\), and \((1-\cos\frac{2\pi k}{n})^{(1)}\) for \(k=1,2,\ldots,n\).
Proof. The proof is similar to that of Theorem 3.10. ◻
Theorem 5.12. Let \(G\) be a uniconnected mixed graph on \(n\) vertices. If \(G\) has an alternating cycle of length \(2n\) that includes all vertices, all arcs and each edge of \(G\) exactly twice, then the \(\mathcal{I}^{\mathcal{L}}\)-spectrum of \(G\) is \(1-\cos\frac{\pi k}{n}\) for \(k=1,2,\ldots,2n\).
Proof. From Theorem 5.8(i), the result can be proved similar to the proof of Theorem 3.11. ◻
Theorem 5.13. Let \(G\) be a simple mixed graph, and let \(u,v\in V_G\) be such that \(u\neq v\) and \(u\not\sim v\). If \(H\) is obtained by identifying \(u\) and \(v\) into a single vertex, then \(\hat{ {\nu}}_{2n-1}(G)\leq\hat{ {\nu}}_{2n-3}(H)\).
Proof. Let \(u',u''\) and \(v',v''\) be the vertices of \(G^A\) corresponding to the vertices \(u\) and \(v\), respectively. Then \(H^A\) is a contraction of \(G^A\), which is obtained by identifying \(u'\) and \(v'\) into a single vertex, and \(u''\) and \(v''\) into a single vertex. This implies that \(H^A\) has \(2n-2\) vertices. From [6, Lemma 1.15]: “Let \(G\) be a graph on \(n\) vertices. If \(H\) is obtained by contractions from \(G\) and \(H\) has \(m\) vertices, then \(\hat{\nu}_{n-1}(G)\leq\hat{\nu}_{m-1}(H)\)”, it follows that \(\hat{\nu}_{2n-1}(G^A)\leq\hat{\nu}_{2n-3}(H^A)\). Since \(\hat{ {\nu}}_{2n-1}(G)=\hat{\nu}_{2n-1}(G^A)\) and \(\hat{ {\nu}}_{2n-3}(H)=\hat{\nu}_{2n-3}(H^A)\), the result follows. ◻
Definition 5.14. Let \(G\) be a mixed graph, and let \(X,Y\subseteq V_G\). We define \[e(X,Y)=|\{\{u,v\}\in E_G\mid u\in X\text{ and }v\in Y\}|,\] and \[a(X,Y)=|\{(u,v)\in \vec{E}_G\mid u\in X\text{ and }v\in Y\}|.\]
For \(S\subseteq V_G\), the mixed volume of \(S\) in \(G\) is defined as \[\text{vl}(S)=\sum\limits_{v\in S}(2d(v)+d^+(v)+d^-(v)).\]
Note that in particular, for a graph \(G\), we have \(\text{vl}(S)=2\text{vol}(S)\).
Lemma 5.15. Let \(G\) be a mixed graph, and let \(X\subseteq V_G\). Then we have \(\text{vl}(X)=\text{vol}( {X})\), where \( {X}\) denote the set of two copies of the elements of \(X\) in \(G^A\).
Proof. Let \(V_G=\{v_1,v_2,\ldots,v_n\}\), and without loss of generality, let \(X=\{v_1,v_2,\ldots,v_k\}\) where \(k\leq n\). Then \( {X}=\{v'_1,v'_2,\ldots,v'_k,v''_1,v''_2,\ldots,v''_k\}\). the mixed volume of \( {X}\) given by \[\text{vl}(X)=\sum\limits_{i=1}^{k}(2d(v_i)+d^+(v_i)+d^-(v_i)),\] and the volume of \( {X}\) is \[\text{vol}( {X})= \sum\limits_{v\in {X}}d(v)=\sum\limits_{i=1}^{k}(d(v'_i)+d(v''_i)).\]
Since \(d(v'_i)=d(v_i)+d^+(v_i)\) and \(d(v''_i)=d(v_i)+d^-(v_i)\) for \(i=1,,2,\ldots,k\), the result follows. ◻
Let \(G\) be a mixed graph. For \(X\subseteq V_G\), we denote the complement of \(X\) in \(G\) by \(X^c=V_G\setminus X\).
Theorem 5.16. Let \(G\) be a simple mixed graph on \(n\) vertices, having at least one edge or one arc, and let \(X,Y\subseteq V_G\). Then we have
(i) \(\left|2e(X,Y)+a(X,Y)-\frac{\text{vl}(X)\text{vl}(Y)}{4e(G)+2a(G)}\right|\leq \hat{ {\nu}}(G)\sqrt{\text{vl}(X)\text{vl}(Y)}\);
(ii) \(\left|2e(X,Y)+a(X,Y)-\frac{\text{vl}(X)\text{vl}(Y)}{4e(G)+2a(G)}\right|\leq \hat{ {\nu}}(G)\frac{\sqrt{\text{vl}(X)\text{vl}(Y)\text{vl}(X^c)\text{vl}(Y^c)}}{4e(G)+2a(G)}\),
where \(\hat{ {\nu}}(G)=\underset{i\neq 2n}{\max}|1-\hat{ {\nu}}_i(G)|\).
Proof. Let \( {X}\) (resp. \( {Y}\)) denote the set of two copies of the elements of \(X\) (resp. \(Y\)) in \(G^A\). Then \( {X}^c\) (resp. \( {Y}^c\)) is the set of two copies of the elements of \(X^c\) (resp. \(Y^c\)) in \(G^A\). Since \(e( {X}, {Y})=2e(X,Y)+a(X,Y)\), \(\text{vol}(V_{G^A})=\text{vl}(V_G)=4e(G)+2a(G)\) and \(\hat{ {\nu}}_i(G)=\hat{\nu}_i(G)\) for \(i=1,2,\ldots,2n\), result follows from Lemma 5.15 and [6, Theorem 5.1 and 5.2]. ◻
As a direct consequence of Theorem 5.16, we get the next result.
Corollary 5.17. Let \(G\) be a simple mixed graph on \(n\) vertices, and let \(X\subseteq V_G\). Then we have the following.
(i) \(\left|2e(X,X)+a(X,X)-\frac{(\text{vl}(X))^2}{4e(G)+2a(G)}\right|\leq \hat{ {\nu}}(G)\frac{\text{vl}(X)\text{vl}(X^c)}{4e(G)+2a(G)}\leq \hat{ {\nu}}(G)\text{vl}(X)\);
(ii) If \(G\) is \(r\)-regular, then \(\left|2e(X,X)+a(X,X)-\frac{r|X|^2}{n}\right|\leq 2r\hat{ {\nu}}(G)|X|\).
Definition 5.18. Let \(G\) be a uniconnected mixed graph. For each distinct pairs of vertices \(u,v\in V_G\), we define the distance between \(u\) and \(v\), denoted by \(d_G(u,v)\) as \[d_G(u,v)=\min\{d_1(u,v),d_2(u,v),d_3(u,v),d_4(u,v)\},\] and \(d_G(u,u)=0\), where
(i) \(d_1(u,v)\) denotes the minimum length of a shortest path joining \(u\) and \(v\) in \(G\) if such a path exists, and the length of a shortest alternating path from \(u\) to \(v\) that contains an even number of arcs, with the first arc in the forward direction, provided such a path exists;
(ii) \(d_2(u,v)\) denotes the length of a shortest alternating path from \(u\) to \(v\) that contains an number of arcs, with the first arc is in the forward direction;
(iii) \(d_3(u,v)\) denotes the length of a shortest alternating path from \(u\) to \(v\) that contains an odd number of arcs, with the first arc is in the backward direction;
(iv) \(d_4(u,v)\) denotes the minimum of the length of a shortest path joining \(u\) and \(v\) in \(G\) if it exists, and the length of a shortest alternating path from \(u\) to \(v\) that contains an even number of arcs and, with the first arc is in the backward direction, provided such a path exists.
Definition 5.19. Let \(G\) be a uniconnected mixed graph. For \(X,Y\subseteq V_G\), the distance between \(X\) and \(Y\), denoted by \(d(X,Y)\), is defined as \[d(X,Y)=\min\{d_G(u,v)\mid u\in X\text{ and }v\in Y\}.\]
Lemma 5.20. Let \(G\) be a mixed graph, and let \(X,Y\subseteq V_G\). Then we have \(d(X,Y)=d( {X}, {Y})\), where \( {X}\) (resp. \( {Y}\)) denote the set of two copies of the elements of \(X\) (resp. \(Y\)) in \(G^A\).
Proof. Suppose \(X\cap Y\neq \emptyset\). Then there exists \(v\in X\cap Y\). Since \(d_G(v,v)=0\), we have \(d(X,Y)=0\). moreover, \(v',v''\in {X}\cap {Y}\), where \(v'\) and \(v''\) are two copies of \(v\) in \(G^A\). Since \(d(v',v')=d(v'',v'')=0\), we have \(d( {X}, {Y})=0\).
Now, suppose \(X\cap Y= \emptyset\). Then we have \( {X}\cap {Y}= \emptyset\). We can write \(d(X,Y)=\min A\), where \(A=\{d_1(u,v),d_2(u,v),d_3(u,v),d_4(u,v)\mid u\in X\text{ and }v\in Y\}\). Let \(B=\{d(u,v)\mid u\in {X}\text{ and }v\in {Y}\}\). Then \(d( {X}, {Y})=\min B\). For \(u\in X\) and \(v\in Y\), we have the following relationships between the distances: \(d_1(u,v)=d(u',v')\), \(d_2(u,v)=d(u',v'')\), \(d_3(u,v)=d(u'',v')\) and \(d_4(u,v)=d(u'',v'')\), where \(u',u''\in {X}\) (resp. \(v',v''\in {Y}\)) are two copies of \(u\) (resp. \(v\)) in \(G^A\). From this, it is clear that \(A=B\). Therefore, \(\min A=\min B\). ◻
Theorem 5.21. Let \(G\) be a simple uniconnected mixed graph on \(n\) vertices. For \(X,Y\subseteq V_G\), we have \[d(X,Y)\leq \left\lceil\frac{\cosh^{-1} \sqrt{\frac{\text{vl}(X^c)\text{vl}(Y^c)}{\text{vl}(X)\text{vl}(Y)}}}{\cosh^{-1} \frac{\hat{ {\nu}}_{1}(G)+\hat{ {\nu}}_{2n-1}(G)}{\hat{ {\nu}}_{1}(G)-\hat{ {\nu}}_{2n-1}(G)}}\right\rceil.\]
Proof. Let \( {X}\) (resp. \( {Y}\)) denote the set of two copies of the elements of \(X\) (resp. \(Y\)) in \(G^A\). Then we have \( {X}^c\) (resp. \( {Y}^c\)) is the set of two copies of the elements of \(X^c\) (resp. \(Y^c\)) in \(G^A\). Since \(\hat{ {\nu}}_1(G)=\hat{\nu}_1(G)\) and \(\hat{ {\nu}}_{2n-1}(G)=\hat{\nu}_{2n-1}(G)\), result follows from Lemmas 5.15, 5.20 and[6, Theorem 3.3]. ◻
Theorem 5.22. Let \(G\) be a simple, uniconnected mixed graph on \(n\) vertices. For \(X_i\subset V_G, i=1,2,\ldots,k\) we have (i) \(\underset{i\neq j}{\min}~d(X_i,X_j)\leq \underset{i\neq j}{\max}\left\lceil\frac{\log \sqrt{\frac{\text{vl}X_i^c\text{vl}X_j^c}{\text{vl}X_i\text{vl}X_j}}}{\log \frac{1}{1-\hat{ {\nu}}_{2n-k+1}(G)}}\right\rceil\) if \(1-\hat{ {\nu}}_{2n-k+1}(G)\geq \hat{ {\nu}}_{1}(G)-1\);
(ii) \(\underset{i\neq j}{\min}~d(X_i,X_j)\leq \underset{i\neq j}{\max}\left\lceil\frac{\log \sqrt{\frac{\text{vl}X_i^c\text{vl}X_j^c}{\text{vl}X_i\text{vl}X_j}}}{\log \frac{\hat{ {\nu}}_{1}(G)+\hat{ {\nu}}_{2n-k+1}(G)}{\hat{ {\nu}}_{1}(G)-\hat{ {\nu}}_{2n-k+1}(G)}}\right\rceil\) if \(\hat{ {\nu}}_{2n-k+1}(G)\neq \hat{ {\nu}}_{1}(G)\);
(iii) \(\underset{i\neq j}{\min}~d(X_i,X_j)\leq \underset{1\leq j<k}{\min}\underset{i\neq j}{\max}\left\lceil\frac{\log \sqrt{\frac{\text{vl}X_i^c\text{vl}X_j^c}{\text{vl}X_i\text{vl}X_j}}}{\log \frac{\hat{ {\nu}}_{j+1}(G)+\hat{ {\nu}}_{2n-k+j-1}(G)}{\hat{ {\nu}}_{j+1}(G)-\hat{ {\nu}}_{2n-k+j-1}(G)}}\right\rceil\) if \(\hat{ {\nu}}_{2n-k+j-1}(G)\neq \hat{ {\nu}}_{j+1}(G)\).
Proof. For \(i=1,2,\ldots,k\), let \( {X}_i\) denote the set of two copies of the elements of \(X_i\) in \(G^A\). Then \( {X}_i^c\) is the set of two copies of the elements of \(X_i^c\) in \(G^A\). From Lemma 5.20, we have \(d(X_i,X_j)=d( {X}_i, {X}_j)\) for \(i,j\in\{1,2,\ldots,k\}\). Since \(\hat{ {\nu}}_i(G)=\hat{\nu}_i(G)\) for \(i=1,2,\ldots,2n\), result follows from Lemma 5.15 and [6, Theorem 3.10, 3.11, 3.12]. ◻
By taking \(k=2\) in part (ii) of Theorem 5.22, we get the next result.
Corollary 5.23. Let \(G\) be a simple uniconnected mixed graph on \(n\) vertices. For \(X,Y\subset V_G\), we have \[d(X,Y)\leq \left\lceil\frac{\log \sqrt{\frac{\text{vl}(X^c)\text{vl}(Y^c)}{\text{vl}(X)\text{vl}(Y)}}}{\log \frac{\hat{ {\nu}}_{1}(G)+\hat{ {\nu}}_{2n-1}(G)}{\hat{ {\nu}}_{1}(G)-\hat{ {\nu}}_{2n-1}(G)}}\right\rceil.\]
It is shown in this paper that the integrated Laplacian matrix, integrated signless Laplacian matrix and normalized integrated Laplacian matrix associated for a mixed graph are respectively identical to the Laplacian matrix, signless Laplacian matrix and normalized Laplacian matrix of the associated graph. This allowed us to use the spectra of these matrices as a means to connect the structural properties of the mixed graph with those of the associated graph.
Some spectral graph theoretic results for simple graphs, utilized in this paper, can be extended to graphs containing loops and/or multiple edges. Consequently, the results presented here, initially proved for simple mixed graphs using these spectral graph theoretic results for simple graphs, can be generalized to mixed graphs with multiple loops, multiple directed loops, multiple edges, and/or multiple arcs.
The first author is supported by the University Grants Commission (UGC), Government of India under the fellowship UGC NET-SRF (NTA Ref. No.: 211610155238).