EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 3, 2022, 1090-1097 ISSN 1307-5543 – ejpam.com Published by New York Business Global On the Cospectrality of Hermitian Adjacency Matrices of Mixed Graphs Omar Alomari1,∗, Mohammad Abudayah1, Manal Ghanem2 1 School of Basic Sciences and Humanities, German Jordanian University, Amman, Jordan 2 Department of Mathematics, School of Science, The University of Jordan, Amman, 11942, Jordan Abstract. A mixed graph D is a graph that can be obtained from a graph by orienting some of its edges. Let α be a primitive nth root of unity, then the α−Hermitian adjacency matrix of a mixed graph is defined to be the matrix Hα = [hrs] where hrs = α if rs is an arc in D, hrs = α if sr is an arc in D, hrs = 1 if sr is a digon in D and hrs = 0 otherwise. In this paper we study the cospectrality of the Hermitian adjacency matrix of a mixed graph. 2020 Mathematics Subject Classifications: 05C20, 05C50, 15A30 Key Words and Phrases: Adjacency Matrix, Mixed graphs, Hermitian Matrix, Spectrum, Cospectrality 1. Introduction In this paper we consider graphs without loops or multiple edges. A mixed graph D is a set of vertices V (D) together with a set of edges E(D) ⊂ V (D) × V (D) where, (u, v) ∈ E(D) does not always imply (v, u) ∈ E(D). An edge (u, v) of a mixed graph D is called oriented (resp. digon) if only one of (u, v) and (v, u) belongs to E(D) (resp. both of (u, v) and (v, u) belong to E(D) ). For simplicity, through this paper arcs and digon will be denoted by uv instead of (u, v). The underlying graph of a mixed graph D, denoted by Γ(D), is the graph obtained from D after unorienting all of its edges. A cycle, (resp. a walk, a path) of a mixed graph D is just a cycle (resp. a walk, a path) of the underlying graph of D. A mixed graph D is called weakly connected if its underlying graph is connected. One of the important branches of algebraic graph theory is the study of graphs and digraphs with respect to some graph matrix and its spectrum. For undirected graphs researchers focused on two kinds of adjacency matrices, the traditional adjacency matrix and the Laplacian adjacency matrix. On the other hand for directed graphs ( digraphs ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i3.4422 Email addresses: omar.alomari@gju.edu.jo (Omar Alomari), mohammad.abudayah@gju.edu.jo (Mohammad Abudayah), m.ghanem@ju.edu.jo (Manal Ghanem) https://www.ejpam.com 1090 © 2022 EJPAM All rights reserved. O. Alomari, M. Abudayah, M. Ghanem / Eur. J. Pure Appl. Math, 15 (3) (2022), 1090-1097 1091 ) the traditional adjacency matrix is not symmetric in general. Therefore, it is very challenging to deal with such matrix. Recently, many researchers have proposed other Hermitian adjacency matrices of mixed graphs. For example in [2] and in [1] authors studied the singular values of the traditional adjacency matrix of a mixed graph D, in these papers it was very clear that the singular values of a mixed graph are related to the common out neighbors between vertices. Coincidentally, Guo and Mohar in [3] defined an interesting Hermitian adjacency matrix of mixed graphs as follows: For a mixed graph D, the i−Hermitian adjacency matrix of D is a |V | × |V | matrix Hi(D) = [huv], where huv =  1 if uv is a digon in D, i if uv is an arc in D, −i if vu is an arc in D, 0 otherwise. In [3] many interesting spectral properties of Hi(D) have been demonstrated. Mohar in [5] extended the previously proposed adjacency matrix. In the new kind of Hermitian adjacency matrices the complex number i is replaced with the sixth root of unity ω = e π 3 i. The new kind of Hermitian adjacency matrices is calledω−Hermitian adjacency matrices. In this paper Mohar discussed many cases with general complex unit number eiθ instead of ω. To be more precise, the definition of the general Hermitian adjacency matrix of a mixed graph, some times called α-Hermitian adjacency matrix, was as follows: Let α = eiθ and D be a mixed graph. Then, the α-Hermitian adjacency matrix of D is a |V | × |V | matrix Hα(D) = [huv], where huv =  1 if uv is a digon in D, α if uv is an arc in D, α if vu is an arc in D, 0 otherwise. In fact, these definitions can be considered as special cases of the complex unit gain graphs which was defined in [4]. The fact that these adjacency matrices (Hi and Hα) are Hermitian has opened a hot research topic nowadays. Finally, let D be a mixed graph, Hα be its α-Hermitian adjacency matrix of D and u, v, r be three vertices of D. Then the α-weight of a walk W in D, say W = r1, r2, ..., rk, is defined to be the product of the entries of Hα corresponds to the values of the arcs and digons in W . To be more formal, hα(W ) = hr1r2hr2r3 . . . hrk−1rk . Furthermore, if Wuv is a walk from the vertex u to the vertex v and Wvr is a walk from the vertex v to the vertex r, then by the walk WuvWvr we mean the walk from the vertex v to the vertex r through the walk Wuv then the walk Wvr. By Rev(Wuv) we mean the walk from the vertex v to the vertex u through the walk Wuv. O. Alomari, M. Abudayah, M. Ghanem / Eur. J. Pure Appl. Math, 15 (3) (2022), 1090-1097 1092 2. Cospectrality of Hermitian Adjacency Matrices of Mixed Graphs Studying cospectrality of two graphs is one of the classical field of algebraic graph theory. However, the cospectrality of mixed graphs can be divided into two studies: The first one is studying the cospectrality of two different mixed graphs with same unit complex number α (α-cospectrality), and the second one is studying cospectrality of same mixed graphs but with different values of α. In this section we study when the Hermitian adjacency matrices (with respect to different values of α) of a weakly connected mixed graph are cospectral. Also we study when α- spectrum of a weakly connected mixed graphD is completely determined by the underlying graph of the mixed graph D. To this end, fix a weakly connected mixed graph D and a unit complex number α. Let u, v ∈ V (D) and let W be a walk in D, say W = (u = r1, ..., rk = v). We now recursively define a function that assigns a value fα W (j) to the jth vertex (i.e. to rj) along W by fα W (1) = 1, fα W (j + 1) =  fα W (j) if rjrj+1 is a digon in D αfα W (j) if rjrj+1 is an arc in D ᾱfα W (j) if rj+1rj is an arc in D  for j = 1, ..., k. We shall write fα W (∗) for the final value fα W (k), see Figure 1 Figure 1: The values of the function fα W (j) along the walk W = 1234567 Let D be a mixed graph, u ∈ V (D), then for a vertex v ∈ V (D) define the α-store of the vertex v with respect to the vertex u by: Tα u(v) = {fα W (∗) : W is a walk from u to v}, and the store size of the vertex v with respect to the vertex u by tαu(v) = |Tα u(v)|. Clearly 1 ∈ Tα u(u) and if D contains a cycle C of weight other than 1, then along any walk W that O. Alomari, M. Abudayah, M. Ghanem / Eur. J. Pure Appl. Math, 15 (3) (2022), 1090-1097 1093 contains C, the store of u will contain values other than 1. In fact, if α is the primitive nth root of unity, the weight of the cycle C is αr, and gcd(n, r) = 1 then the store of the vertex u will contain all powers of α. Theorem 1. Let D be a weakly connected mixed graph, u ∈ V (D) and Hα = [hij ] be its α-Hermitian adjacency matrix. Then the following statements are equivalent: (1) tαu(v) = 1 for a vertex v of D. (2) tαu(m) = 1 for every vertex m of D. (3) For every cycle C = (r1, r2, . . . , rk−1, r1) in D, the weight of C hα(C) = hr1r2hr2r3 . . . hrk−1r1 in Hα equals one. Proof. ((1)) → ((2)) Suppose that tαu(v) = 1 for a vertex v of D and let m be a vertex of D with tαu(m) > 1. Suppose further Wuv is a walk from u to v. Then, since tαu(m) > 1, there are two walks Wum and W ′ um from u to m with fα Wum (∗) ̸= fα W ′ um (∗). Now, consider the walk W = WumRev(W ′ um)Wuv, where Rev(W ′ um) is the walk from m to u through the walk W ′ um. Since fα Wum (∗) ̸= fα W ′ um (∗) we have: fα W(∗) = fWum(∗)fRev(W ′ um (∗)fWuv(∗) (1) ̸= fWuv(∗). (2) Therefore, tαu(v) > 1, which is a contradiction. ((2)) → ((3)) Suppose that C is a cycle in D and let v be a vertex of the cycle C. Then consider the closed walk W = PuvCvRev(Puv), where Puv is a path from u to v and Cv is the closed path from v to v along the cycle C. Then, using the definition of fα W (∗) we have, fα W(∗) = hα(Puv)hα(C)hα(Rev(Puv)) (3) = hα(C). (4) Finally, using the definition of fα W (∗) and the assumption that tαu(v) = 1 for every vertex v of D, we have hα(C) equals to 1. ((3)) → ((1)) Let W be a closed walk start from the initial vertex u. Then, W consists of a sequence of cycles {Ci}ni=1 and sequence of paths {Pj}mj=1. Further, using the assumption in (3) we have O. Alomari, M. Abudayah, M. Ghanem / Eur. J. Pure Appl. Math, 15 (3) (2022), 1090-1097 1094 fα W(∗) = n∏ i=1 hα(Ci) m∏ j=1 hα(Pj) m∏ j=1 hα(Rev(Pj)) (5) = n∏ i=1 hα(Ci) (6) = 1. (7) Therefore, tαu(u) = 1. The above theorem paved the way to the following definition. Definition 1. Let D be a weakly connected mixed graph and u be a vertex of D. Then, D is called an α-monostore graph if tαu(v) = 1 for a vertex v in D. Obviously, changing the initial vertex u of a mixed graph D will not change the store size of the vertices of D, but it may change the values in the store set of the vertices. Theorem 2. Let D be an α-monostore graph, Hα = [hst] be its α-Hermitian adjacency matrix and for a vertex u in D, ∆α = diag{tv : tv ∈ Tα u(v) and v ∈ V (D)}. Then, ∆αHα∆ ∗ α = A(Γ(D)) where A(Γ(D)) is the traditional adjacency matrix of the graph Γ(D). Proof. Since the matrix ∆α is a diagonal matrix, it is enough to prove that ∆αHα∆ ∗ α is a {0, 1}-matrix. To do this, suppose that rs is an arc in D, then (∆αHα∆ ∗ α)rs = trhrsts. Since rs is an arc in D and D is α-monostore mixed graph, ts = hrstr. Therefore, (∆αHα∆ ∗ α)rs = 1. Using the definition of fα W (∗), Theorem 1 and Theorem 2, any vertex of an α-monostore graph D can be used to construct ∆α. Also, Theorem 2 indicates that if D is an α- monostore mixed graph, then the orientation of D can be stored in a diagonal matrix ∆α. Definition 2. If D is an α-monostore graph, then a diagonal matrix ∆α that satisfies ∆αHα∆ ∗ α = A(Γ(D)) is called an orienting matrix of D. Corollary 1. If D is an α-monostore mixed graph then D is cospectral with its underlying graph. Corollary 2. If D is a tree mixed graph then the spectrum of D is completely determined by its underlying graph Γ(D). O. Alomari, M. Abudayah, M. Ghanem / Eur. J. Pure Appl. Math, 15 (3) (2022), 1090-1097 1095 Lemma 1. Let Hα be the α-Hermitian adjacency matrix of a mixed graph D, ∆ = diag(du : du ∈ C, u ∈ V (D) and |du| = 1) and K = [kuv] = ∆Hα∆ ∗. Then, for every cycle C in D the weight of the cycle C in Hα and in K are equal. Proof. Suppose that C = u1u2 . . . unu1 is a cycle inD. Then, observing that (∆Hα∆ ∗)uv = duhuvdv, we have hα(C) = hα(u1u2)hα(u2u3) . . . hα(unu1) (8) = du1hα(u1u2)du2du2hα(u2u3)du3 . . . dunhα(unu1)du1 (9) = k(C). (10) Example 1. Let D be the mixed graph shown in Figure 2a, α is the primitive third root of unity e 2π 3 i and Hα its α-Hermitian adjacency matrix. Obviously, the tree mixed subgraph T illustrated in the solid lines is α-monograph with the orienting matrix ∆α = diag(tv : tv ∈ T and v ∈ V (D)). Then, the matrix K = ∆αHα∆ ∗ α can be considered as the adjacency matrix of the complex weighted graph Dα (or the unit gain graph Dα , see[4]) shown in Figure 2b with weight 1 for each edge of the tree Γ(T ). Furthermore according to Lemma 1, the weight of the edge 53 in Dα, say k(53), equals to the weight of the fundamental cycle C53 = 32453 in Hα. To be more formal, k(53) = t5h53t3. But, t5 = t3h32h24h45 Therefore, k(53) = α2 = k(35) Similar calculations can be done to get, k(89) = α2. Therefore, the matrix K = ∆αHα∆ ∗ α is the adjacency matrix of the complex weighted graph Dα. The above example illustrates that, for every mixed graphD and a spanning mixed tree T of D, there is a complex weighted mixed graph D that is cospectral with the α-hermitian adjacency matrix of D. This idea will be used to prove some further results. Definition 3. Let D be a graph and α, γ are two unit complex numbers. If the α- Hermitian adjacency matrix and the γ-Hermitian adjacency matrix of D are cospectral, then D is called α− γ cospectral. Theorem 3. Let D be a mixed graph and α, γ be two unit complex numbers. If for all cycles C in D one of hα(C) = hγ(C) or hα(C) = hγ(C) is hold then D is α−γ cospectral. Proof. Suppose that T is a spanning tree of D, u is a vertex of D and ∆α (resp. ∆γ) is the α-orienting (resp. the γ-orienting) matrix of T . Then, ∆αHα(T )∆ ∗ α = ∆γHγ(T )∆ ∗ γ = A(Γ(T )) REFERENCES 1096 (a) The mixed graph D with the values of tv in the spanning tree T. (b) The complex weighted graph Dα with the weight of the edges Figure 2 which means that the matrices ∆αHα(D)∆∗ α ( resp. ∆γHγ(D)∆∗ γ) can be considered as a Hermitian adjacency matrices of the weight mixed graph Dα (resp. Dγ) with underlying graph Γ(D), all edges of the tree T have weight 1. Furthermore, suppose that rs is an edge in D that is not in T , and Crs be the fundamental cycle of D corresponding to rs. Then, using Lemma 1 we get that, the weight of rs in Dα (resp. Dγ) equals hα(Crs) (resp. hγ(Crs)). Therefore, either ∆αHα(D)∆∗ α = ∆γHγ(D)∆∗ γ or ∆αHα(D)∆∗ α = ∆γHγ(D)∆∗ γ , which means Hα(D) and Hγ(D) are cospectral. Corollary 3. Let D be a mixed graph and α, γ are unit complex numbers. If D is α- monostore mixed graph then D is γ − αγ cospectral. References [1] Mohammad Abudayah, Omar Alomari, and Torsten Sander. On the n-spectrum of oriented graphs. Open Mathematics, 18(1):486–495, 2020. [2] Omar Alomari, Mohammad Abudayah, and Torsten Sander. The non-negative spec- trum of a digraph. Open Mathematics, 18(1):22–35, 2020. [3] Krystal Guo and Bojan Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. Journal of Graph Theory, 85(1):217–248, 2017. REFERENCES 1097 [4] Ranjit Mehatari, M. Rajesh Kannan, and Aniruddha Samanta. On the adjacency matrix of a complex unit gain graph. Linear and Multilinear Algebra, 0(0):1–16, 2020. [5] B. Mohar. A new kind of hermitian matrices for digraphs. arXiv: Combinatorics, 2019.