On the Spectral Characterization of *H*-Shape Trees ()

Shengbiao Hu

Department of Mathematics, Qinghai Nationalities University, Xining, China.

**DOI: **10.4236/alamt.2014.42005
PDF
HTML
2,565
Downloads
3,954
Views
Citations

Department of Mathematics, Qinghai Nationalities University, Xining, China.

A graph *G* is said to be determined by its spectrum if any graph having the same spectrum as *G* is isomorphic to *G*. An *H*-shape is a tree with exactly two of its vertices having maximal degree 3. In this paper, a formula of counting the number of closed 6-walks is given on a graph, and some necessary conditions of a graph Γ cospectral to an *H*-shape are given.

Keywords

Spectra of Graphs, Cospectral Graphs, Spectra Radius, *H*-Shape Trees, Determined by Its Spectrum

Share and Cite:

Hu, S. (2014) On the Spectral Characterization of *H*-Shape Trees. *Advances in Linear Algebra & Matrix Theory*, **4**, 79-86. doi: 10.4236/alamt.2014.42005.

1. Introduction

Let be a simple undirected graph with vertex set and edge set E. Let be the adjacency matrix of G. Since is a real symmetric matrix, its eigenvalues must be real, and may be ordered as. The sequence of n eigenvalues is called the spectrum of G, the largest eigenvalue is often called the spectral radius of G. The characteristic polynomial of is called the characteristic polynomial of the graph G and is denoted by.

Two graphs are cospectral if they share the same spectrum. A graph G is said to be determined by its spetrum (DS for short) if for any graph H, implies that H is isomorphic to G.

Determining what kinds of graphs are DS is an old problem, yet far from resolved, in the theory of graph spectra. Numerous examples of cospectral but non-isomorphic graphs are reported in literature [1] . However, there are few results known about DS graphs. For the background and some recent surveys of the known results about this problem and related topics, we refer the reader to [2] -[6] and references therein.

Because the kind of problems above are generally very hard to deal with, some more modest ones suggested by van Dam and Haemers [2] , say, “Which trees are DS?”, this problem is also very hard to deal with, because we know a famous result of Schwenk [7] , which says that almost all trees have non-isomorphic cospectral mates.

A T-shape is a tree with exactly one of its vertices having maximal degree 3 such that, where is the path on vertices, and v is the vertex of degree 3. More recently, Wang proved that T-shape tree is DS; Wang and Xu [6] proved that T-shape tree is DS iff for any positive integer.

An H-shape is a tree with exactly two of its vertices having maximal degree 3. We denote by is an H-shape tree such that , and , where u and v are the vertices of degree 3.

In this paper, we give a formula of counting the number of closed 6-walks on a graph, and give some necessary conditions of a graph Γ cospectral to an H-shape.

2. Some Lemmas

In the section, we will present some lemmas which are required in the proof of the main result.

Lemma 2.1 [8] The characteristic polynomial of a graph satisfies the following identities:

1)2) if e = v_{1}v_{2} is a cut-edge of G.

where denotes the graph obtained from G by deleting the edge e and denotes the graph obtained from G by deleting the vertices v_{1}, v_{2} and the edges incident to it.

Lemma 2.2 [1] Let C_{n}, P_{n} denote the cycle and the path on n vertices respectively. Then

Let, set, we get, it is can be write the characteristic polynomial of C_{n}, P_{n} in the following form [6] :

(1)

(2)

Lemma 2.3 [4] [9] Let be the characteristic polynomial of graph G with n vertices, then the coefficient of λ^{n}^{−i} is

(3)

where a_{0} = 1 and the sum is over all subgraphs γ of G consisting of disjoint edges and cycles, and having i vertices. If γ is such a subgraph then comp(γ) is the number of components in it and cyc(γ) is the number of cycles.

Lemma 2.4 [2] [10] Let G be a graph. For the adjacency matrix, the following can be obtained from the spectrum.

1) The number of vertices.

2) The number of edges.

3) Whether G is regular.

4) Whether G is regular with any fixed girth.

5) The number of closed walk of any length.

6) Whether G is bipartite.

3. Main Results

The total number of closed k-walks in a graph G, denoted by.

Lemma 3.1 ([6] p. 657) Let G be a graph with e edges, x_{i} vertices of degree i, and y 4-cycles. Then

(4)

Lemma 3.2 Let Γ be a graph with n vertices. If Γ cospectral to an H-shape and Γ ≠ W_{n}, then 1) Γ have the same degree sequences as the H-shape tree or Γ have the degree sequences.

2) Γ contains no 4-cycles.

Proof. Let Γ be a graph with e edges, x_{i} vertices of degree i, and y 4-cycles. By lemma 2.4 we known that cospectral graphs have the same number of edges and closed 4-walks, respectively. Since Γ is cospectral to an H-shape tree, hence by (4) we have

namely

(5)

Since

(6)

from (5), we have

(7)

the (7) imply to y = 1 or 0.

Case 1. y = 1. by (7) we get x_{0} = 0 and, by (5) we get and x_{1} = 2, then.

We known that “the spectrum of graph W_{n} is the union of the spectra of the circuit C_{4} and the path P_{n}_{−4}” [1] , that is

Case 2. y = 0. By (7) we have x_{0 }≤ 2.

If x_{0} = 0, then, by (5) we get and x_{1}= 4. Thus Γ have the same degree sequences as the H-shape tree.

If x_{0} = 1, then and x_{1} = 1. The degree sequences of Γ is.

If x_{0} = 2, then, x_{2} = n, , a contradiction.

Lemma 3.3 Let G be a graph with e edges, x_{i} vertices of degree i, and z 6-cycles. Then

(8)

where p_{4} is the number of induced paths of length three and k_{1,3} is the number of induced star K_{1,3}.

Proof. A close walk of length 6 can be produced from in the following five classes graphs, they are P_{2}, P_{3}, P_{4}, K_{1,3} and C_{6}. For an edge and a 6-cycle, it is easy to see that the number of close 6-walks equals 2 and 12, respectively. For a P_{3}, the number of close 6-walks of a 1-degree vertex is 3 and the number of close 6-walks of the 2-degree vertex is 6, since the number of induced paths of length two is, hence for all induced paths P_{3}, the number of close 6-walks is. For a P_{4}, since the number of close 6-walks of a 1-degree vertex is 1 and the number of close 6-walks of a 2-degree vertex is 2, hence for all induced paths P_{4}, the number of close 6-walks is 6p_{4}. Similarly, for a K_{1,3,} the number of close 6-walks of a 1-degree vertex is 2 and the number of close 6-walks of the 3-degree vertex is 6, thus for all induced stars K_{1,3}, the number of close 6-walks is 12k_{1,3}.

Corollary 3.4 Let, then

(9)

where.

Proof. Case 1. l_{1} ≥1.

1) If k = 0, that is, then

where and are the number of induced paths P_{4} in. and, respectively. The 8(= 4 + 4) is the number of induced paths of through a 3-degree vertex u (or v). If P_{4} is such a induced path, then u is an internal vertex in the P_{4} and have at least a vertex in the (or).

2) If k ≠ 0, then

Case 2. l_{1} = 0.

1) If k ≠ 0, then

2) If k = 0, similarly, we have.

Example 1. Let, by (9) we have

if we give to a suitable label for the H_{1}, by a simple calculation we can get the diagonal matrix of, that is

clearly, the sum of the elements in the diagonal matrix equals 4 × 11 + 2 × 43 = 130.

Example 2. Let, by (9) we have, similarly, if we give to a suitable label for the H_{2}, then we can get the diagonal matrix of, that is

clearly, the sum of the elements in the diagonal matrix equals 4 × 6 + 4 × 22 + 2 × 29 + 2 × 49 = 268.

Lemma 3.5 Let Γ be a graph with n vertices, e edges, x_{i} vertices of degree i, and z 6-cycles. If Γ cospectral to and Γ ≠ W_{n}, then

(10)

where is the number of elements of equals 1 in and p_{4} is the number of induced paths of length three and k_{1,3} is the number of induced star K_{1,3} in Γ.

Proof. If l_{1} ≥ 1, by Lemma 3.3 we have

Similarly, when l_{1} = 0 the (10) hold.

Definition 1. Let U be a graph obtained from a cycle C_{g }(g is even and 6 ≤ g ≤ n_{1} − 2) and a path, such that identifying an end vertex in the path and any one vertex in the cycle, and uniting an isolated vertex K_{1}.

If a graph have the degree sequences, then the graph is U uniting some cycle.

Lemma 3.6 Let U′ be a graph with degree sequences. If U′ cospectral to an H-shape, then U′ and H satisfying one of the following conditions.

1) There are one 6-cycle in U′ and l_{1} ≥ 1, l_{2}, l_{3}, l_{4}, l_{5} ≥ 2.

2) There are one 6-cycle in U′ and l_{1} = 0, have an element is 1 in.

3) No 6-cycle in U′ and l_{1} ≥ 1, have two elements are 1 in.

4) No 6-cycle in U′ and l_{1} = 0, have three elements are 1 in.

Proof. Without loss of generality, Let, where is even and n_{1} + n_{2} = n. Let U′ have e edges, x_{i} vertices of degree i, and z 6-cycles.

Case 1. l_{1} ≥ 1. By Lemma 3.5 we have, get k = 0, z = 1 or k = 2, z = 0.

Case 2. l_{1} = 0, we have, get k = 1, z = 1 or k = 3, z = 0.

Lemma 3.7 Let, then

(11)

Proof. By Lemma 2.1 (b) and Lemma 2.2 we have

(12)

If a graph has the same degree sequences as the H-shape, then Γ is one of the following graphs G_{1}, G_{2}, G_{3}, G_{4}, G_{5} in figure or it is an H-shape.

Lemma 3.8 If Γ is cospectral to an H-shape tree, then Γ contains no as two connected component.

Proof. Assume that Γ contains aas a connected component, by (11) some li is equal, without loss of generality, let l_{1} = l_{2} = l_{4} = n_{1}, then

If Γ contains a as a connected component, then l_{3} = l_{5} and l_{1} + l_{3} + 1 = l_{1}, a contradiction.

Thus, if a graph cospectral to an H-shape and have the same degree sequences as the H-shape, then Γ is one of the following graphs G_{3}, G_{4}, G_{5} (Fig.) uniting some even cycle, respectively, or it is an H-shape.

Lemma 3.9 If and are cospectral, then

Proof. By (11) we have

(13)

(14)

where. By (14) we have

Let, without loss of generality, we assume that l_{2} ≥ l_{3} ≥ l_{4} ≥ l_{5} and m_{2} ≥ m_{3} ≥ m_{4} ≥ m_{5}. Comparing the 4^{th} lowest term of and, we get m_{5} = l_{5}. Similarly, we comparing the 5^{th}, 6^{th} and 7^{th} lowest term of and, respectively, we get m_{4} = l_{4}, m_{3 }= l_{3} and m_{2} = l_{2}. By , we get m_{1} = l_{1}, thus

Lemma 3.10 Let G_{5} be a graph in Figure, then G_{5} and H-shape are not cospectral.

Proof. Let , that is . Denote the first component by G_{5,1 }and the second component by G_{5,2}. By Lemma 2.1 and_{ }Lemma 2.3 we have

By Lemma 2.1 (a) we have

(15)

Comparing (14) and (15), since for any and for any , hence. G_{5 }and H-shape are not cospectral.

Remark. If G_{5} uniting some, without loss of generality, let, where m_{1} + m_{2} + m_{3} + m_{4} + m_{5} + 1 = n_{1}. Since, we have , ,. Thus, G_{5,1} and H-shape are not cospectral.

Theorem 3.11 Let , if a graph Γ (Γ ≠ W_{n}) cospectral to an H-shape, then either Γ is U (Definition 1) uniting some even cycles (n_{i} ≥ 6), denoted by U′, and U′, H satisfying one of the following conditions.

1) There are one 6-cycle in U′ and l_{1} ≥ 1, l_{2}, l_{3}, l_{4}, l_{5} ≥ 2.

2) There are one 6-cycle in U′ and l_{1} = 0, have 1 element is 1 in.

3) No 6-cycle in U′ and l_{1} ≥ 1, have 2 elements are 1 in.

4) No 6-cycle in U′ and l_{1} = 0, have 3 elements are 1 in, or Γ is the graph G_{3} and G_{4 }in Figure uniting some even cycles, respectively.

Proof. This result is contained from Lemma 3.2 up to Lemma 3.10.

Funding

This work is supported by the Natural Science Foundation of Qinghai Province (Grant No. 2011-Z-911).

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | Cvetkovi'c, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs—Theory and Application. Academic Press, New York. |

[2] | van Dam, E.R. and Haemers, W.H. (2003) Which Graph Are Determined by Their Spectrum? Linear Algebra and Its Applications, 373, 241-272. http://dx.doi.org/10.1016/S0024-3795(03)00483-X |

[3] |
Doob, M. and Haemers, W.H. (2002) The Complement of the Path Is Determined by Its Spectrum. Linear Algebra and Its Applications, 356, 57-65. http://dx.doi.org/10.1016/S0024-3795(02)00323-3 |

[4] | Noy, M. (2003) Graphs Determined by Polynomial Invariants. Theoretical Computer Science, 307, 365-384. |

[5] | Smith, J.H. (1970) Some Propertice of the Spectrum of Graph. In: Guy, R., et al., Eds., Combinatorial Structure and Their Applications, Gordon and Breach, New York, 403-406. |

[6] |
Wang, W. and Xu, C.-X. (2006) On the Spactral Characterization of T-Shape Trees. Linear Algebra and Its Applications, 414, 492-501. http://dx.doi.org/10.1016/j.laa.2005.10.031 |

[7] | Schwenk, A.J. (1973) Almost All Trees Are Cospectral. In: Harary, F., Ed., New Directions in the Theory of Graphs, Academic Press, New York, 275-307. |

[8] | Godsil, C.D. (1993) Algebraic Combinatorics. Chapman & Hall, New York. |

[9] | Sachs, H. (1964) Beziehungen zwischen den in einem graphen enthaltenen kreisenund seinem charakteristischen polynom. Publicationes Mathematicae, 11, 119-134. |

[10] |
Omidi, G.R. and Tajbakhsh, K. (2007) Starlike Trees Are Determined by Their Laplacian Spectrum. Linear Algebra and Its Applications, 422, 654-658. http://dx.doi.org/10.1016/j.laa.2006.11.028 |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.