Printer Friendly

Per-Spectral Characterizations of Bicyclic Networks.

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.

The permanent of nxnmatrix Y = ([y.sub.ij]) (i, j = 1,2,..., n) is defined as

[mathematical expression not reproducible], (1)

where the sum is taken over all permutations a of {1, 2 , ..., n}. Valiant [7] showed that computing the permanent is #P-complete even when restricted to (0, 1)-matrices.

Let G be a graph with n vertices, and let A(G) be (0,1)-adjacency matrix of G. The permanental polynomial of G, denoted by [pi](G, x), is defined as [pi](G, x) = per(xl - A(G)). The permanental spectrum (per-spectrum for short) of graph G, denoted by ps(G), is the set of all roots (together with their multiplicities) of [pi](G, x).

Two graphs are per-cospectral if they share the same per-spectrum. A graph G is said to be determined 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].

A bicyclic network is a simple connected graph in which the number of edges equals the number of vertices plus one [18]. The sandglass graph is a bicyclic network, denoted by S([C.sub.3], [P.sub.h], [C.sub.3]), obtained by appending a triangle to each pendant vertex of the path [P.sub.h]. 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 perspectra. In this paper, we give a solution of this question.

In what follows, we begin with some definitions and notions. Let G [union] H be the union of two graphs G and H which have no common vertices. For any positive integer I, let IG denote the union of I disjoint copies of graph G. The path and cycle on n vertices are denoted by [P.sub.n] and [C.sub.n], respectively. Let [c.sub.i] (G) denote the number of i-cycles in G.

Let [C.sub.p] and [C.sub.q] be two vertex-disjoint cycles. Suppose that [v.sub.1] is a vertex of [C.sub.p] and [v.sub.l] is a vertex of [C.sub.q]. Joining [v.sub.1] and [v.sub.l] by a path [v.sub.1] [v.sub.2] *** [v.sub.l] of length l - 1, where l [greater than or equal to] 1 and l = 1 means identifying [v.sub.1] with [v.sub.l];, the resulting graph (see Figure 1), denoted by [infinity](p, l, q), is called [infinity]-graph. Let [P.sub.r+1], [P.sub.s+1], and [P.sub.t+1] be three vertex-disjoint paths, where r, s, t [greater than or equal to] 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 [theta](r,s,t), is called [theta]-graph. Then bicyclic networks can be partitioned into two classes: the class of graphs which contain [infinity]-graph as its induced subgraph and the class of graphs which contain [theta]-graph as its induced subgraph.

A subgraph H of G is a Sachs 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]). Let G be a graph with [pi](G,x) = [[SIGMA].sup.n.sub.k=0] [b.sub.k](G) [x.sup.n-k]. Then

[b.sub.k] (G) = [(-1).sup.k] [summation over (H)] 1 [less than or equal to] k [less than or equal to] n, (2)

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]). Let G be a graph with n vertices and m edges, and let ([d.sub.1], [d.sub.2], ..., [d.sub.n]) be the degree sequence of G. Then

[mathematical expression not reproducible]. (3)

Lemma 3 (see [17]). Let G be a graph with m edges, and let [t.sub.i] (G) denote the degree sum of the three vertices on ith triangle in G. Then

[b.sub.5] (G) = -2 ([[c.sub.3](G).summation over (i=1)] (m + 3 - [t.sub.i] (G)) + [c.sub.5] (G)). (4)

Lemma 4 (see [13]). The following can be deduced from the permanental polynomial of a graph G:

(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) Whether G is bipartite

2. Sandglass Graphs Are DPS

In this section, we will give the solutions of the problem which sandglass graphs are DPS?

Checking graph G' depicted in Figure 2, direct computation yields [pi](G', x) = [x.sup.13] + 14[x.sup.11] - 4[x.sup.10] + 74[x.sup.9] - 40[x.sup.8] + 186[x.sup.7] - 136[x.sup.6] + 230[x.sup.5] - 180[x.sup.4] + 130[x.sup.3] - 76[x.sup.2] + 25x - 4 = [oi](S([C.sub.3], [P.sub.9], [C.sub.3]), 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.

First, we give some lemmas which will play an important role in the proof of main theorems.

Lemma 5. Let S([C.sub.3], [P.sub.h], [C.sub.3]) be a graph with n vertices. Then [b.sub.5] (S([C.sub.3], [P.sub.h], [C.sub.3])) = -4n + 12.

Proof. By Lemma 3, the proof is trivial. ?

Lemma 6. Let S([C.sub.3], [P.sub.h], [C.sub.3]) be a graph with n vertices. Then n-th coefficient of [pi](S([C.sub.3], [P.sub.h], [C.sub.3]), x) is

[mathematical expression not reproducible]. (5)

Proof. Suppose that n is odd. Then the Sachs subgraph of order n in S([C.sub.3], [P.sub.h], [C.sub.3]) is only [C.sub.3] [union] ((n - 3)/2)[P.sub.2]. By Lemma 1, we have [b.sub.n] (G) = -4. Otherwise, if n is even, then the Sachs subgraph of order n in S([C.sub.3], [P.sub.h], [C.sub.3]) is [C.sub.3] [union] [C.sub.3] [union] ((n- 6)/2)[P.sub.2] and (n/2)[P.sup.2]. By Lemma 1, we have [b.sup.n] (G) = 5.

Lemma 7. Let G be a quadrangle-free graph with n vertices. If [pi](G, x) = [pi](S([C.sub.3], [P.sub.h], [C.sub.3]), x), then the degree sequence of G is

[mathematical expression not reproducible].

Proof. Suppose that the degree sequence G is (3 + [t.sub.1], 3 + [t.sub.2], 2 + [t.sub.3], ...,2 + [t.sub.n]), where [t.sub.1], [t.sub.2] > -3, and [t.sub.i] > -2 (i = 3, 4, ..., n) are integers. Since G and S([C.sub.3], [P.sub.h], [C.sub.3]) have the same number of edges, then

[n.summation over (i=1)] [t.sub.i] = 0. (6)

By Lemma 2, we have

[mathematical expression not reproducible]. (7)

Since [pi](G,x) = [pi](S([C.sub.3], [P.sub.h], [C.sub.3]),x), we have [b.sub.4] (G) = [b.sub.4] (S([C.sub.3], [P.sub.h], [C.sub.3])). By a simple calculation, we obtain

[n.summation over (i=1)] [t.sup.2.sub.i] = -2([t.sub.1] + [t.sub.2]). (8)

Checking (8), it is easy to see that if [absolute value of ([t.sub.1])] [greater than or equal to] 3 or [absolute value of ([t.sub.2])] [greater than or equal to] 3, then [[SIGMA].sup.n.sub.i=3] [t.sup.2.sub.i] < 0, a contradiction. Hence,

-2 [less than or equal to] [t.sub.1], [t.sub.2] [greater than or equal to] 2. (9)

Furthermore, if [t.sub.1] = -[t.sub.2] except [t.sub.1] = [t.sub.2] = 0, then [[SIGMA].sup.n.sub.i=3] [t.sup.2.sub.i] < 0, a contradiction. Thus

[t.sub.1] + [t.sub.2] = 0. (10)

Solving simultaneous equations (6)-(10), we have

[mathematical expression not reproducible]. (11)

Thus the degree sequence of G is possible ([1.sub.2], [2.sub.n-2]), (1, [2.sub.n-2], 3), or ([2.sub.n-2], [3.sup.2]). It is not difficult to check that only ([2.sup.n-2], [3.sup.2]) satisfies the well-known hand-shaking theorem. So, the degree sequence of G is ([2.sup.n-2], [3.sup.2]).

Theorem 8. Restricting consideration on quadrangle-free graphs, sandglass graphs are determined by their per-spectra.

Proof. Let G be a quadrangle-free graph with n vertices percospectral with S([C.sub.3], [P.sub.h], [C.sub.3]). By Lemma 7, we know that the degree sequence of G is ([2.sup.n-2], [3.sup.2]). Then G is isomorphic to [mathematical expression not reproducible] or [mathematical expression not reproducible], where [mathematical expression not reproducible] denotes the union of k > 0 disjoint cycles [mathematical expression not reproducible] of length [k.sub.i]. By the above, it implies that [absolute value of (V(G))] [greater than or equal to] 5. It is not difficult to see that if n = 5, then G is isomorphic to S([C.sub.3], [P.sub.h], [C.sub.3]). So, assume n >5 and consider the following two cases.

Case 1. Assume that G is isomorphic [mathematical expression not reproducible]. We further discuss the following three subcases.

Subcase 1.1. Exact one of the two triangles belongs to the bicyclic component. Then [mathematical expression not reproducible] for p = 3, q [greater than or equal to] 4, and k [greater than or equal to] 1. By Lemma 3, we obtain that [b.sub.5] (G) = -4n + 10 - 2[c.sub.5] (G). By Lemma 5, we have [b.sub.5] (S([C.sub.3], [P.sub.l], [C.sub.3])) - [b.sub.5] (G) = 2 + 2[c.sub.5] (G) > 0. This contradicts the assumption that G and S([C.sub.3], [P.sub.l], [C.sub.3]) are per-cospectral.

Subcase 1.2. Both of the two triangles belong to the bicyclic component. Then [mathematical expression not reproducible]. If k =0, then G is isomorphic to S([C.sub.3], [P.sub.l], [C.sub.3]). Next we suppose that k > 0. By the structure of G and Lemma 1, we can obtain that [b.sub.n] (G) > 5 when n is even, and [b.sub.n] (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 [mathematical expression not reproducible], for p, q [greater than or equal to] 4. By Lemma 3, we have [b.sub.5] (G) = -4n + 8- 2[c.sub.5] (G). So, [b.sub.5] (S([C.sub.3], [P.sub.l], [C.sub.3])) - [b.sub.5] (G) = 4 + 2[c.sub.5] (G) > 0. Thiscontradicts the assumption that G and S([C.sub.3], [P.sub.l], [C.sub.3]) are per-cospectral.

Case 2. Assume that G is isomorphic to [mathematical expression not reproducible]. We further consider the following three subcases.

Subcase 2.1. Exact one of the two triangles belongs to the bicyclic component. Then [mathematical expression not reproducible] for t > 2 and k [greater than or equal to] 1. By the structure of G and Lemma 1, we can obtain that if n is even, then [b.sub.n] (G) > 5; and if n is odd, then [b.sub.n] (G) < -4. By Lemma 6, this is a contradiction.

Subcase 2.2. Both of the two triangles belong to the bicyclic component. Then [mathematical expression not reproducible], 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 = d(r, s, t)UC3 U C3 U(J i=12 Ck,) 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. Let G be a connected graph, where [absolute value of (G)] = n and n [greater than or equal to] 5, and let G be per-cospectral with S([C.sub.3], [P.sub.h], [C.sub.3]). ByLemma 4, G is a bicyclic graph with two triangles and must be isomorphic to a graph containing a sandglass graph S([C.sub.3], [P.sub.l], [C.sub.3]) as its induced subgraph or [K.sub.4] - e (isomorphic to [theta]-graph when r =1 and s = t = 2) as its induced subgraph.

Suppose that G is isomorphic to a graph which contains a sandglass graph S([C.sub.3], [P.sub.l], [C.sub.3]) as its induced subgraph. Then G contains no quadrangles. By Lemma 7, G must be isomorphic to the sandglass graph S([C.sub.3], [P.sub.h], [C.sub.3]).

In the following, we will prove that G is isomorphic to a graph containing [K.sub.4] - e as its induced subgraph.

Suppose that n is even. By Lemma 6, we know that bn(S([C.sub.3], [P.sub.h], [C.sub.3])) = 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, [b.sub.n] (G) = 1, which contradicts the fact that [b.sub.n] (S([C.sub.3], [P.sub.h], [C.sub.3])) = 5.

Assume that n 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 [b.sub.n] (G) = 2. This contradicts [b.sub.n] (S([C.sub.3], [P.sub.h], [C.sub.3])) = 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. Let H be an arbitrary graph with a fixed vertex w and let [G.sub.u] x H denote the coalescence of G and H with respect to u and w, which is the graph obtained from GuH by identifying u and w. Similarly, we define [G'.sub.v] x H. Borowiecki [20] showed that if both G - u and G' - v are per-cospectral, then both [G.sub.u] x H and [G'.sub.v] x 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 [B.sub.u] x H and [B.sub.v] x H are per-cospectral.

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.

https://doi.org/10.1155/2017/7541312

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

The authors thank Dr. Shunyi Liu for providing Figure 2. The authors are supported by NSF of Qinghai (2016-ZJ-947Q) and High-level personnel of scientific research projects of QHMU(2016XJG07).

References

[1] C. Gkantsidis, M. Mihail, and E. Zegura, "Spectral analysis of internet topologies," in Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications (INFOCOM '03), vol. 1, pp. 364-374, San Francisco, Calif, USA, 2003.

[2] D. Cvetkovic' and T. Davidovic', "Multiprocessor interconnection networks," in Applications of Graph Spectra, Zbornik radova 13(21), D. Cvetkovic' and I. Gutman, Eds., vol. 13, pp. 33-63, Mathematical Institute SANU, Belgrade, Serbia, 2009.

[3] D. Cvetkovic", "Applications of Graph Spectra," in An introduction to the literature, Applications of Graph Spectra, Zbornik radova 13(21), D. Cvetkovic' and I. Gutman, Eds., pp. 7-31, Mathematical Institute SANU, Belgrade, Serbia, 2009.

[4] F. Chung and L. Lu, Complex Graphs and Networks, American Mathematical Society, Providence, Rhode Island, 2006.

[5] U. von Luxburg, "A tutorial on spectral clustering," Statistics and Computing, vol. 17, no. 4, pp. 395-416, 2007.

[6] P. V. Mieghem, "Graph spectra for complex networks," Graph Spectra for Complex Networks, pp. 1-346, 2010.

[7] L. G. Valiant, "The complexity of computing the permanent," Theoretical Computer Science, vol. 8, no. 2, pp. 189-201, 1979.

[8] E. R. van Dam and W. H. Haemers, "Which graphs are determined by their spectrum?" Linear Algebra and its Applications, vol. 373, pp. 241-272, 2003.

[9] E. R. van Dam and W. H. Haemers, "Developments on spectral characterizations of graphs," Discrete Mathematics, vol. 309, no. 3, pp. 576-586, 2009.

[10] R. Merris, K. R. Rebman, and W. Watkins, "Permanental polynomials of graphs," Linear Algebra and its Applications, vol. 38, pp. 273-288, 1981.

[11] F. Harary, C. King, A. Mowshowitz, and R. C. Read, "Cospectral graphs and digraphs," The Bulletin of the London Mathematical Society, vol. 3, pp. 321-328, 1971.

[12] W. Li, S. Liu, T. Wu, and H. Zhang, "On the permanental polynomials of graphs," in Graph Polynomials, Y. Shi and et al., Eds., CRC Press, 2016.

[13] S. Liu and H. Zhang, "On the characterizing properties of the permanental polynomials of graphs," Linear Algebra and its Applications, vol. 438, no. 1, pp. 157-172, 2013.

[14] T. Wu and H. Zhang, "Per-spectral characterizations of graphs with extremal per-nullity," Linear Algebra and its Applications, vol. 484, Article ID 13254, pp. 13-26, 2015.

[15] T. Wu and H. Zhang, "Per-spectral and adjacency spectral characterizations of a complete graph removing six edges," Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, vol. 203, pp. 158-170, 2016.

[16] T. Wu and H. Zhang, "Per-spectral characterizations of some bipartite graphs," Discussiones Mathematicae Graph Theory, 2017.

[17] H. Zhang, T. Wu, and H.-J. Lai, "Per-spectral characterizations of some edge-deleted subgraphs of a complete graph," Linear and Multilinear Algebra, vol. 63, no. 2, pp. 397-410, 2015.

[18] J. Ma, Y. Shi, Z. Wang, and J. Yue, "On Wiener polarity index of bicyclic networks," Scientific Reports, vol. 6, Article ID 19066, 2016.

[19] P. Lu, X. Liu, Z. Yuan, and X. Yong, "Spectral characterizations of sandglass graphs," Applied Mathematics Letters. An International Journal of Rapid Publication, vol. 22, no. 8, pp. 1225-1230, 2009.

[20] M. Borowiecki, "On spectrum and per-spectrum of graphs," Publications de l'Institut Mathematique, vol. 38, pp. 31-33, 1985.

Tingzeng Wu (1) and Huazhong Lu (2)

(1) School of Mathematics and Statistics, Qinghai Nationalities University, Xining Qinghai 810007, China

(2) School of Mathematics Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 610054, China

Correspondence should be addressed to Tingzeng Wu; mathtzwu@163.com

Received 17 March 2017; Accepted 7 May 2017; Published 31 May 2017

Academic Editor: Zhi-Zhong Chen

Caption: FIGURE 1: [infinity]-graph and [theta]-graph.

Caption: FIGURE 2: Graph G'.

Caption: FIGURE 3: The bicyclic network B.
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Wu, Tingzeng; Lu, Huazhong
Publication:Journal of Applied Mathematics
Article Type:Report
Date:Jan 1, 2017
Words:3586
Previous Article:Solvability of the Brinkman-Forchheimer-Darcy Equation.
Next Article:Generalized Hybrid One-Step Block Method Involving Fifth Derivative for Solving Fourth-Order Ordinary Differential Equation Directly.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters