# The Singularity of Oriented Outerplanar Graphs with a Given Number of Inner Edges

Authors: Borui He; Xianya Geng; Long Wang
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A digraph is called oriented if there is at most one arc between two distinct vertices. An oriented graph is called nonsingular (singular) if its adjacency matrixAD is nonsingular (singular). In this paper, we study the singularity of the oriented outerplanar graph with a given number of inner edges.


---

## Body

## 1. Introduction

A digraphD=VD,ED consists of a nonempty finite set VD of elements called vertices and a finite set ED of ordered pairs of distinct vertices called arcs. Its adjacency matrix AD is the (0, 1)-matrix with aij=1 if and only if vivj is an arc in D. The rank rD of D is the rank of its adjacency matrix AD and D is called singular (respectively, nonsingular) if AD is singular (respectively, nonsingular). A digraph D can be obtained from an undirected graph G by replacing each edge uv of G with an arc or with a couple of arcs uv and vu. In this case, D is called an orientation of G and G is called the underlying graph of D. Two vertices are called adjacent if they are connected by an arc. If there is an arc from vertex u to vertex v, we indicate this by writing uv. Note that if vivj∈ED whenever vivj∈ED then D becomes an undirected graph and AD is symmetric. The rank of AD is equal to the number of nonzero eigenvalues and AD is nonsingular if and only if AD has no zero eigenvalues. We deal with digraphs where loops are not permitted and there is at most one arc between two distinct vertices; these are usually called oriented graphs.In fact, the singularity of undirected graphs is very important in chemistry. For a conjugated hydrocarbon molecule, its chemical stability depends on the singularity of the corresponding molecule graph [1]. In 1957, Collatz and Sinogowitz [2] posed the problem of characterising all singular (or nonsingular) graphs. The problem seems to be very hard and only a few particular results are known. For undirected graphs, it is easy to see that each complete graph is nonsingular [3]. Cvetković and Gutman [4, 5] showed that if B is bipartite and has no cycles with length 0 (mod 4), then rB=2mB, where mB is the matching number of B. This means that B is nonsingular if and only if B has a perfect matching. Guo et al. [6] determined all nonsingular unicyclic graphs. Li et al. [7] characterised the singularity of line graphs of unicyclic graphs with depth one. Gutman and Sciriha [8] presented a beautiful result showing that the line graph LT of a tree T is either nonsingular or has exactly one zero eigenvalue. For bipartite graphs [9], bicyclic graphs [10], and tricyclic graphs [11], the rank sets of each type have been determined, but the characterisation of nonsingular graphs remains open. For further results on the singularity of undirected graphs, see [12].There have been a few investigations on the singularity of oriented graphs. Monsalve and Rada [13] proposed the sink-source orientations, which preserve the rank for an oriented graph, and thus are very useful in singularity problems. Based on this, Zhang et al. [14] characterised the oriented graphs with a rank no larger than two. Chen et al. [15] determined the singularities of oriented graphs from the following three classes: graphs in which cycles are vertex disjoint, graphs in which all cycles share exactly one common vertex, and graphs formed by cycles sharing a common path. Ma and Jiang [16] give a necessary condition for an oriented bipartite graph to be nonsingular, characterise nonsingular oriented bipartite graphs Bm,n when min m,n≤3. A planar graph G is called an outerplanar graph if all of its vertices lie on the boundary of the same plane. The edge on the boundary is called the outer edge, the other edges are called the inner edge. In this paper, we aim to characterise the singularity of oriented outerplanar graphs with a given number of inner edges. By controlling the number of inner edges of the outerplanar graph, the singularity when the outer edge is directed and the existence of sink-source vertices are discussed, respectively.


## 2. Preliminaries

In this section, we make preparations for the main results. An oriented graphD is connected if its underlying graph is connected. Two vertices are adjacent if they are connected by an arc. We indicate an arc from u to v by writing uv. For a vertex v of D, we denote by N+v (respectively, N−v) the set of vertices u such that vu (respectively, uv) is an arc of D. The out-degree (respectively, in-degree) of v is d+v=N+v (respectively, d−v=N−v). The degree of v in D is dv=d+v+d−v. If dv=1, we call v a pendant vertex. We call v a sink (respectively, source) vertex if d+v=0 (respectively, d−v=0) and a sink-source vertex if d+vd−v=0. If there is a sink-source vertex there must be a sink vertex and a source vertex. Let D=VD,ED be an oriented graph. An oriented graph H=VH,EH is called a subgraph of D if VH⊆VD and EH⊆ED. We denote by H=D−uv the subgraph of D formed by deleting the arc uv from D. When uv∈EH if and only if uv∈ED for each ordered pair of vertices u and v in H, then H is called an induced subgraph of D. If H is an induced subgraph of D, then D−H is the induced subgraph of D with VD−H=VD/VH. If VH=x, we write D−H as D−x for brevity.Lemma 1 (see [15]).
LetD be an oriented graph, If D has a sink-source vertex, then D is singular. In particular, if D has a pendant vertex, then D is singular.Lemma 2 (see [14]).
LetD be an oriented graph and let x, y be two distinct vertices of D.(i)
IfN+x⊆N+y, then rD1=rD, where D1 is the subgraph of D obtained by deleting all yz for z∈N+x.(ii)
IfN−x⊆N−y, then rD2=rv, where D2 is the subgraph of D obtained by deleting all wy for w∈N−x.(iii)
IfN+x⊆N+y and N−x⊆N−y, then rD3=rD, where D3 is the subgraph of D obtained by deleting all yz for z∈N+x and all wy for w∈N−x.Lemma 3 (see [15]).
LetC be an oriented cycle. Then C is nonsingular if and only if C is directed.Lemma 4 (see [15]).
LetD be an oriented connected graph in which cycles are disjoint. Then D is nonsingular if and only if D satisfies all the following conditions:(i)
D has no pendant vertices(ii)
Each cycle inD is directed(iii)
Two cycles are adjacent inD if and only if they are connected by an arc


## 3. Oriented Outerplanar Graph with A Given Inner Edge

In this section, we characterise the singularity of the oriented outerplanar graph with a given inner edge.Theorem 1.
LetG be an oriented outerplanar graph. Then G is singular if and only if there is a pair sink-source vertex on the outer edge of G without considering the inner edge, see Figure 1.Figure 1
Singular situation.Proof.
Letx and y be two neighbours of u in G1. Assume that xu,yu,uv∈EG1. Since N+x=N+y=u, so the rows that correspond to the adjacency matrix are the same, the case is singular according to the properties of the determinant. In the case of G2,G3 and G4, they have a sink vertex or source vertex on the outer edge and are not connected to the inner edge. Then G2,G3 and G4 all of them are singular by Lemma 1.
LetG be an oriented outerplanar graph and it is directed on the outer edge. Let x and y neighbour of v and u. Assume that uv,uy,xv∈EG. Since N+x=v⊆N+u, it follows that rG−uv=rG by Lemma 2. Since G−uv is a directed cycle, it is nonsingular by Lemma 3. Now(1)rG=rG−uv=VG−uv=VG.
AndG is nonsingular.
Theorem1 has thus been proved.Example 1.
(1)
The adjacency matrix ofG5 is(2)A1=0100100001000000010000000100000001000000011000000.Set|λ E-A1| = 0, all the eigenvalues of A1 can be obtained by calculation. The results are as follows:(3)λ1=−0.9320+0.2879i,λ2=−0.9320−0.2879i,λ3=−0.1375+1.0900i,λ4=−0.1375−1.0900i,λ5=1.1382+0.0000i,λ6=0.5004+0.7173i,λ7=0.5004−0.7173i.The value ofA1 is equal to the product of all its eigenvalues, therefore A1≠0. Thus, G5 is nonsingular.(2)
The adjacency matrix ofG6 is(4)A2=0100100000100000000100000000100000000100000000100000000110000000.Set|λE − A2| = 0, all the eigenvalues of A2 can be obtained by calculation. The results are as follows:(5)λ1=1.1148+0.0000i,λ2=0.5756+0.7073i,λ3=0.5756−0.7073i,λ4=0.1288+1.0097i,λ5=0.1288−1.0097i,λ6=−0.8256+0.7153i,λ7=−0.8256+0.7153i,λ8=−0.8725+0.0000i.The value ofA2 is equal to the product of all its eigenvalues, therefore A2≠0. Thus, G6 is nonsingular.(3)
The adjacency matrix ofG7 is(6)A3=0000100100000001000000010000000101000000011000000.Set|λE − A3| = 0, all the eigenvalues of A3 can be obtained by calculation. The results are as follows:(7)λ1=1.1673+0.0000i,λ2=0.1812+1.0840i,λ3=0.1812−1.0840i,λ4=−0.7649+0.3525i,λ5=−0.7649−0.3525i,λ6=0.0000+0.0000i,λ7=0.0000+0.0000i.The value ofA3 is equal to the product of all its eigenvalues, therefore A3=0. Thus, G7 is singular.(4)
The adjacency matrix ofG8 is(8)A4=0000100010000000010000000010000000010100000000100000000110000000.Set|λE − A4| = 0, all the eigenvalues of A4 can be obtained by calculation. The results are as follows:(9)λ1=−0.9293+0.6752i,λ2=−0.9293−0.6752i,λ3=0.3550+1.0925i,λ4=0.3550−1.0925i,λ5=1.1487+0.0000i,λ6=0.0000+0.0000i,λ7=0.0000+0.0000i,λ8=0.0000+0.0000i.The value ofA4 is equal to the product of all its eigenvalues, therefore A4=0. Thus, G8 is singular.


## 4. Oriented Outerplanar Graph with Given Two Inner Edges

In this section, we characterise the singularity of the oriented outerplanar graph with given two inner edges. Here are two main cases. First, discuss the singularity of the graph where the outer edge is directed. Then discuss the singularity of the graph where the outer edge has a sink-source vertex. The sink-source vertex mentioned here refers to the sink or source vertex that appears on the outer edge without considering the existence of the inner edge.Theorem 2.
LetG be an outerplanar graph and the outer edge is directed. Then G is singular if and only if G can be obtained from the graph shown in Figure 2.Figure 2
Singular situation.Proof.
In order to prove that Theorem2 is true, it is proved that the case in Figure 2 is singular, and the other cases are nonsingular. Let G be an outerplanar graph with the outer edge is directed. Let w,x,y,z the four vertices of the two inner edges. Assume that xw,xy,zw,zy∈EG. Since N+x=N+y=w,y, so the rows that correspond to the adjacency matrix are the same, by subtracting two rows to get a zero row. Thus AG and G are singular.
Next, we will prove the other cases are nonsingular. When there are no inner edges, each vertex has an out- and in-degree of 1. We want to develop from the vertex outer degree to think and solve problems.Case 1. One vertex has an out-degree of 3 and the others have an out-degree of 1.This case is when two inner edges are assumed to beux,uy∈EG are connected to the same vertex u, and at the same time the vertex is an out-degree of 3 and the others have an out-degree of 1. Therefore, by Lemma 2, two inner edges ux,uy can be deleted, rG=rG−ux−uy. Since G−ux−uy is a directed cycle, it is nonsingular by Lemma 3. Now(10)rG=rG−ux−uy=VG−ux−uy=VG.AndG is nonsingular.Case 2. Two vertexes have an out-degree of 2 and the others have an out-degree of 1. There are roughly two different cases for the connection of the two inner edges.(1)
Two inner edges have terminal vertices connected at the same vertex.In this case, after the inner edge is joined, we will denote the vertices with out-degree 2 asx and y. And the terminal vertex shared by these two inner edges as v. Since only the vertices connecting the initial vertices of the two inner edges are out-degree of 2, the remaining vertices are out-degree of 1. There must be some vertex that has an initial vertex out-degree of 1 and a terminal vertex is v. Therefore, an inner edge can be deleted by Lemma 2. Another inner edge can be deleted in the same way according to Lemma 2. So by deleting the inner edge you get a directed cycle, it is nonsingular by Lemma 3.(2)
The terminal vertices of the two inner edges are not connected to the same vertex.The proof is the same as (1), after the inner edge is joined, the out-degree of the vertex is 2, and the vertex adjacent to the other terminal vertices will always have an out-degree of 1 to that vertex. Therefore, an inner edge can be deleted by Lemma2. Another inner edge can be deleted in the same way according to Lemma 2. So by deleting the inner edge, we will get a directed cycle, it is nonsingular by Lemma 3.
Theorem2 has thus been proved.Example 2.
(1)
The adjacency matrix ofG10 is(11)B1=0100100001000000010000100100000001000000011000000.Set|λE − B1| = 0, all the eigenvalues of B1 can be obtained by calculation. The results are as follows:(12)λ1=−0.2481+1.0340i,λ2=−0.2481−1.0340i,λ3=−0.7245+0.0000i,λ4=1.2207−0.0000i,λ5=0.0000+0.0000i,λ6=0.0000+0.0000i,λ7=0.0000+0.0000i.The value ofB1 is equal to the product of all its eigenvalues, therefore B1=0. Thus, G10 is singular.(2)
The adjacency matrix ofG11 is(13)B2=0100010000100000000100000000100001000100000000100000000110000000.Set|λE − B2| = 0, all the eigenvalues of B2 can be obtained by calculation. The results are as follows:(14)λ1=−1.1892+0.0000i,λ2=1.1892+0.0000i,λ3=0.0000−1.1892i,λ4=0.0000+1.1892i,λ5=0.0000+0.0000i,λ6=0.0000+0.0000i,λ7=0.0000+0.0000i,λ8=0.0000+0.0000i.The value ofB2 is equal to the product of all its eigenvalues, therefore B2=0. Thus, G11 is singular.(3)
The adjacency matrix ofG12 is(15)B3=0100100001000000010000000100010001000000011000000.Set|λE − B3| = 0, all the eigenvalues of B3 can be obtained by calculation. The results are as follows:(16)λ1=−0.0772+1.2121i,λ2=−0.0772−1.2121i,λ3=−0.9206+0.0000i,λ4=0.4087+0.6469i,λ5=0.4087−0.6469i,λ6=1.2578+0.0000i,λ7=1.0000+0.0000i.The value ofB3 is equal to the product of all its eigenvalues, therefore B3≠0. Thus, G12 is nonsingular.(4)
The adjacency matrix ofG13 is(17)B4=0100010000100000000100000000100000100100000000100000000110000000.Set|λE − B4| = 0, all the eigenvalues of B4 can be obtained by calculation. The results are as follows:(18)λ1=−0.7271+0.9341i,λ2=−0.7271−0.9341i,λ3=−0.2481+1.0340i,λ4=−0.2481−1.0340i,λ5=−0.7245+0.0000i,λ6=1.2207+0.0000i,λ7=0.7271+0.4300i,λ8=0.7271−0.4300i.The value ofB4 is equal to the product of all its eigenvalues, therefore B4≠0. Thus, G13 is nonsingular.Theorem 3.
LetG be an outerplanar graph and outer edge with sink-source vertices. Then G is nonsingular if and only if G can be obtained from the graph shown in Figure 3.Figure 3
Nonsingular situation.Proof.
In order to prove that Theorem2 is true, it is proved that the case in Figure 3 is nonsingular, and the other cases are singular. For G14 in the case of Figure 3 assume that xw,zw,zy,uy∈EG14. Since N+u=y⊆N+v, it follows that rG14=rG14−xy by Lemma 2. Since G14−xy follow the two cycles are adjacent and connected by an arc. Thus it is nonsingular by Lemma 4. Now(19)rG14=rG−xy=VG14−xy=VG14.
AndG14 is nonsingular.
ForG15 in the case of Figure 3 assume that xw,zw,zu∈EG15. Since N+x=w⊆N+z, it follows that rG15=rG15−zw by Lemma 2. Since G15−zw follow the two cycles are adjacent and connected by an arc. Thus it is nonsingular by Lemma 4. Now(20)rG15=rG−zw=VG15−zw=VG15.
AndG15 is nonsingular.
ForG16 in the case of Figure 3 assume that uw,zw,zv∈EG16. Since N+u=w⊆N+z, it follows that rG16=rG16−zw by Lemma 4. Since G16−zw follow the two cycles are adjacent and connected by an arc. Thus it is nonsingular by Lemma 4. Now(21)rG16=rG−zw=VG16−zw=VG16.
AndG16 is nonsingular.
Next, we will prove the other cases are singular. We are going to split it up into two cases to prove that the rest of the cases are singular. These are cases where the outer edge has a pair of sink-source vertices and two pairs of sink-source vertices.Case 1. The outer edge has a pair of sink-source vertices.(1)
When the two inner edges are connected at the sink vertex and source vertex, respectively, see Figure4G17 and G18. For G17, let x and y be two neighbours of z, xz,yz∈EG17. Since N+x=N+y=z, so the rows that correspond to the adjacency matrix are the same, by subtracting two rows to get a zero row. Thus AG17 and G17 are singular. For G18, let x and y be two neighbours of z, xz,yz∈EG18. Since N+x=N+y=z, so the rows that correspond to the adjacency matrix are the same, by subtracting two rows to get a zero row. Thus AG18 and G18 are singular.(2)
When there is an inner edge connected at the sink-source vertex. When the out-degree of the two adjacent vertices of the sink vertex is 1, then it is singular. When the vertex adjacent to the sink vertex has an out-degree of 2, the other terminal vertices of the other inner edge can be connected to the source vertex or the vertex separated by two or more vertex from the source vertex. At this point, except for the source vertex and one of the adjacent vertices of sink vertices has an out-degree of 2, all other vertices have an out-degree of 1. Therefore, an inner edge can be deleted according to Lemma2 to obtain graph G19. Thus graph is singular.Case 2. The outer edge has two pairs of sink-source vertices.When there are two pairs of sink-source vertices on the outside, then the two inner edges need to be connected at the sink-source vertex. Otherwise, the graph has sink-source vertices that are singular, by Lemma1. When the terminal vertices of the two inner edges are separated by several vertices, the out-degree of the two adjacent vertices at the sink vertex is 1, then the graph is singular.
Theorem3 has thus been proved.Figure 4
Singular situation.Example 4.
(1)
The adjacency matrix ofG20 is(22)H1=0000010010001000010000000010000000010100000000100000000110000000.Set|λE − H1| = 0, all the eigenvalues of H1 can be obtained by calculation. The results are as follows:(23)λ1=−1.0000+0.0000i,λ2=−1.0000+0.0000i,λ3=0.0000−1.0000i,λ4=0.0000−1.0340i,λ5=0.0000+0.0000i,λ6=0.0000+0.0000i,λ7=1.0000+0.0000i,λ8=1.0000+0.0000i.The value ofH1 is equal to the product of all its eigenvalues, therefore H1≠0. Thus, G20 is nonsingular.(2)
The adjacency matrix ofG21 is(24)H2=0100000100001000010000000010000000010100100000000000010000000010.Set|λE − H2| = 0, all the eigenvalues of H2 can be obtained by calculation. The results are as follows:(25)λ1=−1.2720+0.0000i,λ2=0.0000+1.2720i,λ3=0.0000−1.2720i,λ4=1.2720+0.0000i,λ5=−0.7862+0.0000i,λ6=0.0000+0.7862i,λ7=0.0000−0.7862i,λ8=0.7862+0.0000i.The value ofH2 is equal to the product of all its eigenvalues, therefore H2≠0. Thus, G21 is nonsingular.(3)
The adjacency matrix ofG22 is(26)H3=0000001010000000010010000010000000010100000000100000000110000000.Set|λE − H3| = 0, all the eigenvalues of H3 can be obtained by calculation. The results are as follows:(27)λ1=−0.5000+0.8660i,λ2=−0.5000+0.8660i,λ3=−0.5000−0.8660i,λ4=−0.5000−0.8660i,λ5=1.0000+0.0000i,λ6=1.0000+0.0000i,λ7=0.0000+0.0000i,λ8=0.0000+0.0000i.The value ofH3 is equal to the product of all its eigenvalues, therefore H3=0. Thus, G22 is singular.(4)
The adjacency matrix ofG23 is(28)H4=0100000100100000000010000010000000010100000000101000000000000010.Set|λE − H4| = 0, all the eigenvalues of H4 can be obtained by calculation. The results are as follows:(29)λ1=−0.6300+1.0911i,λ2=−0.6300−1.0911i,λ3=1.2599+0.0000i,λ4=0.0000+0.0000i,λ5=0.0000+0.0000i,λ6=0.0000+0.0000i,λ7=0.0000+0.0000i,λ8=0.0000+0.0000i.The value ofH4 is equal to the product of all its eigenvalues, therefore H4=0. Thus, G23 is singular.



---

*Source: 1527031-2022-11-29.xml*