[PDF] bipartite graph algorithm dfs
[PDF] bipartite graph definition with example
[PDF] bipartite graph example pdf
[PDF] bipartite graph worksheet
[PDF] bird on australian 50 cent coin
[PDF] birth rates in europe by country
[PDF] birthday reminder android app source code
[PDF] bis exchange rate index
[PDF] bit masking in c geeksforgeeks
[PDF] bitcoin pdf 2020
[PDF] bitcoin price
[PDF] bitcoin sovereignty through mathematics pdf
[PDF] bitwise and operators in c
[PDF] bitwise operators in c with examples
[PDF] bitwise operators in c with examples ppt
On the Determinant of the Adjacency Matrix
of a Type of Plane Bipartite Graphs
Lingling Huang, Weigen Yan
1 School of Sciences, Jimei University, Xiamen 361021, China (Received July 9, 2012)
Abstract
LetGbe a simple graph andA(G) its adjacencymatrix. Based on some results of Rara (H. M. Rara,Discr. Math.151 (1996) 213-219), we show that the determinant ofA(G)ofa plane graphGwhich has the property that every face-boundary is a cycle of size divisible by 4, equals-1,0 or 1, provided the inner dual graph ofGis a tree. As applications, we compute the algebraic structure count of some polygonal chains.
1. INTRODUCTION
LetGbe a simple graph with vertex setV(G
)={v 1 ,v 2 ,...,v n }and edge setE(G)= {e 1 ,e 2 ,...,e m }. The adjacencymatrix of graphGis ann×n(0,1)-matrixA(G)=(a ij), wherea ij = 1 if and only if (v i ,v j )isanedgeofGanda ij = 0 otherwise. Letd G (u)be the degree of vertexuofG.IfV 1 ?V(G)andE 1 ?E(G), we useG-V 1 andG-E 1 to denote the subgraphs ofGinduced byV(G)\V 1 andE(G)\E 1 , respectively. Particulary, ifV 1 ={u}andE 1 e},weuseG-uandG-eto denoteG-{u}andG-{e}.Let G be the dual graph of a plane graphGandfthe vertex ofD corresponding to the unbounded face ofG.CallG -fto be the inner dual graph ofG, denoted byG (see
Figure 1).
Deift and Tomei [5] proved an interesting result: The determinant of the adjacency matrix of a finite subgraphGofZ×Zequals-1,0 or 1, providedGhas no "hole". This 1
Corresponding author
MATCH Communications in Mathematical and in Computer Chemistry MATCH Commun. Math. Comput. Chem. 68 (2012) 931-938
ISSN 0340 - 6253
Figure 1: (a). A plane graphGwith three facesf,f
1 andf 2 . (b). The dual graphG of
G. (c). The inner dual graphG
ofG. implies that the algebraic structure count of a finite subgraphGofZ×Zequals 0 or 1, providedGhas no "hole" (The algebraic structure count of a bipartite graphGis defined as the square root of the absolute value of det(A(G)), see [6,13,14]). For some results on the determinant of the adjacencymatrix of graphs (resp. the algebraic structure count of bipartite graphs) see for example [1,3,7,11,12]. (resp. [3,8-10]). Apolyomino systemis a finite 2-connected plane graph such that each interior face is surrounded by a regular square of length one. A special case of the above result by Deift and Tomei is that ifGis a polyomino systemwhose inner dual is a tree, then the determinant ofA(G)equals-1,0 or 1. It is natural to ask whether there exists a similar result for the determinant ofA(G) of a plane graphGwhich has the property that every face-boundary is a cycle of size divisible by 4, provided the inner dual graph ofGis a tree. Themain result of this short note, Theorem2.6, answers this question in the affirmative. Finally, as applications we compute the algebraic structure count of some polygonal chains.
2. Main results
We useP
n andC n to denote the path and cycle withnvertices. Now, we introduce some known lemmas.
Lemma 2.1.[12] LetP
6 =[1,2,3,4,5,6] be an induced subgraph ofGwithd G (2) = d G (3) =d G (4) =d G (5) = 2. IfHis the graph formed fromG-{2,3,4,5}by joining vertices 1 and 6 with an edge, then det(A(G)) = det(A(H)).-932-
Lemma 2.2.[12] LetC
4 =[v 1 ,v 2 ,v 3 ,v 4 ,v 1 ] be a subgraph ofGwithd G (v 1 )=2.IfG is the graph obtained fromGby removing the edgesv 2 v 3 andv 3 v 4 ,then det(A(G )) = det(A(G)).
Figure 2: The graphGobtained fromG
1 andG 2 Lemma 2.3.[12] LetGbe the graph obtained by joining the vertexxof the graphG 1 to the vertexyof the graphG 2 by an edge (see Fig. 2). Then det(A(G)) = det(A(G 1 )) det(A(G 2 ))-det(A(G 1 -x)) det(A(G 2 -y)). The following lemmaisimmediate fromthe lemmaabove.
Lemma 2.4.LetGbe a graph andvbeanyvertexofG.IfG
is the graph obtained fromGby joiningvto a new vertexu,then det(A(G )) =-det(A(G-v)). By induction, the following result follows fromLemma2.4. Corollary 2.5.IfTis a tree withnvertices, then the determinant ofA(T)equals(-1) n/2 ifThas a perfectmatching and zero otherwise. Lemma 2.6.LetGbe a plane graph each bounded face of which is a cycle with length equalto0(mod4). If the inner dualG is a tree, then the determinant of the adjacency matrix ofGequals-1,0 or 1, i.e., det(A(G)) = 0,±1. Proof.Since each bounded face ofGis a cycle with even number of edges,Gis a bipartite graph. First, we prove the following claim.-933- Claim.LetGbe the graph obtained by joining the vertexxof the bipartite graphG 1 to the vertexyof the bipartite graphG 2 by an edge. If det(A(G i )) = 0,±1, det(A(G 1 x)) = 0,±1 and det(A(G 2 -y)) = 0,±1, then det(A(G)) = 0,±1. By Lemma2.3, det(A(G)) = det(A(G 1 )) det(A(G 2 ))-det(A(G 1 -x)) det(A(G 2 -y)).(1)
If det(A(G
1 )) det(A(G 2 )) = 0, then by (1) the claimholds. If det(A(G 1 )) =±1and det(A(G 2 )) =±1, then both|V(G 1 -x)|and|V(G 2 -y)|are odd, implying det(A(G 1 x)) = det(A(G 2 -y)) = 0. So the det(A(G)) =±1. Hence the claimfollows. Now we prove the theoremby induction on|V(G)|,thenumber of vertices ofG.IfG contains no cycle, that is,|V(G )|= 0, then, by Corollary 2.5, det(A(G)) = 0,±1. IfG has a cut edgee=(u,v), then by induction and the claimabove, the theoremfollows. Hence wemay assumethatGis 2-edge connected. Note that the inner dualG is a tree. If|V(G )|=1,thenGis a cycle with 4svertices for some integers. Obviously, det(A(C 4s )) = 0. Hence we suppose that|V(G )|≥2. Letfbe a vertex of degree one ofG .Thenfcan be regarded as a bounded face ofGwhose boundary is a cycle with
4kvertices for some integerk. HenceGhas the formof the graphs illustrated in Figure
3, whereG
0 is plane graph each bounded face of which is a cycle with length equal to 0 (mod4) andG 0 =G -fis a tree. We distinguish the following two cases.
Figure 3: (a). The graphG
1 with a facefwhose boundary is a cycle with four vertices. (b). The graphG 2 with a facefwhose boundary is a cycle with 4kvertices (k≥2).
Case 1.k=1.
Ifk=1,Gis of the formof graphG
1 shown in Figure 3(a). Sinced G1 (1) = 2 and
1-2-4-3-1 is a cycle ofG=G
1 ,byLemma2.2,det(A(G)) = det(A(G 1 det(A(G 1 -e 1 -e 2 )), wheree 1 =(2,4) ande 2 =(3,4). By Lemma2.4, det(A(G 1 -e 1 -e 2 )) =-det(A(G 0 -e 1
Note thatG
0 -e 1 is a plane graph each bounded face of which is a cycle with length equalto0(mod4). Moreover, the inner dual graph ofG 0 -e 1 is a forest. By induction, det(A(G 0 -e 1 )) = 0,±1. Hence det(A(G)) = det(A(Gquotesdbs_dbs14.pdfusesText_20
[PDF] BIPARTITE GRAPHS OBTAINED FROM ADJACENCY MATRICES