Inverse of $\alpha$-Hermitian Adjacency Matrix of a Unicyclic Bipartite Graph

Alomari, Omar; Abudayah, Mohammad; AbuGhneim, Omar

doi:10.61091/jcmcc119-07

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 119
Pages: 63-73

Research article

Inverse of $α$ -Hermitian Adjacency Matrix of a Unicyclic Bipartite Graph

^¹, ^², ^³

¹College of Engineering and Technology, American University of the Middle East, Kuwait

²School of Basic Sciences and Humanities, German Jordanian University, Madaba 11180, Jordan

³Department of Mathematics, Faculty of Science, The University of Jordan, Amman, Jordan

Received: 09/01/2024
Accepted: 15/03/2024
Published: 31/03/2024

Copyright Link
License

Abstract

Let $X$ be bipartite mixed graph and for a unit complex number $α$ , $H_{α}$ be its $α$ -hermitian adjacency matrix. If $X$ has a unique perfect matching, then $H_{α}$ has a hermitian inverse $H_{α}^{- 1}$ . In this paper we give a full description of the entries of $H_{α}^{- 1}$ in terms of the paths between the vertices. Furthermore, for $α$ equals the primitive third root of unity $γ$ and for a unicyclic bipartite graph $X$ with unique perfect matching, we characterize when $H_{γ}^{- 1}$ is $\pm 1$ diagonally similar to $γ$ -hermitian adjacency matrix of a mixed graph. Through our work, we have provided a new construction for the $\pm 1$ diagonal matrix.

Keywords: Mixed graphs,

α

-Hermitian adjacency matrix, Inverse matrix, Bipartite mixed graphs, Unicyclic bipartite mixed graphs, Perfect matching

1. Introduction

A partially directed graph $X$ is called a mixed graph, the undirected edges in $X$ are called digons and the directed edges are called arcs. Formally, a mixed graph $X$ is a set of vertices $V (X)$ together with a set of undirected edges $E_{0} (D)$ and a set of directed edges $E_{1} (X)$ . For an arc $x y \in E_{1} (X)$ , $x$ (resp. $y$ ) is called initial (resp. terminal) vertex. The graph obtained from the mixed graph $X$ after stripping out the orientation of its arcs is called the underlying graph of $X$ and is denoted by $Γ (X)$ .

A collection of digons and arcs of a mixed graph $X$ is called a perfect matching if they are vertex disjoint and cover $V (X)$ . In other words, perfect matching of a mixed graph is just a perfect matching of its underlying graph. In general, a mixed graph may have more than one perfect matching. We denote the class of bipartite mixed graphs with a unique perfect matching by $H$ . In this class of mixed graphs the unique perfect matching will be denoted by $M$ . For a mixed graph $X \in H$ , an arc $e$ (resp. digon) in $M$ is called matching arc (resp. matching digon) in $X$ . If $D$ is a mixed subgraph of $X$ , then the mixed graph $X ∖ D$ is the induced mixed graph over $V (X) ∖ V (D)$ .

Studying a graph or a digraph structure through properties of a matrix associated with it is an old and rich area of research. For undirected graphs, the most popular and widely investigated matrix in literature is the adjacency matrix. The adjacency matrix of a graph is symmetric, and thus diagonalizable and all of its eigenvalues are real. On the other hand, the adjacency matrix of directed graphs and mixed graphs is not symmetric and its eigenvalues are not all real. Consequently, dealing with such matrix is very challenging. Many researchers have recently proposed other adjacency matrices for digraphs. For instance in [1], the author investigated the spectrum of $A A^{T}$ , where $A$ is the traditional adjacency matrix of a digraph. The author called them non negative spectrum of digraphs. In [2], authors proved that the non negative spectrum is totally controlled by a vertex partition called common out neighbor partition. Authors in [3] and in [4] (independently) proposed a new adjacency matrix of mixed graphs as follows:

For a mixed graph $X$ , the hermitian adjacency matrix of $X$ is a $| V | \times | V |$ matrix $H (X) = [h_{u v}]$ , where

$h_{u v} = {\begin{cases} 1 & if u v \in E_{0} (X), \\ i & if u v \in E_{1} (X), \\ - i & if v u \in E_{1} (X), \\ 0 & otherwise . \end{cases}$

This matrix has many nice properties. It has real spectrum and interlacing theorem holds. Beside investigating basic properties of this hermitian adjacency matrix, authors proved many interesting properties of the spectrum of $H$ . This motivated Mohar in [5] to extend the previously proposed adjacency matrix. The new kind of hermitian adjacency matrices, called $α$ -hermitian adjacency matrices of mixed graphs, are defined as follows: Let $X$ be a mixed graph and $α$ be the primitive $n^{t h}$ root of unity $e^{\frac{2 π}{n} i}$ . Then the $α$ hermitian adjacency matrix of $X$ is a $| V | \times | V |$ matrix $H_{α} (X) = [h_{u v}]$ , where

$h_{u v} = {\begin{cases} 1 & if u v \in E_{0} (D), \\ α & if u v \in E_{1} (D), \\ \bar{α} & if v u \in E_{1} (D), \\ 0 & otherwise . \end{cases}$

Clearly the new kind of hermitian adjacency matrices of mixed graphs is a natural generalization of the old one for mixed graphs and even for the graphs. As we mentioned before these adjacency matrices ( $H_{i} (X)$ and $H_{α} (X)$ ) are hermitian and have interesting properties. This paved the way to more a facinating research topic much needed nowadays.

For simplicity when dealing with one mixed graph $X$ , then we write $H_{α}$ instead of $H_{α} (X)$ .

The smallest positive eigenvalue of a graph plays an important role in quantum chemistry. Motivated by this application, Godsil in [6] investigated the inverse of the adjacency matrix of a bipartite graph. He proved that if $T$ is a tree graph with perfect matching and $A (T)$ is its adjacency matrix then, $A (T)$ is invertabile and there is ${1, - 1}$ diagonal matrix $D$ such that $D A^{- 1} D$ is an adjacency matrix of another graph. Many of the problems mentioned in [6] are still open. Further research appeared after this paper that continued on Godsil’s work see [7], [8] and [9].

In this paper we study the inverse of $α$ -hermitian adjacency matrix $H_{α}$ of unicyclic bipartite mixed graphs with unique perfect matching $X$ . Since undirected graphs can be considered as a special case of mixed graphs, the out comes in this paper are broader than the work done previously in this area. We examine the inverse of $α$ -hermitian adjacency matricies of bipartite mixed graphs and unicyclic bipartite mixed graphs. Also, for $α = γ$ , the primative third root of unity, we answer the traditional question, when $H_{α}^{- 1}$ is ${\pm 1}$ diagonally similar to an $α$ -hermitian adjacency matrix of mixed graph. To be more precise, for a unicyclic bipartite mixed graph $X$ with unique perfect matching we give full characterization when there is a ${\pm 1}$ diagonal matrix $D$ such that $D H_{γ}^{- 1} D$ is an $γ$ -hermitian adjacency matrix of a mixed graph. Furthermore, through our work we introduce a construction of such diagonal matrix $D$ . In order to do this, we need the following definitions and theorems:

Definition 1. [10] Let $X$ be a mixed graph and $H_{α} = [h_{u v}]$ be its $α$ -hermitian adjacency matrix.

$X$ is called elementary mixed graph if for every component $X^{'}$ of $X$ , $Γ (X^{'})$ is either an edge or a cycle $C_{k}$ (for some $k \geq 3$ ).
For an elementary mixed graph $X$ , the rank of $X$ is defined as $r (X) = n - c,$ where $n = | V (X) |$ and $c$ is the number of its components. The co-rank of $X$ is defined as $s (X) = m - r (X)$ , where $m = | E_{0} (X) \cup E_{1} (X) |$ .
For a mixed walk $W$ in $X$ , where $Γ (W) = r_{1}, r_{2}, \dots r_{k}$ , the value $h_{α} (W)$ is defined as $h_{α} (W) = h_{r_{1} r_{2}} h_{r_{2} r_{3}} h_{r_{3} r_{4}} \dots h_{r_{k - 1} r_{k}} \in {α^{n}}_{n \in Z}$

Recall that a bijective function $η$ from a set $V$ to itself is called permutation. The set of all permutations of a set $V$ , denoted by $S_{V}$ , together with functions composition form a group. Finally recall that for $η \in S_{V}$ , $η$ can be written as composition of transpositions. In fact the number of transpositions is not unique. But this number is either odd or even and cannot be both. Now, we define $s g n (η)$ as $(- 1)^{k}$ , where $k$ is the number of transposition when $η$ is decomposed as a product of transpositions. The following theorem is well known as a classical result in linear algebra.

Theorem 1. If $A = [a_{i j}]$ is an $n \times n$ matrix then $d e t (A) = \sum_{η \in S_{n}} s g n (η) a_{1, η (1)} a_{2, η (2)} a_{3, η (3)} \dots a_{n, η (n)} .$

2. Inverse of $α$ -Hermitian Adjacency Matrix of a Bipartite Mixed Graph

In this section, we investigate the invertibility of the $α$ -hermitian adjacency matrix of a bipartite mixed graph $X$ . Then we find a formula for the entries of its inverse based on elementary mixed subgraphs. This will lead to a formula for the entries based on the type of the paths between vertices. Using Theorem 1, authors in [10] proved the following theorem:

Theorem 2. (Determinant expansion for $H_{α}$ ) [10] Let $X$ be a mixed graph and $H_{α}$ its $α$ -hermitian adjacency matrix, then $d e t (H_{α}) = \sum_{X^{'}} (- 1)^{r (X^{'})} 2^{s (X^{'})} R e (\prod_{C} h_{α} (\vec{C})),$ where the sum ranges over all spanning elementary mixed subgraphs $X^{'}$ of $X$ , the product ranges over all mixed cycles $C$ in $X^{'}$ , and $\vec{C}$ is any mixed closed walk traversing $C$ .

Now, let $X \in H$ and $M$ is the unique perfect matching in $X$ . Then since $X$ is bipartite graph, $X$ contains no odd cycles. Now, let $C_{k}$ be a cycle in $X$ , then if $C_{k} \cap M$ is a perfect matching of $C_{k}$ then, $M Δ C_{k} = M ∖ C_{k} \cup C_{k} ∖ M$ is another perfect matching in $X$ which is a contradiction. Therefore there is at least one vertex of $C_{k}$ that is matched by a matching edge not in $C_{k}$ . This means if $X \in H$ , then $X$ has exactly one spanning elementary mixed subgraph that consist of only $K_{2}$ components. Therefore, Using the above discussion together with Theorem 2 we get the following theorem:

Theorem 3. If $X \in H$ and $H_{α}$ is its $α$ -hermitian adjacency matrix then $H_{α}$ is non singular.

Now, Let $X$ be a mixed graph and $H_{α}$ be its $α$ -hermitian adjacency matrix. Then, for invertible $H_{α}$ , the following theorem finds a formula for the entries of $H_{α}^{- 1}$ based on elementary mixed subgraphs and paths between vertices. The proof can be found in [11].

Theorem 4. Let $X$ be a mixed graph, $H_{α}$ be its $α$ -hermitian adjacency matrix and for $i \neq j$ , $ρ_{i \to j} = {P_{i \to j} : P_{i \to j} is a mixed path from the vertex i to the vertex j}$ . If $det (H_{α}) \neq 0$ , then $\begin{aligned} _{i j} = & \frac{1}{det (H_{α})} \sum_{P_{i \to j} \in ρ_{i \to j}} (- 1)^{| E (P_{i \to j}) |} h_{α} (P_{i \to j}) \sum_{X^{'}} (- 1)^{r (X^{'})} 2^{s (X^{'})} R e (\prod_{C} h_{α} (\vec{C})), \end{aligned}$ where the second sum ranges over all spanning elementary mixed subgraphs $X^{'}$ of $X ∖ P_{i \to j}$ , the product is being taken over all mixed cycles $C$ in $X^{'}$ and $\vec{C}$ is any mixed closed walk traversing $C$ .

This theorem describes how to find the non diagonal entries of $H_{α}^{- 1}$ . In fact, the diagonal entries may or may not equal to zero. To observe this, lets consider the following example:

Example 1. Consider the mixed graph $X$ shown in Figure 1 and let $α = e^{\frac{π}{5} i}$ . The mixed graph $X$ has a unique perfect matching, say $M$ , and this matching consists of the set of unbroken arcs and digons. Further $M$ is the unique spanning elementary mixed subgraph of $X$ . Therefore, using Theorem 2 $d e t [H_{α}] = (- 1)^{8 - 4} 2^{4 - 4} = 1.$ So, $H_{α}$ is invertible. To calculate $[H_{α}^{- 1}]_{i i}$ , we observe that $[H_{α}^{- 1}]_{i i} = \frac{d e t ((H_{α})_{(i, i)})}{d e t (H_{α})} = d e t ((H_{α})_{(i, i)}),$ where $(H_{α})_{(i, i)}$ is the matrix obtained from $H_{α}$ by deleting the $i^{t h}$ row and $i^{t h}$ column, which is exactly the $α$ -hermitian adjacency matrix of $X ∖ {i}$ . Applying this on the mixed graph, one can deduce that the diagonal entries of $H_{α}^{- 1}$ are all zeros except the entry $(H_{α}^{- 1})_{11}$ . In fact it can be easily seen that the mixed graph $X ∖ {1}$ has only one spanning elementary mixed subgraph. Therefore, $[H_{α}^{- 1}]_{11} = d e t ((H_{α})_{(1, 1)}) = (- 1)^{7 - 2} 2^{6 - 5} R e (α) = - 2 R e (α) .$

Figure 1: Mixed Graph $X$ where $H_{α}^{- 1}$ has Nonzero Diagonal Entry

The following theorem shows that if $X$ is a bipartite mixed graph with unique perfect matching, then the diagonal entries of $H_{α}^{- 1}$ should be all zeros.

Theorem 5. Let $X \in H$ and $H_{α}$ be its $α$ -hermitian adjacency matrix. Then, for every vertex $i \in V (X)$ , $(H_{α}^{- 1})_{i i} = 0$ .

Proof. Observing that $X$ is a bipartite mixed graph with a unique perfect matching, and using Theorem 3, we have $H_{α}$ is invertable. Furthermore, $(H_{α}^{- 1})_{i i} = \frac{det ((H_{α})_{(i, i)})}{det (H_{α})} .$

Note that $(H_{α})_{(i, i)}$ is the $α$ -hermitian adjacency matrix of the mixed graph $X ∖ {i}$ . However $X$ has a unique perfect matching, therefore $X ∖ {i}$ has an odd number of vertices. Hence $X ∖ {i}$ has neither a perfect matching nor an elementary mixed subgraph and thus $det ((H_{α})_{(i, i)}) = 0$ .

Now, we investigate the non diagonal entries of the inverse of the $α$ -hermitian adjacency matrix of a bipartite mixed graph, $X \in H$ . In order to do that we need to characterize the structure of the mixed graph $X ∖ P$ for every mixed path $P$ in $X$ . To this end, consider the following theorems:

Theorem 6. [12]Let $M$ and $M^{'}$ be two matchings in a graph $G$ . Let $H$ be the subgraph of $G$ induced by the set of edges $M Δ M^{'} = (M ∖ M^{'}) \cup (M^{'} ∖ M) .$ Then, the components of $H$ are either cycles of even number of vertices whose edges alternate in $M$ and $M^{'}$ or a path whose edges alternate in $M$ and $M^{'}$ and end vertices unsaturated in one of the two matchings.

Corollary 1. For any graph $G$ , if $G$ has a unique perfect matching then $G$ does not contain alternating cycle.

Definition 2. Let $X$ be a mixed graph with unique perfect matching. A path $P$ between two vertices $u$ and $v$ in $X$ is called co-augmenting path if the edges of the underlying path of $P$ alternates between matching edges and non-matching edges where both first and last edges of $P$ are matching edges.

Corollary 2. Let $G$ be a bipartite graph with unique perfect matching $M$ , $u$ and $v$ are two vertices of $G$ . If $P_{u v}$ is a co-augmenting path between $u$ and $v$ , then $G ∖ P_{u v}$ is a bipartite graph with unique perfect matching $M ∖ P_{u v}$ .

Proof. The part that $M ∖ P_{u v}$ is being a perfect matching of $G ∖ P_{u v}$ is obvious. Suppose that $M^{'} \neq M ∖ P_{u v}$ is another perfect matching of $G ∖ P_{u v}$ . Using Theorem 6, $G ∖ P_{u v}$ consists of an alternating cycles or an alternating paths, where its edges alternate between $M ∖ P_{u v}$ and $M^{'}$ . If all $G ∖ P_{u v}$ components are paths, then $G ∖ P_{u v}$ has exactly one perfect matching, which is a contradiction. Therefore, $G ∖ P_{u v}$ contains an alternating cycle say $C$ . Since $P_{u v}$ is a co-augmenting path, we have $M^{'} \cup (P_{u v} \cap M)$ is a perfect matching of $G$ . Therefore $G$ has more than one perfect matching, which is a contradiction.

Theorem 7. Let $G$ be a bipartite graph with unique perfect matching $M$ , $u$ and $v$ are two vertices of $G$ . If $P_{u v}$ is not a co-augmenting path between $u$ and $v$ , then $G ∖ P_{u v}$ does not have a perfect matching.

Proof. Since $G$ has a perfect matching, then $G$ has even number of vertices. Therefore, when $P_{u v}$ has an odd number of vertices, $G ∖ P_{u v}$ does not have a perfect matching.

Suppose that $P_{u v}$ has an even number of vertices. Then, $P_{u v}$ has a perfect matching $M$ . Therefore if $G ∖ P_{u v}$ has a perfect matching $M^{'}$ , then $M \cup M^{'}$ will form a new perfect matching of $G$ . This contradicts the fact that $G$ has a unique perfect matching.

Now, we are ready to give a formula for the entries of the inverse of $α$ -hermitian adjacency matrix of bipartite mixed graph $X$ that has a unique perfect matching. This characterizing is based on the co-augmenting paths between vertices of $X$ .

Theorem 8. Let $X$ be a bipartite mixed graph with unique perfect matching $M$ , $H_{α}$ be its $α$ -hermitian adjacency matrix and $ℑ_{i \to j} = {P_{i \to j} : P_{i \to j} \small{ is a co-augmenting mixed path from the vertex } i to the vertex j} .$ Then

$(H_{α}^{- 1})_{i j} = {\begin{cases} \sum_{P_{i \to j} \in ℑ_{i \to j}} (- 1)^{\frac{| E (P_{i \to j}) | - 1}{2}} h_{α} (P_{i \to j}) & if i \neq j, \\ 0 & if i = j . \end{cases}$

Proof. Using Theorem 4, $[H_{α}^{- 1}]_{i j} = \frac{1}{det (H_{α})} \sum_{P_{i \to j} \in ρ_{i \to j}} [(- 1)^{| E (P_{i \to j}) |} h_{α} (P_{i \to j}) \sum_{X^{'}} (- 1)^{r (X^{'})} 2^{s (X^{'})} R e (\prod_{C} h_{α} (\vec{C}))],$ where the second sum ranges over all spanning elementary mixed subgraphs of $X ∖ P_{i \to j}$ . The product is being taken over all mixed cycles $C$ of $X^{'}$ and $\vec{C}$ is any mixed closed walk traversing $C$ .

First, using Theorem 7 we observe that if $P_{i \to j}$ is not a co-augmenting path then $X ∖ P_{i \to j}$ does not have a perfect matching. Therefore, the term corresponds to $P_{i \to j}$ contributes zero. Thus we only care about the co-augmenting paths. According to Corollary 2, for any co-augmenting path $P_{i \to j}$ from the vertex $i$ to the vertex $j$ we get $X ∖ P_{i \to j}$ has a unique perfect matching, namely $M \cap E (X ∖ P_{i \to j})$ . Using Corollary 1, $X ∖ P_{i \to j}$ does not contain an alternating cycle. Thus $X ∖ P_{i \to j}$ contains only one spanning elementary mixed subgraph which is $M ∖ P_{i \to j}$ . So,

$[H_{α}^{- 1}]_{i j} = \frac{1}{det (H_{α})} \sum_{P_{i \to j} \in ℑ_{i \to j}} (- 1)^{| E (P_{i \to j}) |} h_{α} (P_{i \to j}) (- 1)^{V (X ∖ P_{i \to j}) - k},$ where $k$ is the number of components of the spanning elementary mixed subgraph of $X ∖ P_{i \to j}$ . Observe that $| V (X ∖ P_{i \to j}) | = n - (| E (P_{i \to j}) | + 1)$ , $k = \frac{n - (| E (P_{i \to j}) | + 1)}{2}$ and $det (H_{α}) = (- 1)^{\frac{n}{2}}$ , we get the result.

3. Inverse of $γ$ -hermitian Adjacency Matrix of a Unicyclic Bipartite Mixed Graph

Let $γ$ be the third root of unity $e^{\frac{2 π}{3} i}$ . Using Theorem 8, $h_{α} (P_{i \to j}) \in {α^{i}}_{i = 1}^{n}$ plays a central rule in finding the entries of $H_{α}^{- 1}$ and since the third root of unity has the property $γ^{i} \in {1, γ, \bar{γ}}$ we focus our study in this section on $α = γ$ . The property that $α^{i} \in {\pm 1, \pm α, \pm \bar{α}}$ is not true in general. To illustrate, consider the mixed graph shown in Figure 2 and let $α = e^{\frac{π}{5} i}$ . Using Theorem 1 we get $H_{05}^{- 1} = e^{\frac{3 π}{5} i}$ which is not from the set ${\pm 1, \pm α, \pm \bar{α}}$ .

In this section, we are going to answer the classical question whether the inverse of $γ$ -hermitian adjacency matrix of a unicyclic bipartite graph is ${1, - 1}$ diagonally similar to a hermitian adjacency matrix of another mixed graph or not. Consider the mixed graph shown in Figure 2. Then, obviously entries of $H_{γ}^{- 1}$ are from the set ${0, \pm 1, \pm γ, \pm \bar{γ}}$ .

Figure 2: Unicycle Bipartite Mixed Graph with Unique Perfect Matching and $4$ Pegs

Another thing we should bear in mind is the existence of ${1, - 1}$ diagonal matrix $D$ such that $D H_{γ} D$ is $γ$ -adjacency matrix of another mixed graph. In the mixed graph $X$ in Figure 2, suppose that $D = d i a g {d_{0}, d_{1}, \dots, d_{9}}$ is ${1, - 1}$ diagonal matrix with the property $D H_{γ} D$ has all entries from the set ${0, γ, \bar{γ}}$ . Then, $\begin{array}{l} d_{0} d_{5} = 1, \\ d_{0} d_{9} = - 1, \\ d_{9} d_{7} = - 1, \\ d_{5} d_{7} = - 1, \end{array}$ which is impossible. Therefore, such diagonal matrix $D$ does not exist. To discuss the existence of the diagonal matrix $D$ further, let $G$ be a bipartite graph with unique perfect matching. Define $X_{G}$ to be the mixed graph obtained from $G$ by orienting all non matching edges. Clearly for $α \neq 1$ and $α \neq - 1$ changing the orientation of the non matching edges will change the $α$ -hermitian adjacency matrix. For now lets restrict our study on $α = - 1$ . Using Theorem 8 one can easily get the following observation.

Observation 1. Let $G$ be a bipartite mixed graph with unique perfect matching $M$ , $H_{- 1}$ be the $- 1$ -hermitian adjacency matrix of $X_{G}$ and $ℑ_{i \to j} = {P_{i \to j} : P_{i \to j} is a co-augmenting mixed path from the vertex i to the vertex j in X_{G}} .$ One can use Theorem 8 to get

$(H_{- 1}^{- 1})_{i j} = {\begin{cases} | ℑ_{i \to j} | & if i \neq j, \\ 0 & if i = j . \end{cases}$

So, the question we need to answer now is when $A (G)$ and $H_{- 1} (X_{G})$ are diagonally similar. To this end, let $G$ be a bipartite graph with a unique perfect matching and $u \in V (G)$ . Then for a walk $W = u = r_{1}, r_{2}, r_{3}, \dots, r_{k}$ in $G$ , define a function that assign the value $f_{W} (j)$ for the $j^{t h}$ vertex of $W$ as follows: $f_{W} (1) = 1$ and $f_{W} (j + 1) = {\begin{cases} - f_{W} (j) & if r_{j} r_{j + 1} is unmatching edge in G, \\ f_{W} (j) & if r_{j} r_{j + 1} is matching edge in G, \end{cases}$

See Figure 3.

Figure 3: The Values of $f_{W}$ where $W$ is the Closed Walk Starting from $0$

Since any path from a vertex $u$ to itself consist of pairs of identical paths and cycle, we get the following remark:

Remark 1. Let $G$ be bipartite graph with unique perfect matching and $F (u) = {f_{W} (u) : W is aclosed walk in G starting at u} .$ then, $| F (u) | = 1$ if and only if the number of unmatching edges in each cycle of $G$ is even.

Finally, let $G$ be a bipartite graph with unique perfect matching and suppose that each cycle of $G$ has an even number of unmatched edges. For a vertex $u \in V (G)$ define the function $w : V (G) \to {1, - 1}$ by $w (v) = f_{W} (v), where W is apath from u to v .$

Definition 3. Suppose that $G$ is bipartite graph with unique perfect matching and every cycle of $G$ has even number of unmatched edges. Suppose further $V (G) = {v_{1}, v_{2}, \dots, v_{n}}$ and $u \in V (G)$ . Define the matrix $D_{u}$ by $D_{u} = d i a g {w (v_{1}), w (v_{2}), \dots, w (v_{n})}$ .

Theorem 9. Suppose $G$ is a bipartite graph with unique perfect matching and every cycle of $G$ has an even number of unmatched edges. Then for every $u \in V (G)$ , we get $D_{u} A (G) D_{u} = H_{- 1} (X_{G})$ .

Proof. Note that, for $x, y \in V (G)$ , we have $(D_{u} A (G) D_{u})_{x y} = d_{x} a_{x y} d_{y}$ . Using the definition of $D_{u}$ we get,

$d_{x} d_{y} = {\begin{cases} - 1 & if x y is an unmatching edge in G, \\ 1 & if x y is a matching edge in G, \\ 0 & otherwise. \end{cases}$ Therefore, $(D_{u} A (G) D_{u})_{x y} = (H_{- 1})_{x y}$ .

Now we are ready to discuss the inverse of $γ$ -hermitian adjacency matrix of unicyclic mixed graph. Let $X$ be a unicyclic bipartite graph with unique perfect matching. An arc or digon of $X$ is called a peg if it is a matching arc or digon and incident to a vertex of the cycle in $X$ . Since $X$ is unicyclic bipartite graph with unique perfect matching, $X$ has at least one peg. Otherwise the cycle in $X$ will be alternate cycle, and thus $X$ has more than one perfect matching which contradicts the assumption. Since each vertex of the cycle incident to a matching edge and $| V (X) |$ is even, $X$ should contain at least two pegs. The following theorem will deal with unicyclic bipartite mixed graphs $X \in H$ with more than two pegs.

Theorem 10. Let $X$ be a unicyclic bipartite graph with unique perfect matching. If $X$ has more than two pegs, then between any two vertices of $X$ there is at most one co-augmenting path.

Proof. Let $ρ_{1}, ρ_{2}$ and $ρ_{3}$ be three pegs in $X$ , $u, v \in V (D)$ , $C$ is the unique cycle in $X$ and suppose there are two co-augmenting paths between $u$ and $v$ , say $P$ and $P^{'}$ . Since $X$ is unicyclic, we have $V (C) \subset P \cup P^{'}$ ,

Case 1: $E (P) \cup E (P^{'})$ does not contain any of the pegs. Then, if $v$ is the $X$ cycle vertex incident to $ρ_{1}$ then, $v$ is not matched by an edge in the cycle, which means one of $P$ or $P^{'}$ is not co-augmenting path, which contradicts the assumption.
Case 2: $(E (P) \cup E (P^{'})$ contain pegs. Then, $(E (P) \cup E (P^{'})$ should contain at most two pegs, suppose that $ρ_{1}$ and $v$ is the vertex of $X$ cycle that incident to $ρ_{1}$ . Then, $v$ belongs to either $P$ or $P^{'}$ , again since $ρ_{1}$ is a matched edge, $v$ is not matched by the cycle edges which means one of $P$ or $P^{'}$ is not co-augmenting path. which contradicts the assumption.

Corollary 3. Let $X$ be a unicycle bipartite mixed graph with unique perfect matching. If $X$ has more than two pegs, then

$(H_{α}^{- 1})_{i j} = {\begin{cases} (- 1)^{\frac{| E (P_{i \to j}) | - 1}{2}} h_{α} (P_{i \to j}) & if P_{i \to j} is a co-augmenting path from i to j, \\ 0 & Otherwise. \end{cases}$
If the cycle of $X$ contains even number of unmatching edges, then for any vertex $u \in V (X)$ , $D_{u} H_{γ}^{- 1} (X) D_{u}$ is $γ$ -hermitian adjacency matrix of a mixed graph.

Proof. Part one is obvious using Theorem 8 together with Theorem 11.

For part two, we observe that $γ^{i} \in {1, γ, \bar{γ}}$ . Therefore all $H_{γ}^{- 1} (X)$ entries are from the set ${\pm 1, \pm γ, \pm \bar{γ}}$ . Also the negative signs in $A (Γ (X))^{- 1}$ and in $H_{γ}^{- 1}$ appear at the same position. Which means $D_{u} H_{γ}^{- 1} D_{u}$ is $γ$ -hermitian adjacency matrix of a mixed graph if and only if $D_{u} A (Γ (X)) D_{u}$ is adjacency matrix of a graph. Finally, Theorem 1 ends the proof.

Now we will take care of unicycle graph with exactly two pegs. Using the same technique of the proof of Theorem 11, one can show the following:

Theorem 11. Let $D$ be a unicyclic bipartite graph with unique perfect matching and exactly two pegs $ρ_{1}$ and $ρ_{2}$ . Then for any two vertices of $D$ , $u$ and $v$ , if there are two co-augmenting paths from the vertex $u$ to the vertex $v$ , then $ρ_{1}$ and $ρ_{2}$ are edges of the two paths.

Let $X$ be a unicyclic bipartite mixed graph with unique perfect matching and exactly two pegs, and let $u v$ and $u^{'} v^{'}$ be the two pegs of $X$ where $v$ and $v^{'}$ are vertices of the cycle of $X$ . We, denote the two paths between $v$ and $v^{'}$ by $F_{v \to v^{'}}$ and $F_{v \to v^{'}}^{c}$ .

Theorem 12.

Let $X$ be a unicyclic bipartite mixed graph with unique perfect matching and exactly two pegs and let $C$ be the cycle of $X$ . If there are two coaugmenting paths between the vertex $x$ and the vertex $y$ , then

$(H_{α}^{- 1})_{x y} = (- 1)^{\frac{| E (P_{x \to y}) | - 1}{2}} \frac{h_{α} (P_{x \to v}) h_{α} (P_{y \to v^{'}})}{h_{α} (F_{v \to v^{'}})} [(- 1)^{m + 1} h_{α} (C) + 1],$ where $F_{v \to v^{'}}$ is chosen to be the part of the path $P_{x \to y}$ in the cycle $C$ and $C$ is of size $2 m$ .

Proof. Suppose that $P_{x \to y}$ and $Q_{x \to y}$ are the paths between the vertices $x$ and $y$ , using theorem 8 we have

$(H_{α}^{- 1})_{x y} = (- 1)^{\frac{| E (P_{x \to y}) | - 1}{2}} h_{α} (P_{x \to y}) + (- 1)^{\frac{| E (Q_{x \to y}) | - 1}{2}} h_{α} (Q_{x \to y}) .$

Now, using Theorem 11, $P_{x \to y}$ $(Q_{x \to y})$ can be divided into three parts $P_{x \to v}$ , $F_{v \to v^{'}}$ and $P_{v^{'} \to y}$ (resp. $Q_{x \to v} = P_{x \to v}, F_{v \to v^{'}}^{c}$ and $Q_{v^{'} \to y} = P_{v^{'} \to y}$ ).
Observe that the number of unmatched edges in $F_{v \to v^{'}}$ is $k_{1} = \frac{| E (F_{v \to v^{'}}) | + 1}{2}$ and the number of unmatched edges in $F_{v \to v^{'}}^{c}$ is $k_{2} = m - \frac{| E (F_{v \to v^{'}}) | + 1}{2} + 1$ we get

$(H_{α}^{- 1})_{x y} = (- 1)^{k} h_{α} (P_{x \to v}) h_{α} (P_{v \to y}) ((- 1)^{k_{1}} h_{α} (F_{v \to v^{'}}) + (- 1)^{k_{2}} h_{α} (F_{v \to v^{'}}^{c})),$ where $k = \frac{| E (P_{x \to v}) | + | E (P_{v^{'} \to y}) |}{2} - 1$ .

Note here $\bar{h_{α} (F_{v \to v^{'}})} h_{α} (F_{v \to v^{'}}^{c}) = h_{α} (C)$ , therefore, $(H_{α}^{- 1})_{x y} = (- 1)^{\frac{| E (P_{x \to y}) | - 1}{2}} \frac{h_{α} (P_{x \to v}) h_{α} (P_{y \to v^{'}})}{h_{α} (F_{v \to v^{'}})} [(- 1)^{m + 1} h_{α} (C) + 1] .$

Theorem 13. Let $X$ be a unicyclic bipartite mixed graph with unique perfect matching and $H_{γ}$ be its $γ$ -hermitian adjacency matrix. If $X$ has exactly two pegs, then $H_{γ}^{- 1}$ is not $\pm 1$ diagonally similar to $γ$ -hermitian adjacency matrix of a mixed graph.

Proof. Let $x x^{'}$ and $y y^{'}$ be the two pegs of $X$ , where $x^{'}$ and $y^{'}$ are vertices of the cycle $C$ of $X$ . Then, using Theorem 12 we have $(H_{γ}^{- 1})_{x y} = (- 1)^{\frac{| E (P_{x \to y}) | - 1}{2}} \frac{h_{γ} (P_{x \to x^{'}}) h_{γ} (P_{y \to y^{'}})}{h_{γ} (F_{x^{'} \to y^{'}})} [(- 1)^{m + 1} h_{γ} (C) + 1],$ where $F_{x^{'} \to y^{'}}$ is chosen to be the part of the path $P_{x \to y}$ in the cycle $C$ and $C$ is of size $2 m$ . Suppose that $D = d i a g {d_{v} : v \in V (X)}$ is a ${\pm 1}$ diagonal matrix with the property that $D H_{γ}^{- 1} D$ is $γ$ -hermitian adjacency matrix of a mixed graph.

Case 1: Suppose $m$ is even say $m = 2 r$ .

Observe that $(- 1)^{m + 1} h_{γ} (C) + 1 = 1 - h_{γ} (C)$ . If $h_{γ} (C) \in {1, γ, γ^{2}}$ , then $1 - h_{γ} (C) \notin {\pm 1, \pm γ, \pm γ^{2}}$ and so $H_{γ}^{- 1}$ is not $\pm 1$ diagonally similar to $γ$ -hermitian adjacency matrix of a mixed graph. Thus we only need to discuss the case when $h_{γ} (C) = 1$ . To this end, suppose that $h_{γ} (C) = 1$ . Then $(H_{γ}^{- 1})_{x y} = 0$ . Since the length of $C$ is $4 r$ , we have the number of unmatching edges (number of matching edges) in $C$ is $\frac{4 r + 2}{2}$ (resp. $\frac{4 r - 2}{2}$ ). Since the number of unmatching edges in $C$ is odd, there is a coaugmenting path $F_{x \to y}$ from $x$ to $y$ that contains odd number of unmatching edges and another coaugmenting path $F_{x \to y}^{c}$ with even number of unmatching edges. Now, let $o^{'} o$ ( $e^{'} e$ ) be any matching edges in the path $F_{x \to y}$ (resp. $F_{x \to y}^{c}$ ). Then, without loss of generality we may assume that there is a coaugmenting path between $x$ and $e$ , $x$ and $o$ (and hence there is a co-augmenting path between $y$ and $o^{'}$ , $y$ and $e^{'}$ ). Now, if $d_{x} d_{y} = 1$ then
- $(D H_{γ}^{- 1} D)_{x o} = (- 1)^{k} d_{x} h_{γ} (P_{x \to o}) d_{o}$
- $(D H_{γ}^{- 1} D)_{y o^{'}} = (- 1)^{k^{'}} d_{y} h_{γ} (P_{y \to o^{'}}) d_{o^{'}}$
Observe that $k + k^{'}$ is odd number, we have $d_{o} d_{o^{'}} = - 1$ . This contradict the fact that for every matching edge $g g^{'}$ , $d_{g} d_{g^{'}} = 1$ . The case when $d_{x} d_{y} = - 1$ is similar to the above case but with considering the path $F_{x \to y}^{c}$ instead of $F_{x \to y}$ and the vertex $e$ instead of $o$ .
Case 2:Suppose $m$ is odd say $2 r + 1$ . Then $(H_{γ}^{- 1})_{x y} = (- 1)^{\frac{| E (P_{x \to y}) | - 1}{2}} \frac{h_{α} (P_{x \to v}) h_{α} (P_{y \to v^{'}})}{h_{α} (F_{v \to v^{'}})} [h_{α} (C) + 1] .$ Therefore, $(H_{γ}^{- 1})_{x y} = (- 1)^{\frac{| E (P_{x \to y}) | - 1}{2}} \frac{h_{α} (P_{x \to v}) h_{α} (P_{y \to v^{'}})}{h_{α} (F_{v \to v^{'}})} {\begin{cases} - γ & if h_{α} (C) = γ^{2}, \\ - γ^{2} & if h_{α} (C) = γ, \\ 2 & if h_{α} (C) = 1. \end{cases}$ Obviously, when $h_{α} (C) = 1$ , $H_{γ}^{- 1}$ is not $\pm 1$ diagonally similar to $γ$ -hermitian adjacency matrix of a mixed graph. Thus, the cases we need to discuss here are when $h_{α} (C) = γ$ and $h_{α} (C) = γ^{2}$ .

Since $m$ is odd, then $C$ contains an even number of unmatched edges. Therefore, either both paths between $x$ and $y$ , $F_{x \to y}$ and $F_{x \to y}^{c}$ , contain odd number of unmatching edges or both of them contains even number of unmatching edges.

To this end, suppose that both of the paths $F_{x \to y}$ and $F_{x \to y}^{c}$ contain odd number of unmatched edges. Then, $(H_{γ}^{- 1})_{x y} \in {γ^{i}}_{i = 0}^{2}$ , which means $d_{x} d_{y} = 1$ . Finally, let $v^{'} v$ be any matching edge in $F_{x \to y}$ where $P_{x \to v}$ and $P_{v^{'} \to y}$ are coaugmenting paths, then obviously $d_{v} d_{v^{'}} = 1$ . But one of the coaugmenting paths $P_{x \to v}$ and $P_{v^{'} \to y}$ should contain odd number of unmatching edges and the other one should contain even number of unmatched edges. Which means $d_{x} d_{v} d_{v^{'}} d_{y} = - 1$ . This contradicts the fact that $d_{v} d_{v^{'}} = 1$ .

In the other case, when both $F_{x \to y}$ and $F_{x \to y}^{c}$ contain even number of unmatching edges, one can easily deduce that $d_{x} d_{y} = - 1$ and using same technique we can get another contradiction.

Note that Corollary 3 and Theorem 13 give a full characterization of a unicyclic bipartite mixed graph with unique perfect matching where the inverse of its $γ$ -hermitian adjacency matrix is ${\pm 1}$ diagonally similar to $γ$ -hermitian adjacency matrix of a mixed graph. We summarize this characterization in the following corollary.

Theorem 14. Let $X$ be a unicyclic bipartite mixed graph with unique perfect matching and $H_{γ}$ its $γ$ -hermitian adjacency matrix. Then, $H_{γ}^{- 1}$ is $\pm 1$ diagonally similar to $γ$ -hermitian adjacency matrix if and only if $X$ has more than two pegs and the cycle of $X$ contains even number of unmatching edges.

Acknowledgments

We thank the anonymous referees for their helpful comments.

References:

Jovanovic, I.M., 2017. Non-negative spectrum of a digraph. Ars Math. Contemp., 12(1), pp.167-182.
Alomari, O., Abudayah, M. and Sander, T., 2020. The non-negative spectrum of a digraph. Open Mathematics, 18(1), pp.22-35.
Guo, K. and Mohar, B., 2017. Hermitian adjacency matrix of digraphs and mixed graphs. Journal of Graph Theory, 85(1), pp.217-248.
Liu, J. and Li, X., 2015. Hermitian-adjacency matrices and Hermitian energies of mixed graphs. Linear Algebra and its Applications, 466, pp.182-207.
Mohar, B., 2020. A new kind of Hermitian matrices for digraphs. Linear Algebra and its Applications, 584, pp.343-352.
Deza, M.M., Deza, E., Deza, M.M. and Deza, E., 2014. Distances in Physics and Chemistry. Encyclopedia of Distances, pp.487-519.
Pavlíková, S. and Jediný, J.K., 1990. On the inverse and the dual index of a tree. Linear and Multilinear Algebra, 28(1-2), pp.93-109.
McLeman, C. and McNicholas, E., 2014. Graph invertibility. Graphs and Combinatorics, 30, pp.977-1002.
Akbari, S. and Kirkland, S.J., 2007. On unimodular graphs. Linear Algebra and its Applications, 421(1), pp.3-15.
Abudayah, M., Alomari, O. and Sander, T., 2021. Hermitian adjacency matrices of mixed graphs. arXiv preprint arXiv:2103.16969.
Abudayah, M., Alomari, O., and AbuGhneim, O. A. 2020, ‘Inverse of $α$ -Hermitian Adjacency Matrix of Mixed Tree Graphs’. Journal of Graph Theory, 18(1), pp. 22-35.
Clark, J. and Holton, D.A., 1991. A first look at graph theory. World Scientific.

[1] Jovanovic, I.M., 2017. Non-negative spectrum of a digraph. Ars Math. Contemp., 12(1), pp.167-182.

[2] Alomari, O., Abudayah, M. and Sander, T., 2020. The non-negative spectrum of a digraph. Open Mathematics, 18(1), pp.22-35.

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

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

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

[6] Deza, M.M., Deza, E., Deza, M.M. and Deza, E., 2014. Distances in Physics and Chemistry. Encyclopedia of Distances, pp.487-519.

[7] Pavlíková, S. and Jediný, J.K., 1990. On the inverse and the dual index of a tree. Linear and Multilinear Algebra, 28(1-2), pp.93-109.

[8] McLeman, C. and McNicholas, E., 2014. Graph invertibility. Graphs and Combinatorics, 30, pp.977-1002.

[9] Akbari, S. and Kirkland, S.J., 2007. On unimodular graphs. Linear Algebra and its Applications, 421(1), pp.3-15.

[10] Abudayah, M., Alomari, O. and Sander, T., 2021. Hermitian adjacency matrices of mixed graphs. arXiv preprint arXiv:2103.16969.

[11] Abudayah, M., Alomari, O., and AbuGhneim, O. A. 2020, ‘Inverse of $α$ -Hermitian Adjacency Matrix of Mixed Tree Graphs’. Journal of Graph Theory, 18(1), pp. 22-35.

[12] Clark, J. and Holton, D.A., 1991. A first look at graph theory. World Scientific.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing