# Per-Spectral Characterizations of Bicyclic Networks

Authors: Tingzeng Wu; Huazhong Lü
Journal: Journal of Applied Mathematics
 (2017)

---

## Abstract

Spectral techniques are used for the study of several network properties: community detection, bipartition, clustering, design of highly synchronizable networks, and so forth. In this paper, we investigate which kinds of bicyclic networks are determined by their per-spectra. We find that the permanental spectra cannot determine sandglass graphs in general. When we restrict our consideration to connected graphs or quadrangle-free graphs, sandglass graphs are determined by their permanental spectra. Furthermore, we construct countless pairs of per-cospectra bicyclic networks.


---

## Body

## 1. Introduction

It was recognized in about last decade that graph spectra have several important applications in computer science. Graph spectra appear in internet technologies, pattern recognition, computer vision, data mining, multiprocessor systems, statistical databases, and many other areas. For example, spectral filtering is applied in the study of Internet structure [1]. This method uses the eigenvectors of the adjacency and other graph matrices and some clusters in data sets represented by graphs. For more information about the applications of graph spectra in computer science see [2–6], among others.Thepermanent of n×n matrix Y=(yij)(i,j=1,2,…,n) is defined as (1)perY=∑σ∏i=1nyiσi, where the sum is taken over all permutations σ of {1,2,…,n}. Valiant [7] showed that computing the permanent is #P-complete even when restricted to (0, 1)-matrices.LetG be a graph with n vertices, and let A(G) be (0,1)-adjacency matrix of G. Thepermanental polynomial of G, denoted by π(G,x), is defined as π(G,x)=per(xI-A(G)). Thepermanental spectrum (per-spectrum for short) of graph G, denoted by ps(G), is the set of all roots (together with their multiplicities) of π(G,x).Two graphs areper-cospectral if they share the same per-spectrum. A graph G is said to bedetermined by its per-spectrum (DPS for short) if there is no other nonisomorphic graph with the same per-spectrum.Which graphs are determined by their adjacency spectra is an old problem in graph spectra theory. van Dam and Haemers [8, 9] gave an excellent survey of answers to the question of which graphs are determined by the spectra of some graph polynomials. Merris et al. [10] first considered the problem which graph is DPS. And they showed that the five pairs adjacency cospectral graphs (see [11]) are DPS. Based on the result, they formulated that the per-spectrum seems a little better than the adjacency spectrum when it comes to distinguishing graphs which are not trees. In fact, characterizing what kinds of graphs are determined by the per-spectra is generally a very hard problem. Up to now, only a few types of graphs are proved to be DPS; see [12–17].Abicyclic network is a simple connected graph in which the number of edges equals the number of vertices plus one [18]. Thesandglass graph is a bicyclic network, denoted by S(C3,Ph,C3), obtained by appending a triangle to each pendant vertex of the path Ph. Lu et al. [19] proved that sandglass graphs are determined by their adjacency spectra. Motivated by the statement of Merris et al., a natural problem is whether sandglass graphs are determined by their per-spectra. In this paper, we give a solution of this question.In what follows, we begin with some definitions and notions. LetG∪H be the union of two graphs G and H which have no common vertices. For any positive integer l, let lG denote the union of l disjoint copies of graph G. The path and cycle on n vertices are denoted by Pn and Cn, respectively. Let ci(G) denote the number of i-cycles in G.LetCp and Cq be two vertex-disjoint cycles. Suppose that v1 is a vertex of Cp and vl is a vertex of Cq. Joining v1 and vl by a path v1v2⋯vl of length l-1, where l≥1 and l=1 means identifying v1 with vl, the resulting graph (see Figure 1), denoted by ∞(p,l,q), is called ∞-graph. Let Pr+1, Ps+1, and Pt+1 be three vertex-disjoint paths, where r,s,t≥1 and at most one of them is 1. Identifying the three initial vertices and terminal vertices of them, respectively, the resulting graph (see Figure 1), denoted by θ(r,s,t), is called θ-graph. Then bicyclic networks can be partitioned into two classes: the class of graphs which contain ∞-graph as its induced subgraph and the class of graphs which contain θ-graph as its induced subgraph.Figure 1
∞-graph and θ-graph.A subgraphH of G is aSachs subgraph if each component of H is a single edge or a cycle. Merris et al. [10] gave a modified Sachs formula to compute the coefficients of the permanental polynomials of graphs.Lemma 1 (see [10]).
LetG be a graph with π(G,x)=∑k=0nbk(G)xn-k. Then (2)bkG=-1k∑H2cH,1≤k≤n, where the sum is taken over all Sachs subgraphs H of G on k vertices, and c(H) is the number of cycles in H.Lemma 2 (see [13]).
LetG be a graph with n vertices and m edges, and let (d1,d2,…,dn) be the degree sequence of G. Then(3)b0G=1,b1G=0,b2G=m,b3G=-2c3G,b4G=m2-∑i=1ndi2+2c4G.Lemma 3 (see [17]).
LetG be a graph with m edges, and let ti(G) denote the degree sum of the three vertices on ith triangle in G. Then (4)b5G=-2∑i=1c3Gm+3-tiG+c5G.Lemma 4 (see [13]).
The following can be deduced from the permanental polynomial of a graphG:(i)
The number of vertices(ii)
The number of edges(iii)
The number of triangles(iv)
The length of the shortest odd cycle(v)
The number of the shortest odd cycles(vi)
WhetherG is bipartite


## 2. Sandglass Graphs Are DPS

In this section, we will give the solutions of the problem which sandglass graphs are DPS?Checking graphG′ depicted in Figure 2, direct computation yields π(G′,x)=x13+14x11-4x10 + 74x9-40x8+186x7-136x6+230x5-180x4+130x3-76x2+25x-4=π(S(C3,P9,C3),x). This implies that the permanental spectra cannot determine sandglass graphs in general. Examining graph G′ again, we know that G′ is not connected and contains a quadrangle. It is natural to consider the problem which sandglass graphs are DPS when we restrict our consideration to connected graphs or quadrangle-free graphs, where the quadrangle-free graph is one which contains no quadrangles (i.e., cycles of length 4). We will answer these questions one by one in the following.Figure 2
GraphG′.First, we give some lemmas which will play an important role in the proof of main theorems.Lemma 5.
LetS(C3,Ph,C3) be a graph with n vertices. Then b5(S(C3,Ph,C3))=-4n+12.Proof.
By Lemma3, the proof is trivial.Lemma 6.
LetS(C3,Ph,C3) be a graph with n vertices. Then n-th coefficient of π(S(C3,Ph,C3),x) is (5)bnSC3,Ph,C3=-4,ifnisodd;5,ifniseven.Proof.
Suppose thatn is odd. Then the Sachs subgraph of order n in S(C3,Ph,C3) is only C3∪n-3/2P2. By Lemma 1, we have bn(G)=-4. Otherwise, if n is even, then the Sachs subgraph of order n in S(C3,Ph,C3) is C3∪C3∪n-6/2P2 and n/2P2. By Lemma 1, we have bn(G)=5.Lemma 7.
LetG be a quadrangle-free graph with n vertices. If π(G,x)=π(S(C3,Ph,C3),x), then the degree sequence of G is (2n-2,32), where ak means a,a,…,a︷k.Proof.
Suppose that the degree sequenceG is (3+t1,3+t2,2+t3,…,2+tn), where t1,t2>-3, and ti>-2(i=3,4,…,n) are integers. Since G and S(C3,Ph,C3) have the same number of edges, then(6)∑i=1nti=0.By Lemma 2, we have(7)b4G=n+12-3+t12-3+t22-∑i=3n2+ti2.Since π(G,x)=π(S(C3,Ph,C3),x), we have b4(G)=b4(S(C3,Ph,C3)). By a simple calculation, we obtain(8)∑i=1nti2=-2t1+t2.Checking (8), it is easy to see that if t1≥3 or t2≥3, then ∑i=3nti2<0, a contradiction. Hence,(9)-2≤t1,t2≤2.Furthermore, if t1=-t2 except t1=t2=0, then ∑i=3nti2<0, a contradiction. Thus(10)t1+t2≠0.Solving simultaneous equations (6)–(10), we have (11)t1=t2=-2,t3=⋯=tn=0,t1=-2,t2=-1,t3=±1,t4=⋯=tn=0,t1=-2,t2=0,t3=⋯=tn=0,t1=t2=-1,t3=t4=±1,t5=⋯=tn=0,t1=-1,t2=0,t3=±1,t4=⋯=tn=0,t1=0,t2=-2,t3=⋯=tn=0,t1=0,t2=-1,t3=±1,t4=⋯=tn=0,t1=t2=0,t3=⋯=tn=0.Thus the degree sequence of G is possible (12,2n-2), (1,2n-2,3), or (2n-2,32). It is not difficult to check that only (2n-2,32) satisfies the well-known hand-shaking theorem. So, the degree sequence of G is (2n-2,32).Theorem 8.
Restricting consideration on quadrangle-free graphs, sandglass graphs are determined by their per-spectra.Proof.
LetG be a quadrangle-free graph with n vertices per-cospectral with S(C3,Ph,C3). By Lemma 7, we know that the degree sequence of G is (2n-2,32). Then G is isomorphic to ∞(p,l,q)∪(⋃i=1kCki) or θ(r,s,t)∪(⋃i=1kCki), where ⋃i=1kCki denotes the union of k≥0 disjoint cycles Cki of length ki. By the above, it implies that VG≥5. It is not difficult to see that if n=5, then G is isomorphic to S(C3,Pl,C3). So, assume n>5 and consider the following two cases.
Case  1. Assume that G is isomorphic to ∞(p,l,q)∪(⋃i=1kCki). We further discuss the following three subcases.
Subcase  1.1. Exact one of the two triangles belongs to the bicyclic component. Then G=∞(p,l,q)∪C3∪⋃i=1k-1Cki for p=3,q≥4, and k≥1. By Lemma 3, we obtain that b5(G)=-4n+10-2c5(G). By Lemma 5, we have b5(S(C3,Pl,C3))-b5(G)=2+2c5(G)>0. This contradicts the assumption that G and S(C3,Pl,C3) are per-cospectral.
Subcase  1.2. Both of the two triangles belong to the bicyclic component. Then G=∞(3,l,3)∪⋃i=1kCki. If k=0, then G is isomorphic to S(C3,Pl,C3). Next we suppose that k>0. By the structure of G and Lemma 1, we can obtain that bn(G)>5 when n is even, and bn(G)<-4 when n is odd. By Lemma 6, this is a contradiction.
Subcase  1.3. Neither of the two triangles belongs to the bicyclic component. Then G=∞(p,l,q)∪C3∪C3∪⋃i=1k-2Cki for p,q≥4. By Lemma 3, we have b5(G)=-4n+8-2c5(G). So, b5(S(C3,Pl,C3))-b5(G)=4+2c5(G)>0. This contradicts the assumption that G and S(C3,Pl,C3) are per-cospectral.
Case  2. Assume that G is isomorphic to θ(r,s,t)∪(⋃i=1kCki). We further consider the following three subcases.
Subcase  2.1. Exact one of the two triangles belongs to the bicyclic component. Then G=θ(1,2,t)∪C3∪⋃i=1k-1Cki for t>2 and k≥1. By the structure of G and Lemma 1, we can obtain that if n is even, then bn(G)>5; and if n is odd, then bn(G)<-4. By Lemma 6, this is a contradiction.
Subcase  2.2. Both of the two triangles belong to the bicyclic component. Then G=B21,2,2∪(⋃i=1kCki), which is a contradiction to G being a quadrual-free graph.
Subcase  2.3. Neither of the two triangles belongs to the bicyclic component. Then G=θ(r,s,t)∪C3∪C3∪(⋃i=1k-2Cki) for r>1, s,t≥2 or r≥1, s,t>2. By Lemma 3, we have b5(G)=-4n+8-2c5(G). By Lemma 6, we have a contradiction, and the theorem follows.Theorem 9.
Restricting consideration on connected graphs, sandglass graphs are determined by their per-spectra.Proof.
LetG be a connected graph, where G=n and n≥5, and let G be per-cospectral with S(C3,Ph,C3). By Lemma 4, G is a bicyclic graph with two triangles and must be isomorphic to a graph containing a sandglass graph S(C3,Pl,C3) as its induced subgraph or K4-e (isomorphic to θ-graph when r=1 and s=t=2) as its induced subgraph.
Suppose thatG is isomorphic to a graph which contains a sandglass graph S(C3,Pl,C3) as its induced subgraph. Then G contains no quadrangles. By Lemma 7, G must be isomorphic to the sandglass graph S(C3,Ph,C3).
In the following, we will prove thatG is isomorphic to a graph containing K4-e as its induced subgraph.
Suppose thatn is even. By Lemma 6, we know that bn(S(C3,Ph,C3))=5. This implies, by Lemma 1, that G must have odd perfect matchings. Examining the structure of G, we see that G has at most two perfect matchings. So, G only has uniquely one perfect matching. This implies that all triangles or 4-cycle in G are not a component of some Sachs subgraph of order n. Thus, the perfect matching of G is a unique Sachs subgraph of order n. By Lemma 1, bn(G)=1, which contradicts the fact that bn(S(C3,Ph,C3))=5.
Assume thatn is odd. By Lemma 1 and examining the structure of G, we know that the Sachs subgraphs of order n in G is only the union of a triangle and a perfect matching of G deleting all edges on the triangle. Then bn(G)=2. This contradicts bn(S(C3,Ph,C3))=5.
This completes the proof.For any bicyclic network, it is difficult to discuss which is determined by its per-spectrum. We can construct countless pairs per-cospectral bicyclic networks. LetH be an arbitrary graph with a fixed vertex w and let Gu·H denote the coalescence of G and H with respect to u and w, which is the graph obtained from G∪H by identifying u and w. Similarly, we define Gv′·H. Borowiecki [20] showed that if both G-u and G′-v are per-cospectral, then both Gu·H and Gv′·H are also per-cospectral. As an example, let B=B′ be the bicyclic network depicted in Figure 3. As B-u and B-v are isomorphic, they are per-cospectral. By the above-mentioned result of Borowiecki [20], for any graph H, both Bu·H and Bv·H are per-cospectral.Figure 3
The bicyclic networkB.


## 3. Summary

Per-spectra is an important part of graph spectra. In this paper, we discuss properties of permanental spectra of bicyclic networks. We show that without some limitations bicyclic networks are not DPS. Particularly, we find a pair of per-cospectral graphs. Combining the result of Lu et al. [19], our results (Theorems 8 and 9) are beyond Merris et al.’s imagination. Finally, we pose the following conjecture.Conjecture 10.
Sandglass graphs with a perfect matching are DPS.



---

*Source: 7541312-2017-05-31.xml*