Several properties of antiadjacency matrices of directed graphs

1.   Introduction

Let $D$ be a directed acyclic graph with $V\left(D\right) = \left\{{v}_{1}, {v}_{2}, \dots, {v}_{n}\right\}$. An adjacency matrix of a directed graph $D$ is a matrix $A = \left[{a}_{ij}\right]$ of order $n\times n.$ For $i\ne j$, if there is an arc from $i$ to $j$ then ${a}_{ij} = 1$, otherwise ${a}_{ij} = 0$. The matrix $B = J-A$ is called the antiadjacency matrix of a directed graph $D,$ where $J$ is the matrix of order $n\times n$ with all of those entries as one ^[1]. Note that the notion antiadjacency that we use in this paper is following the notion from Bapat ^[1], and it is different from the notion that is used by other researchers such as Wang et al. ^[2] who used the notion antiadjacency for an eccentricity matrix.

One interesting problem in graph theory is finding the Hamiltonian path or cycle. Some applications can be solved if we find a Hamiltonian path and cycle, as examples in the Traveling Salesman Problems and DNA sequencing. Bapat ^[1] showed that if $D$ is a directed acyclic graph and $B$ is its antiadjacency matrix, then $\mathrm{d}\mathrm{e}\mathrm{t}\left(B\right) = 1$ if $D$ has a Hamiltonian path and $\mathrm{d}\mathrm{e}\mathrm{t}\left(B\right) = 0$ for other cases. Thus, the antiadjacency matrix has very interesting results. We provide general results of characteristic polynomials of directed acyclic graphs.

Let us consider a directed graph in general. We prove several properties, such as its determinant characterizing when the directed graph has a Hamiltonian path, its characteristic polynomial has a special property that the coefficient of the characteristic polynomial has a relation with a number of directed paths with a certain length, and we also give some results for the energy of a directed graph. Some basic definitions used in this paper refer to these two textbooks ^[3,4].

2.   Known results

In this section, we give some known properties of the antiadjacency matrix. We start with properties on the determinant of antiadjacency and its relationship with the existence of the Hamiltonian path in the graph. Moreover, we also give the known results of the characteristic polynomials for arbitrary matrices. This property will be used to prove the property of antiadjacency of the characteristic polynomial of a directed acyclic graph.

Theorem 2.1 and the two corollaries show that the determinant of the antiadjacency matrix of the directed acyclic graph can characterize whether the graph has a Hamiltonian path or not.

Theorem 2.1. ^[1] Let $B$ be a $0-1$ matrix with order $n\times n$ such that ${b}_{ij} = 1$ if $i\ge j$. Then $\mathrm{det}\left(B\right)$ equals $1$ if ${b}_{12} = {b}_{23} = {b}_{34} = \dots = {b}_{\left(n-1\right)n} = 0$, and otherwise $\mathrm{det}\left(B\right) = 0$.

Corollary 2.1. ^[1] Let $D$ be a directed acyclic graph with $V\left(D\right) = \left\{{v}_{1}, {v}_{2}, \dots, {v}_{n}\right\}$. Let $B$ be the antiadjacency matrix of $D$. Then $\mathrm{det}\left(B\right) = 1$ if $D$ has a Hamiltonian path, and otherwise $\mathrm{det}\left(B\right) = 0$.

Corollary 2.2. ^[1] Let $G$ be a directed acyclic graph with $V\left(G\right) = \left\{{v}_{1}, {v}_{2}, \dots, {v}_{n}\right\}$. Let $B$ be the antiadjacency matrix of $G$. Then a principal minor of $B$ is $1$ if and only if the subgraph induced by the corresponding vertices has a Hamiltonian path.

Theorem 2.2. ^[5] If ${\lambda }^{n}+{c}_{1}{\lambda }^{n-1}+{c}_{2}{\lambda }^{n-2}+{c}_{3}{\lambda }^{n-3}+\dots +{c}_{n-1}\lambda +{c}_{n} = 0$ is the characteristic equation for ${A}_{n\times n}$ then

where $\left|{A}_{i}^{\left(j\right)}\right|$ are the $i\times i$ principal minors of $A$ and $j = \mathrm{1, 2}, 3, \dots, w$ where $w$ is the number of $i\times i$ principal minors of $A$.

The eigenvalues ${\lambda }_{1}, {\lambda }_{2}, \dots, {\lambda }_{n}$ of the antiadjacency matrix $B$ of directed graph $D$ are the roots of the characteristic polynomial

The spectrum of antiadjacency matrix $B$ of a directed acyclic graph $D$ is written as

Regarding the regular graphs, there are several results that are known. Examples are stated in the following theorems.

Theorem 2.3. ^[3] Let $G$ be a $k$ -regular graph, then $k$ is an adjacency eigenvalue of G.

Theorem 2.4. ^[6] If $G$ is a $k$ -regular graph, then the line graph $L\left(G\right)$ is a ($2k-2$) $-$ regular graph.

Note that the line graph $L\left(G\right)$ of a graph $G$ is the graph whose vertices can be assigned in one-to one correspondence with the edges of $G$ in such a way that two vertices of $L\left(G\right)$ are adjacent if and only if the corresponding edges of $G$ are adjacent.

Theorem 2.5. ^[3] Let $G$ be a $k$ -regular graph with $n$ vertices. Then

3.   Results

In this section, we give new results regarding four topics. In the first subsection, we discuss the determinants of several directed graphs. In the second subsection, we present properties related to the characteristic polynomial of a directed acyclic graph. In the next subsection, we are concerned about the regular directed graph, and in the last subsection, we discuss some early results of the antiadjacency energy graph.

3.1.   Determinant

From Section 2, we know some properties that show the value of the determinant of the directed acyclic graph is related to the existence of the Hamiltonian directed path. If there is an arc from $u$ to $v$, then $u$ is adjacent to $v$. Vertex $v$ is called the out-neighbor of $u$ and vertex $u$ is called the in-neighbor of $v.$ The set ${N}^{+}\left(v\right) = \left\{u\right|u\; \mathrm{i}\mathrm{s}\; \mathrm{o}\mathrm{u}\mathrm{t}-\mathrm{n}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{b}\mathrm{o}\mathrm{r}\; \mathrm{o}\mathrm{f}\; v\}$ and ${N}^{+}\left(v\right) = \left\{u\right|u\; \mathrm{i}\mathrm{s}\; \mathrm{i}\mathrm{n}-\mathrm{n}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{b}\mathrm{o}\mathrm{r}\; \mathrm{o}\mathrm{f}\; v\}.$

In the following theorem, we show one property that is sufficient for the determinant of the antiadjacency matrix, which has a value of 0.

Theorem 3.1. Let $D$ be a directed graph, and let $B\left(D\right)$ be the antiadjacency of $D$. If there are two vertices ${v}_{i}\ne {v}_{j}$ with ${N}^{+}\left({v}_{i}\right) = {N}^{+}\left({v}_{j}\right),$ $\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\; \mathrm{det}\left(B\left(D\right)\right) = 0$.

Proof. Let $D$ be a directed graph with $n$ vertices with two vertices ${v}_{i}\ne {v}_{j}$ with ${N}^{+}\left({v}_{i}\right) = {N}^{+}\left({v}_{j}\right)$ and $B\left(D\right)$ is an antiadjacency matrix of $D$. The property ${N}^{+}\left({v}_{i}\right) = {N}^{+}\left({v}_{j}\right)$ shows there are two identical rows of $B\left(D\right)$. It follows that rank $\left(B\left(D\right)\right) < n$. Thus, det $\left(B\right(D\left)\right) = 0$.

□

A similar result can be found for the inner neighbor as follows.

Theorem 3.2. Let $D$ be a directed graph, and let $B$ be the antiadjacency of $D$. If there are two vertices ${v}_{i}\ne {v}_{j}$ with ${N}^{-}\left({v}_{i}\right) = {N}^{-}\left({v}_{j}\right)$ $\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\; \mathrm{det}\left(B\left(D\right)\right) = 0$.

Next, we give values of the determinant of the antiadjacency matrix from several directed graphs with a directed cycle as its subgraph, including the cycle itself. Diwyacitta et al. proved the following theorem for directed cycle graph.

Theorem 3.3. ^[7] Let $B\left({C}_{n}\right)$ be the antiadjacency matrix of the directed cycle ${C}_{n},$ then $\mathrm{det}\left(B\left({C}_{n}\right)\right) = n-1$.

Now, we give the determinant of several directed cyclic graphs. We categorized the families of the graphs as type $T1.1$ (for directed cycle), type $T1.2$, type $T2.1$, type $T2.2$, and type $T2.3$. The cyclic directed graph is called type $T1.2$, $T1.2\left(n, k\right),$ if it contains a directed cycle with $n$ vertices, that has a directed cycle subgraph with $n-1$ vertices (not including the ${n}^{th}$ vertex), and has $k\le n-3$ arcs from the ${n}^{th}$ vertex to other vertices. Note that the $T1.1\left(n\right)$ type is a directed cycle.

Theorem 3.4. Let $D$ be a graph of type $T1.2(n, k)$ and $B\left(D\right)$ be its antiadjacency matrix. Then $\mathrm{det}\left(B\left(D\right)\right) = n-2$.

Proof. Let $D$ be a type $T1.2(n, k)$ and $B\left(D\right)$ is its antiadjacency matrix. The general form of the antiadjacency matrix of type $T1.2(n, k)$ is as follows:

where $J$ is a square with all entries equal to one, $I$ is an identity matrix, and $\boldsymbol{y}$ is a row vector with $\boldsymbol{y} = \left[{y}_{1}, {y}_{2}, \dots, {y}_{n-2}\right]$, ${y}_{i}$ is equal to $0$ if there are arcs from the ${n}^{th}$ vertex to ${i}^{th}$ vertex, for $i = \mathrm{2, 3}, \dots, n-2$ and equal to 1 for other cases.

We can obtain

Since $\left|\begin{array}{ccc}n-2 & \mathbf{0} & 0\\ \mathbf{1} & \left(-1\right)· {I}_{(n-2)\times (n-2)} & \mathbf{0}\\ 0 & \boldsymbol{y} & 1\end{array}\right|$ is a lower triangular matrix, then

The value of $2\left(n-2\right)$ is always even, then $\mathrm{det}\left(B\left(D\right)\right) = n-2$.

□

The second class of directed graph is a cyclic directed graph that contains a directed cycle with $n-1$ vertices (not including the ${n}^{th}$ vertex), and there is a vertex outside this cycle (name it as $v$), and we can add arc(s) from a vertex in this cycle to the center vertex $c$. Note that the vertex $c$ can be an isolated vertex. We this graph type into three types: type $T2.1, T2.2$, and $T2.3.$

A directed graph is called type 2.1 if the graph consists of the directed cycle ${C}_{n}$ and a center vertex so we can add $k$ arc(s) from any vertex in the cycle to the center vertex. The notation of this type of graph is $T2.1(n, k)$ where $n-1$ is the number of vertices in the cycle and $k$ is the number of additional arcs. Tables 3.1 and 3.2 show examples of type $T1.2$ and $T2.1$ of graphs.

The value of the determinant of a directed graph of types $T2.1(n, k)$ and $T2.2(n, k)$ depends on the number of additional arcs $( = k)$.

Theorem 3.5. Let $G$ be a directed graph of type $T2.1(n, k)$ with its antiadjacency matrix $B\left(G\right)$. Then $\mathrm{det}\left(B\left(G\right)\right) = k-1$.

Proof. Let $G$ be a graph of type $T2.1(n, k)$ and $B\left(G\right)$ be its antiadjacency matrix. The adjacency matrix of this type of graph is as follows:

where $B\left({C}_{n-1}\right)$ is the general form of the antiadjacency matrix of the graph with type $T1.1\left(n-1\right)$ or a directed cycle of order $n-1$, $\boldsymbol{x}$ is a column vector with size $n-1$ with $\boldsymbol{x} = {\left[{x}_{1}, {x}_{2}, \dots, {x}_{n-1}\right]}^{T}$. The value of ${x}_{i}$ is equal to $0$ if there is an arc from ${i}^{th}$ vertex to the center vertex, and equal to 1 for other cases. The number of 0 entries of $\boldsymbol{x}$ is equal to $k$.

Using the elementary row operation, we obtain

Since the value of $2\left(n-2\right)$ is always even, then $\mathrm{det}\left(B\left(G\right)\right) = k-1$.

□

A directed graph is called type 2.2 if the graph consists of the directed cycle ${C}_{n}$ and a center vertex, so we can add $k$ arc(s) from the center vertex to any vertex in the cycle. Note that the center vertex can be an isolated vertex. The notation of this type of graph is $T2.2\left(n, k\right),$ where $n$ is the number of vertices in the cycle and $k$ is the number of additional arcs. Examples of type $T2.2$ of graph can be found in Table 3.3.

In Theorem 3.6 below, it is shown that the determinant characteristic of the directed graph type $T2.2(n, k)$ is the same as the directed graph of type $T2.1(n, k)$. The determinant value is $k-1$, where $k$ is the number of arcs going to or coming from the center vertex.

Theorem 3.6. Let $D$ be a directed graph of type $T2.2(n, k)$ with an antiadjacency matrix $B\left(D\right)$. Then, $\mathrm{det}\left(B\left(D\right)\right) = k-1$.

Proof. Let $D$ be a directed graph of type $T2.2\left(n, k\right)$ and $B\left(D\right)$ be its antiadjacency matrix of $D$. With the similar way of vertex label as type $T2.1$, we have the general form of antiadjacency matrix of a directed graph with type $T2.2$ as follows:

with $B\left({C}_{n-1}\right)$ is a general form antiadjacency matrix of ${C}_{n-1}$ and $\boldsymbol{x}$ is a row vector of order $1\times (n-1)$ with $\boldsymbol{x} = \left[{x}_{1}, {x}_{2}, \dots, {x}_{n-1}\right]$, where ${x}_{i}$ is equal to $0$ if there is an arc from the ${n}^{th}$ vertex to ${i}^{th}$ vertex, and equal to $1$ for other cases. The number of entries 0 in the vector $\boldsymbol{x}$ is equal to $k$.

Using a similar way as in Theorem 3.5, we will obtain $\mathrm{det}\left(B\left(D\right)\right) = k-1.$

□

The last type of directed graph that is discussed is type $T2.3.$ This class of directed graph is a combination of t $\mathrm{y}\mathrm{p}\mathrm{e}T2.1(n, k)$ and $\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}\; T2.2(n, k)$. Thus, there is one arc from the ${(n-1)}^{th}$ vertex to the center vertex and $k$ arcs from center vertex to the ${i}^{th}$ vertices, with $1\le k\le n-3$. The in-degree of the center vertex is 1 (one), and its out-degree is $k$. Examples of type $T2.3$ of graph can be found in Table 3.4.

Theorem 3.7. Let $D$ be a directed graph of Type $T2.3(n, k)$ and $B\left(D\right)$ its adjacency matrix. Then, $\mathrm{det}\left(B\left(D\right)\right) = 0$.

Proof. Let $D$ be a directed graph of type $T2.3\left(n, k\right).$ Let $c$ be a center vertex, then | ${N}^{+}\left(c\right)| = k.$ Consider the ${\left(n-1\right)}^{th}$ vertex which is n the neighbor of $c.$ Then, ${N}^{-}\left(c\right) = {N}^{+}\left(x\right)$, where $x$ is the in-degree of the ${1}^{st}$ vertex of the cycle ${C}_{n-1}.$ Thus, according to Theorem 3.1, we have $\mathrm{det}\left(B\left(D\right)\right) = 0$.

□

3.2.   Polynomial characteristics of a directed acyclic graph

Many results on polynomial characteristics of the adjacency matrix of the directed acyclic graph have been found (see Bapat ^[1] and Brouwer and Haemerss ^[4] as examples). However, the characteristic polynomial of the antiadjacency matrix for a directed acyclic graph can give more information on the graph's structure, especially on the number of directed paths with a certain length in that directed graph as shown in Theorem 3.8. As an example, the adjacency characteristic polynomial of the directed path ${P}_{3}$ is $p\left(A\right({P}_{3}\left)\right) = {-\lambda }^{3}$. From this equation, we know that the number of vertices is 3. However, if we look at the antiadjacency of the directed path ${P}_{3},$ we have $p\left(B\right({P}_{3}\left)\right) = {\lambda }^{3}–2\lambda$. Thus, we have additional information, such as one directed path of length two. Stanley ^[8] has a similar result for the directed acyclic graph for the coefficient in det $(I+zC)$, where $C$ is a complement of the adjacency matrix of the graph, and $z$ is a coefficient.

Several results exist on characteristic polynomial of antiadjacency matrix of directed graphs ^[9,10,11,12]. However, the results are corollaries of the Theorem 3.8. There are also some results for undirected cases ^[13,14], but in this section, we consider only the directed graphs.

Theorem 3.8. Let $D$ be a directed acyclic graph with $V\left(D\right) = \left\{{v}_{1}, {v}_{2}, \dots, {v}_{n}\right\}$. Let $B$ be the antiadjacency matrix of $D$ whose antiadjacency matrix characteristic polynomial is

Then $\left|{b}_{i}\right|, i = \mathrm{1, 2}, 3, \dots, n$, equals the number of directed paths in $D$ where the length of directed paths is $i-1$.

Proof. By expanding the determinant of $\left(\lambda I-B\left(D\right)\right)$, it can be seen that,

By Theorem 2.2,

where the $\left|{B}_{i}^{\left(j\right)}\right|$ are the $i\times i$ principal minors of $B$ and $j = \mathrm{1, 2}, 3, \dots, w$ where $w$ is a number of $i\times i$ principal minors of $B$.

By Corollary 2.2, a principal minor of $B$ is $1$ if and only if the subgraph induced by the corresponding vertices of $D$ has a Hamiltonian path. Thus, the absolute values of the sum of nonsingular $i\times i$ principal minors of $B$ equal the number of the directed paths in $G$ with length $i-1$. Then, $\left|{b}_{i}\right|$, $i = \mathrm{1, 2}, 3, \dots, n$ equals the number of directed paths in $G$ is $i-1$.

□

If we have two disjoint directed acyclic graphs, we can easily find the characteristic polynomial of the disjoint union of these two directed graphs. Let $B$ be the antiadjacency matrix of $G$ whose antiadjacency matrix characteristic polynomial is

Then, by Theorem 3.1, we obtain the following results.

Corollary 3.1. If ${b}_{i}\ne 0,$ then ${b}_{j}\ne 0$ for all $j < i$ with $i = 2, 3, 4, \dots, n$. If ${c}_{n}\ne 0,$ then $D$ has a Hamiltonian directed path.

Corollary 3.2. If $i$ is the greatest index with ${b}_{i}\ne 0,$ then the algebraic multiplicity of eigenvalue equal 0 in the characteristic polynomial antiadjacency matrix of the acyclic directed graph $D$ is $n-i$.

Let ${D}_{1}$ be an acyclic directed graph with a characteristic polynomial antiadjacency matrix is ${p\left(B\left({D}_{1}\right), \lambda \right) = \lambda }^{{n}_{1}}+{b}_{1}{\lambda }^{{n}_{1}-1}+{b}_{2}{\lambda }^{{n}_{1}-2}+\dots +{b}_{r}{\lambda }^{{n}_{1}-r}$ with $r$ is the biggest index, ${b}_{r}\ne 0$. Let ${D}_{2}$ be an acyclic directed graph with a characteristic polynomial antiadjacency matrix is ${p\left(B\left({D}_{2}\right), \lambda \right) = \lambda }^{{n}_{2}}+{d}_{1}{\lambda }^{{n}_{2}-1}+{d}_{2}{\lambda }^{{n}_{2}-2}+\dots +{d}_{s}{\lambda }^{{n}_{2}-s}$ with $s$ is biggest index, ${d}_{s}\ne 0$. Then, the characteristic polynomial antiadjacency matrix of $D = {D}_{1}\cup {D}_{2}$ is $p\left(B\left(D\right), \lambda \right) = {\lambda }^{{n}_{1}+{n}_{2}}+\left({b}_{1}+{d}_{1}\right){\lambda }^{{n}_{1}+{n}_{2}-1}+\left({b}_{2}+{d}_{2}\right){\lambda }^{{n}_{1}+{n}_{2}-2}+\dots +\left({b}_{t}+{d}_{t}\right){\lambda }^{{n}_{1}+{n}_{2}-t}$ with $t = \mathrm{m}\mathrm{a}\mathrm{x}\left\{r, s\right\}$. This property can be generalized as follows.

Corollary 3.3. Let ${D}_{i}, i = \mathrm{1, 2}, 3, \dots, q$ be acyclic directed graphs with antidjacency matrix characteristic polynomial are $p\left(B\left({D}_{i}\right), \lambda \right) = {\lambda }^{{n}_{i}}+{b}_{i1}{\lambda }^{{n}_{i}-1}+{b}_{i2}{\lambda }^{{n}_{i}-2}+\dots +{b}_{i{r}_{i}}{\lambda }^{{n}_{i}-{r}_{i}}$ with ${r}_{i}$ are biggest index, ${b}_{i{r}_{i}}\ne 0, i = \mathrm{1, 2}, 3, \dots, q$. Then, the characteristic polynomial antidjacency matrix of $D = \bigcup _{i = 1}^{q}{D}_{i}$ is

with $p = \sum _{i = 1}^{q}{n}_{i}$ and $t = \mathrm{m}\mathrm{a}\mathrm{x}\{{r}_{i}\mid i = \mathrm{1, 2}, \dots, q\}$.

3.3.   Regular graph

In this subsection, we give several properties of regular directed graphs.

Theorem 3.9. Let $D$ be a $k$ -regular directed graph of order $n$. Let $A$ be an adjacency matrix for $D$ and ${\lambda }_{i}$ be an eigenvalue of $A$, for $i = 1, ..., n$, with ${\lambda }_{1} = k$. Let $B = J-A$ be the anti-adjacency matrix of $D$, then the eigenvalues of $B, \mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{d}\; \mathrm{b}\mathrm{y}{\lambda }^{*},$ are $n-k$ and $-{\lambda }_{i}$ for $i = 2, ..., n$. Thus, $p\left(B\right(D), {\lambda }^{*}) = ({\lambda }^{*}-(n-k\left)\right){\prod }_{i = 2}^{n}({\lambda }^{*}+{\lambda }_{i})$.

Proof. Let $D$ be a $k$ -regular directed graph of order $n$. Suppose that $A$ is the adjacency of $D$. Then $k$ is an eigenvalue of $A\mathbf{1} = k\mathbf{1}$ where 1 is an eigenvector of all ones. Let $B$ be the antiadjacency of the directed graph $D$. Then, $B\mathbf{1} = \left(J-A\right)\mathbf{1} = \left(n-k\right)I.$ Thus, $n-r$ is an eigenvalue of $B$ with eigenvector 1.

Let $\{\mathbf{1}, {v}_{2}, {v}_{3}, \dots, {v}_{n}\}$ be an orthogonal basis eigenvector of $A$. This means that ${v}_{i}$ is orthogonal to 1, for $i = 2, \dots, n.$ We have $B{v}_{i} = \left(J-A\right){v}_{i} = \left(J-{\lambda }_{i}\right){u}_{i} = -{\lambda }_{i}{u}_{i}$. Thus, the eigenvalues of $B$ are $n-k$ and $-{\lambda }_{i}$ for $i = 2, ..., n$. We conclude that $p\left(B\left(D\right), {\lambda }^{*}\right) = ({\lambda }^{*}-(n-k\left)\right){\prod }_{i = 2}^{n}({\lambda }^{*}+{\lambda }_{i})$.

□

We know that the Cayley graph of ${Z}_{n}, \mathrm{C}\mathrm{a}\mathrm{y}({Z}_{n}, S)$ with $S$ is the generator set is a regular directed graph. Thus, we have the following result.

Corollary 3.4. ^[15] If the adjacency matrix $A$ of Cay(${Z}_{n}, S$) has

3.4.   Energy of the graph

The energy of graph $G$, with notation $E\left(G\right)$, is the sum of all absolute values of its eigenvalues. Thus, if $A\left(G\right)$ is the adjacency matrix of $G$, with eigenvalues ${\lambda }_{1}, ..., {\lambda }_{n}$, then $E\left(G\right) = \sum _{i = 1}^{n}\left|{\lambda }_{i}\right|$ ^[16]. This concept is interesting because it has application in mathematical chemistry. The term 'energy' is inspired from quantum chemistry. We can define a similar term of an energy graph using an antiadjacency matrix for a directed graph. Thus, the antiadjacency-energy of a directed graph D is the sum of its eigenvalues, denoted by ${E}_{B}\left(D\right) = \sum _{1\le i\le n}\left|{\lambda }_{i}\right|$.

Theorem 3.10 has several results on the sum of eigenvalues and the quadratic eigenvalues of the directed acyclic digraph.

Theorem 3.10. Let $D$ be an acyclic directed graph with $n$ vertices and $m$ edges. Let $B$ be an anti-adjacency matrix of the graph $D$. If $p\left(B\right) = {\lambda }^{n}+{b}_{1}{\lambda }^{n-1}+{b}_{2}{\lambda }^{n-2}+\dots +{b}_{n-1}\lambda +{b}_{n} = 0$ is a characteristic equation of $B$ and ${\mathrm{\lambda }}_{1}, \dots, {\mathrm{\lambda }}_{\mathrm{n}}$ are the eigenvalues of $B$, then

Proof. According to Theorem 2.2, for $k = 1$, we obtain

From Theorem 3.8, we know that $\left|{b}_{1}\right|$ is the number of paths with length 0; this means the number of vertices, which is equal to $n.$ Then, $\sum _{1\le i\le n}{\lambda }_{i} = -{b}_{1} = \left|{b}_{1}\right| = n$. Thus, we have $\sum _{1\le i\le n}{\lambda }_{i} = n.$

We know that $n = \sum _{1\le i\le n}{\lambda }_{i}\le \left|\sum _{1\le i\le n}{\lambda }_{i}\right|\le \sum _{1\le i\le n}\left|{\lambda }_{i}\right|$. Thus, $\sum _{1\le i\le n}\left|{\lambda }_{i}\right|\ge n.$

Using Theorem 2.2, for $k = 2,$ we have

The value of $\left|{b}_{2}\right|$ is equal to the number of edges. Thus, ${b}_{2} = c = m.$ We can conclude that

We have already proven that $\sum _{1\le i\le n}{\lambda }_{i} = n.$

In the last step, we prove $\sum _{1\le i\le n}\left|{{\lambda }_{i}}^{2}\right|\ge {n}^{2}-2m.$

We have ${n}^{2}-2m = \sum _{1\le i\le n}{{\lambda }_{i}}^{2}\le \left|\sum _{1\le i\le n}{{\lambda }_{i}}^{2}\right|\le \sum _{1\le i\le n}\left|{{\lambda }_{i}}^{2}\right|$. Then, we can conclude that $\sum\limits_{1\le i\le n}\left|{{\lambda }_{i}}^{2}\right|\ge {n}^{2}-2m.$

□

Corollary 3.5. Let $D$ be an acyclic directed graph with $n$ vertices and $m$ edges. Let $B$ be an anti-adjacency matrix of graph $D$. If ${\mathrm{\lambda }}_{1}, \dots, {\mathrm{\lambda }}_{\mathrm{n}}$ are the eigenvalues of $B$, then the antiadjacency-energy of $D$ has a lower bound ${E}_{B}\left(D\right) = \sum _{1\le i\le n}\left|{\lambda }_{i}\right|\ge n.$

Next, we give several classes of directed acyclic graphs that have antiadjacency-energy equal to its lower bound.

Example 3.1. Let ${\overrightarrow{K}}_{m, n}$ be a complete bipartite directed graph with $m, n\ge 1$. Let $B\left({\overrightarrow{K}}_{m, n}\right)$ be the antiadjacency matrix of ${\overrightarrow{K}}_{m, n}$ of order $\left(m+n\right)\times \left(m+n\right)$. Then, the antiadjacency matrix characteristic polynomial of ${\overrightarrow{K}}_{m, n}$ with $m, n\ge 1$ is $p\left(B\left({\overrightarrow{K}}_{m, n}\right)\right) = {\lambda }^{m+n}-\left(m+n\right){\lambda }^{m+n-1}+{\left(mn\right)\lambda }^{m+n-2}$.

Spectrum antiadjacency matrix of a complete bipartite directed graph ${\overrightarrow{K}}_{m, n}$ with $m, n\ge 1$ is $Spec\left(B\left({\overrightarrow{K}}_{m, n}\right)\right) = \left(\begin{array}{ccc}m & n & 0\\ 1 & 1 & m+n-2\end{array}\right)$. Thus, ${E}_{B}\left({\overrightarrow{K}}_{m, n}\right) = \left|V\left({\overrightarrow{K}}_{m, n}\right)\right|.$

From the spectrum, we can see that ${E}_{B}\left({\overrightarrow{K}}_{m, n}\right) = \sum _{1\le i\le n}\left|{\lambda }_{i}\right| = m+n = \left|V\left({\overrightarrow{K}}_{m, n}\right)\right|.$

□

An example of a complete bipartite directed graph ${\overrightarrow{K}}_{\mathrm{4, 5}}$ is given in Figure 1. It can be checked that $p\left(B\left({\overrightarrow{K}}_{\mathrm{4, 5}}\right)\right) = {\lambda }^{9}-9{\lambda }^{8}+20{\lambda }^{7}$ and $\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\left(B\left({\overrightarrow{K}}_{\mathrm{4, 5}}\right)\right) = \left(\begin{array}{ccc}5 & 4 & 0\\ 1 & 1 & 7\end{array}\right)$. Thus ${E}_{B}\left({\overrightarrow{K}}_{\mathrm{4, 5}}\right) = 5+4 = 9.$

Example 3.2. Let ${\overrightarrow{CP}}_{n}$ be a complete path directed graph with $n\ge 1$. Let $B\left({\overrightarrow{CP}}_{n}\right)$ be the anti-adjacency matrix of ${\overrightarrow{CP}}_{n}$ of order $n\times n$. Then, the antiadjacency matrix characteristic polynomial of ${\overrightarrow{CP}}_{n}$ with $n\ge 1$ is $p\left(B\left({\overrightarrow{CP}}_{n}\right)\right) = {\left(\lambda -1\right)}^{n}$.

The spectrum antiadjacency matrix of the complete path directed graph ${\overrightarrow{CP}}_{n}$ with $n\ge 1$ is $\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\left(B\left({\overrightarrow{CP}}_{n}\right)\right) = \left(\begin{array}{c}1\\ n\end{array}\right)$. From the spectrum, we can see that

Example 3.3. Let ${\overrightarrow{K}}_{{m}_{i}, {n}_{i}}, i = \mathrm{1, 2}, 3, \dots, q$ be complete bipartite directed graphs ${m}_{i}\ge 1, {n}_{i}\ge 1$ and antiadjacency matrix characteristic polynomial are

Then, the antiadjacency matrix characteristic polynomial of the union of complete bipartite directed graphs $\overrightarrow{K} = \bigcup _{i = 1}^{q}{\overrightarrow{K}}_{{m}_{i}, {n}_{i}}$ with ${m}_{i}\ge 1, {n}_{i}\ge 1$ is

The spectrum antiadjacency matrix of the union of complete bipartite directed graphs $\overrightarrow{K} = \bigcup _{i = 1}^{q}{\overrightarrow{K}}_{{m}_{i}, {n}_{i}}$ with ${m}_{i}\ge 1, {n}_{i}\ge 1, i = \mathrm{1, 2}, 3, \dots, q$ is

with

From the spectrum, we can see that

For the disjoint union of acyclic directed graphs, we can obtain that its energy will be equal to the sum of energy of components of the directed graph.

4.   Conclusions

In this paper, we give some results on the antiadjacency matrix of directed graph. In the first part, we give some results on the determinant of the antiadjacency matrix. In the second part, we show that we can have more information on the characteristic polynomial of the antiadjacency matrix of the directed acyclic graph. In the third part, we have some results on regular digraphs, and in the last part, we introduce and give some elementary results for the antiadjacency energy of a directed graph. For future research, we can study more results and properties of the antiadjacency matrix spectrum. Moreover, we can study more properties of antiadjacency energy of the directed graph and find the antiadjacency energy for several interesting families of directed graphs.

Author contributions

K. S. Sugeng: conceptualization, supervision, review and editing; Firmansyah and Wildan: formal analysis; Handari and Hariadi: formal analysis and validation; Imran: validation.

Acknowledgments

This research has been funded by Universitas Indonesia Research Grant No NKB-748/UN2.RST/HKP.05.00/2023. The authors would like to thank the reviewers for their invaluable suggestions.

Conflict of interest

There is no conflict interest in this paper.