R Boulet
email: boulet@univ-tlse2.fr

B Jouve
email: jouve@univ-tlse2.fr

Keywords:

An even (resp. odd) lollipop is the coalescence of a cycle of even (resp. odd) length and a path with pendant vertex as distinguished vertex. It is known that the odd lollipop is determined by its spectrum and the question is asked by W. Haemers, X. Liu and Y. Zhang for the even lollipop. We revisit the proof for odd lollipop, generalize it for even lollipop and therefore answer the question. Our proof is essentially based on a method of counting closed walks.

Introduction

Let G be a simple graph with n vertices and A its adjacency matrix, Q G (X) denotes its characteristic polynomial and λ 1 (G) ≥ λ 2 (G) ≥ • • • ≥ λ n (G) the associated eigenvalues; λ 1 (G) is the spectral radius of G. It is known that some informations about the graph structure can be deduced from these eigenvalues such as the number of edges or the length of the shortest odd cycle; but the reverse question Which graphs are determined by their spectrum ? (asked, among others, in [START_REF] Van Dam | Which graphs are determined by their spectrum? Linear Algebra and its Applications[END_REF]) is far from being solved; some partial results exist [START_REF] Doob | The complement of the path is determined by its spectrum[END_REF][START_REF] Shen | Graph Z n and some graphs related to Z n are determined by their spectrum[END_REF][START_REF] Wang | On spectral characterisation of T-shape trees[END_REF] which contribute to answer this question.

Let us remind that the coalescence of two graphs G 1 with distinguished vertex v 1 and G 2 with distinguished vertex v 2 , is formed by identifying vertices v 1 and v 2 that is, the vertices v 1 and v 2 are replaced by a single vertex v adjacent to the same vertices in G 1 as v 1 and the same vertices in G 2 as v 2 . If it is not necessary v 1 or v 2 may not be specified.

A lollipop L(p, k) is the coalescence of a cycle C p with p ≥ 3 vertices and a path P k+1 with k + 1 ≥ 2 vertices with one of its vertex of degree one as distinguished vertex, figure 1 shows an example of a lollipop. The lollipop L(p, 0) is C p . An even (resp. odd) lollipop has a cycle of even (resp. odd) length. In this paper we shall show that the lollipop graph is determined by its spectrum, answering to an open question asked in [START_REF] Haemers | Spectral characterizations of lollipop graphs[END_REF][START_REF] Van Dam | Developments on spectral characterizations of graphs[END_REF] for even lollipop. It is known [START_REF] Haemers | Spectral characterizations of lollipop graphs[END_REF] that the odd lollipop is determined by its spectrum, but the proof given in [START_REF] Haemers | Spectral characterizations of lollipop graphs[END_REF] cannot be generalized for even lollipops. We revisit here this proof in order to generalize it to even lollipops.

Figure 1: Lollipop L [START_REF] Favaron | Some eigenvalues properties in graphs (conjectures of graffiti -ii)[END_REF][START_REF] Van Dam | Which graphs are determined by their spectrum? Linear Algebra and its Applications[END_REF] We describe in section 2 some basic results of spectral graph theory we shall use in the following of the paper. We also explain the method we use to count closed walks in a graph and revisit two proofs of results about lollipops. The main section of the paper (section 3) shows that the even lollipop is determined by its spectrum; the proof is based on two points: connectivity of a graph cospectral with an even lollipop and existence of a 4-cycle in a graph cospectral with a L(4, k).

To fix notations, the disjoint union of two graphs G and H is noted G ∪ H. As defined in [START_REF] Wang | On spectral characterisation of T-shape trees[END_REF] a T-shape tree S a,b,c (a, b, c > 0) is a tree with one and only one vertex v of degree 3 such that S a,b,c \{v} = P a ∪ P b ∪ P c . We extend this notation for all b, c ∈ N by S 0,b,c = P b+c+1 .

0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 Figure 2: S 1,2,2
By S n-1 we denote the star with n vertices and by T n the tree with n vertices drawn on figure 3. Finally let d(u, v) be the distance (the length of a shortest path) between two vertices u and v and δ(v) the degree of a vertex v.

0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 n-6 vertices
2 Basic results and revisited proofs

Counting the closed walks

It is a classical result that the number of closed walks of length k ≥ 2 is i λ k i

We describe here a method to count the number of closed walks of a given length within a graph.

Let M be a graph, a k-covering closed walk in M is a closed walk of length k in M running through all the edges at least once. Let G be a graph, M(G) denotes the set of all distinct subgraphs (not necessarily induced) of G isomorphic to M and |M(G)| is the number of elements of M(G). According to that point of view, M may be called a motif (or a pattern). The number of k-covering closed walks in a motif M is denoted by w k (M) and we define the set M k (G) = {M, w k (M) > 0} which is finite if G is a finite graph.

As a consequence, the number of closed walks of length k in G is:

i λ k i = M ∈M k (G) w k (M)|M(G)| (1)
In practice, there are at least two methods to determine w k (M): on one hand a combinatorial way which counts the number of covering closed walks of length k in M, on the other hand an algebraic method which uses the following straightforward formula:

w k (M) = λ i ∈Sp(M ) λ k i - M ′ ∈M k (M ),M ′ =M w k (M ′ )|M ′ (M)|
where Sp(M) denotes the spectrum of the adjacency matrix of M.

Using equation [START_REF] Cvetkovic | Spectra of graphs[END_REF] and table 5 in appendix, we have the following proposition:

Proposition 1. i) If G is a graph without triangles and C 5 then: In this paper we shall have to count all the |M(G)|, M ∈ M i (G) of a given unicyclic graph G. For that aim we describe here the steps of the process we follow to count the P k (G) which are the only motifs hard to denombrate. Let p be the length of the cycle of G.

ALGORITHM to count P k (G):

set

H = G set |P k (G)| = 0.
while there exists a pendant vertex u in H do count the number q of paths P k of H containing u

let |P k (G)| = |P k (G)| + q let H = H\{u} end while if p ≥ k then |P k (G)| = |P k (G)| + p end if return |P k (G)|

Known results

Proposition 2. [START_REF] Cvetković | Spectra of unicyclic graphs[END_REF] Let G be a graph with n vertices and m edges and let λ i its associated eigenvalues. We have:

i λ 4 i = 8|C 4 (G)| + 2m + 4|P 3 (G)|.
Let n k be the number of vertices of degree k in G, we have:

i λ 4 i = 8c 4 + k kn k + 4 k≥2 k(k -1) 2 n k
The following result relates the coefficients of the characteristic polynomial of a graph with structural properties of this graph:

Theorem 1. [1] Let Q G (X) = X n + a 1 X n-1 + a 2 X n-2 + ... + a n
be the characteristic polynomial of a graph G. We call an "elementary figure" the graph P 2 or the graphs C q , q > 0. We call a "basic figure" U every graph all of whose components are elementary figures. Let p(U) be the number of connected components of U and c(U) the number of cycles in U. We note U i the set of basic figures with i vertices. Then

a i = U ∈U i (-1) p(U ) 2 c(U ) , i = 1, 2, ..., n
It follows this theorem:

Theorem 2. [1] Let Q G (X) = X n + a 1 X n-1 + a 2 X n-2 + ... + a n
be the characteristic polynomial of a graph G. The length of the shortest odd cycle in G is given by the smallest odd index p such that a p = 0 and the value of a p gives the number of p-cycles in G.

It ensues that a bipartite graph (ie a graph with no odd cycles) cannot be cospectral with a non-bipartite graph.

The following result is useful at many time in the paper, for instance to find bounds on eigenvalues: Theorem 3 (Interlacing theorem). [START_REF] Godsil | Algebraic Graph Theory[END_REF] Let G be a graph with n vertices and associated eigenvalues λ 1 ≥ λ 2 ≥ ... ≥ λ n and let H be an induced subgraph of G with m vertices and associates eigenvalues

µ 1 ≥ µ 2 ≥ ... ≥ µ m . Then for i = 1, ..., m, λ n-m+i ≤ µ i ≤ λ i .
The next theorems give a way to compute the characteristic polynomial of a graph by deleting a vertex or an edge: Theorem 4. [START_REF] Cvetkovic | Spectra of graphs[END_REF] Let G be a graph obtained by joining by an edge a vertex x of a graph G 1 and a vertex y of a graph G 2 . Then

Q G (X) = Q G 1 (X)Q G 2 (X) -Q G 1 \x (X)Q G 2 \y (X)
Theorem 5. [START_REF] Cvetkovic | Spectra of graphs[END_REF] Let G be a graph and x a vertex of G, then:

Q G (X) = XQ G\x (X) - y∼x Q G\{x,y} (X) -2 C, x∈C Q G\C (X)
where y ∼ x means that yx is an edge of G and the second sum is on the set of the cycles C containing x. Theorem 6. [START_REF] Cvetkovic | Spectra of graphs[END_REF] Let G be a graph and x a pendant vertex of G. Then:

Q G (X) = XQ G\x (X) -Q G\x,y (X)
where y is the neighbor of x.

Property 1. We have the following equalities:

Q Cp (X) = XQ P p-1 (X) -2Q P p-2 (X) -2 Q Pp (X) = XQ P p-1 (X) -Q P p-2 (X)
Proof. A direct consequence of theorems 4 and 6.

The following theorem relates the behavior of the spectral radius of a graph by subdividing an edge. An internal path of a graph G is an elementary path

x 0 x 1 • • • x k (ie x i = x j for all i = j but eventually x 0 = x k ) of G with δ(x 0 ) > 2, δ(x k ) > 2, δ(x i ) = 2 for all other i's.
Theorem 7. [START_REF] Simić | On the largest eigenvalue of some homeomorphic graphs[END_REF][START_REF] Hoffman | On the spectral radii of topologically equivalent graphs[END_REF] Let xy be an edge of a connected graph G not belonging to an internal path, then the spectral radius strictly increases by subdividing xy. Let xy be an edge of a connected graph G = T n belonging to an internal path, then the spectral radius strictly decreases by subdividing xy. Theorem 8. [START_REF] Favaron | Some eigenvalues properties in graphs (conjectures of graffiti -ii)[END_REF] Let G be a graph with maximal degree δ M , then λ 1 (G) ≥ √ δ M Let B(p, q) be the coalescence of two cycles C p and C q (see figure 4 for an example).

Theorem 9. [11] For p ≥ 3, q ≥ 3, λ 1 (B(p, q)) > 4 √ 3 > √ 5 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 Figure 4: B(8,5)

Bounds on eigenvalues

Theorem 7 gives the following corollaries:

Corollary 1. λ 1 (L(p, k)) > λ 1 (L(p + 1, k)) Corollary 2. λ 1 (L(p, k)) < λ 1 (L(p, k + 1))
Given p ≥ 3, q ≥ 3, let H(p, q) be the coalescence of C p and L(q, 1) with the pendant vertex as distinguished vertex (see figure 5 for an example).

0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 Figure 5: H(6,8) Theorem 10. λ 1 (H(p, q)) > √ 5.
Proof. Without loss of generality we suppose that p ≥ q. According to theorem 7 we have λ 1 (H(p, q)) ≥ λ 1 (H(p, p)) so it is sufficient to prove the theorem for H(p, p). As

lim x→+∞ Q H(p,q) (x) = +∞ it is sufficient to prove that Q H(p,p) ( √ 5) < 0 Theorem 4 gives: Q H(p,p) (X) = Q Cp (X)Q Cp (X) -Q P p-1 (X)Q P p-1 (X) Q H(p,p) (X) = [Q Cp (X)] 2 -[Q P p-1 (X)] 2
and by property 1 we have:

Q H(p,p) (X) = [XQ P p-1 (X) -2Q P p-2 (X) -2] 2 -[Q P p-1 (X)] 2
Let (u n ) n∈N be the sequence defined by u n = Q Pn ( √ 5). We have (property 1):

u n = √ 5u n-1 -u n-2 . Since u 1 = √ 2 and u 2 = 4 then u n = β n+1 1 -β n+1 2 where β 1 = √ 5+1 2 and beta 2 = √ 5-1 2 . Q H(p,p) ( √ 5) = [ √ 5u p-1 -2u p-2 -2] 2 -(u p-1 ) 2 = [( √ 5 + 1)β p-1 1 -2][( √ 5 -1)β p-1 2 -2]
We have [(

√ 5 + 1)β p-1 1 -2] > 0 and [( √ 5 -1)β p-1 2 -2] < 0 so Q H(p,p) ( √ 5) < 0.
Theorem 11. For k = 0 we have λ 1 (L(p, k)) > 2 and λ 2 (L(p, k)) < 2.

Proof. λ 1 (L(p, k)) > 2: the spectral radius of a cycle is 2 and a cycle is an induced subgraph of L(p, k) so by the interlacing theorem we have λ

1 (L(p, k)) ≥ 2. It remains to show that λ 1 (L(p, k)) = 2. By theorem 4 we have Q L(p,k) (2) = Q Cp (2)Q P k (2) -Q P p-1 (2)Q P k-1 (2) = -Q P p-1 (2)Q P k-1
(2) = 0 (because the spectral radius of a path is strictly less than 2).

λ 2 (L(p, k)) < 2: the path P p+k-1 is an induced subgraph of L(p, k) so by the interlacing theorem we have λ 2 (L(p, k)) ≤ λ 1 (P p+k-1 ) < 2.

Theorem 12. We have λ 1 (L(p, k)) < √ 5.

Proof. By corollary 1 we have

λ 1 (L(p, k)) ≤ λ 1 (L(3, k)) so it is sufficient to prove the theorem for p = 3. For k = 0, λ 1 (L(3, 0)) = 2 < √ 5.
We now assume that k > 0. Using theorem 4 and Q C 3 (X) = (X + 1) 2 (X -2) we have:

Q L(3,k) (X) = (X + 1) 2 (X -2)Q P k (X) -(X -1)(X + 1)Q P k-1 (X) and Q L(3,k) ( √ 5) = (2 √ 5 -2)Q P k ( √ 5) -4Q P k-1 ( √ 5) Let us suppose that Q L(3,k) ( √ 5) > 0. We have Q L(3,k+1) ( √ 5) = (2 √ 5 -2)Q P k+1 ( √ 5) -4Q P k ( √ 5) but Q P k+1 ( √ 5) = √ 5Q P k ( √ 5) -Q P k-1 ( √ 5) so Q L(3,k+1) ( √ 5) = 2 √ 5 -2 4 (2 √ 5 -2)Q P k ( √ 5) -4Q P k-1 ( √ 5)
and by induction on k ≥ 1 we have

Q L(3,k+1) ( √ 5) > 0.
Since the polynomial Q L(3,k) has one and only one root in ]2, +∞[ (theorem 11) then

Q L(3,k) (2) < 0 and Q L(3,k) ( √ 5) > 0 implies that λ 1 (L(3, k)) < √ 5.
Theorem 13. Let G be a graph cospectral with L(p, k), then max{δ(v), v ∈ V (G)} ≤ 4.

Proof. A direct consequence of theorems 12 and 8.

Theorem 14. Let G be a graph cospectral with a lollipop. Then, for p ≥ 3 and q ≥ 3, C p ∪ C q or H(p, q) or B(p, q) cannot be induced subgraphs of G Proof. If C p ∪ C q is an induced subgraph of G then as λ 2 (C p ∪ C q ) = 2 by interlacing theorem we get λ 2 (G) ≥ 2, impossible by theorem 11. H(p, q) or B(p, q) cannot be induced subgraphs of G because λ 1 (G) < √ 5 (theorem 12) and λ 1 (H(p, q)) > √ 5 (theorem 10), λ 1 (B(p, q)) > √ 5 (theorem 9).

2.4

There are no cospectral non-isomorphic lollipops: revisited proof

In [START_REF] Haemers | Spectral characterizations of lollipop graphs[END_REF] it is proved that two cospectral lollipops are isomorphic. We revisit here this result in a shortest proof using closed walks.

Theorem 15. There are no cospectral non-isomorphic lollipops.

Proof. Let L(p, k) and L(p ′ , k ′ ) with n = p + k = p ′ + k ′ and p < p ′ be two non isomorphic lollipops. To show that they have different spectra we show that there are less closed walks of length p in L(p ′ , k ′ ) than in L(p, k). Let e (resp. e ′ ) be an edge of the cycle of L(p, k) (resp. L(p ′ , k ′ )) incident to the vertex of degree 3, W (resp W ′ ) the set of closed walks of length p of L(p, k) (resp. L(p ′ , k ′ )), Ŵ (resp Ŵ′ ) the set of closed walks of length p of L(p, k) (resp. L(p ′ , k ′ )) not containing e (resp. e ′ ) and W (resp W′ ) the set of closed walks of length p of L(p, k) (resp. L(p ′ , k ′ )) containing e (resp. e ′ ). We have:

|W| = | Ŵ| + | W| (resp. |W ′ | = | Ŵ′ | + | W′ |). It's obvious that | Ŵ| = | Ŵ′ | because L(p, k)\{e} = L(p ′ , k ′ )\{e ′ } = P n . We are going to show that | W| < | W′ | by the following equation: | W| = M ∈Mp, e∈E(M ) w p (M)|M(G)|
where E(M) is the set of the edges of M.

We denote by M e a motif M containing e. The motifs containing e (resp e ′ ) with at least one p-covering closed walk are exactly :

• the P i 's for 2 ≤ i ≤ p 2 + 1 and we have |P e ′ i (L(p ′ , k ′ ))| ≤ |P e i (L(p, k))|. • the S a

The odd lollipop is determined by its spectrum: revisited proof

We revisit here the proof that the odd lollipop is determined by its spectrum. The aim of the proof is to determine the degree distribution. We already know that there are no vertices of degree greater or equal than 5 (theorem 13).

Lemma 1. Let G be a graph cospectral with L(p, k), p odd. Then G has no isolated vertices.

Proof. We have to show that 0 is not an eigenvalue of L(p, k) that is the constant coefficient, a n , of the characteristic polynomial of L(p, k) is non-zero. According to theorem 1 we have:

a n = U ∈Un (-1) p(U ) 2 c(U ) But |U n | = 1 :
• if k is odd, then U n is the disjoint union of p+k 2 paths P 2 , and a n = (-1)

p+k 2 = 0.
• If k is even then U n is the disjoint union of k 2 paths P 2 and a cycle C p , and a n = (-1)

k 2 +1 2 = 0. Lemma 2.
Let G be a graph cospectral with L(p, k), p odd. Then there are no 4-cycles in G.

Proof.

Let us remark that an odd closed walk necessary runs through an odd cycle. As G and L(p, k) have the same characteristic polynomial, according to theorem 2, the length of the shortest odd cycle of G is p and there is only one such cycle, so M p+2 (G) ⊂ {C p , L(p, 1), C p+2 }. Using equation [START_REF] Cvetkovic | Spectra of graphs[END_REF] we have:

λ i ∈Sp(G) λ p+2 i = w p+2 (C p )|C p (G)| + w p+2 (L(p, 1))|L(p, 1)(G)| + w p+2 (C p+2 )|C p+2 (G)| = w p+2 (C p ) + (2p + 4)|L(p, 1)(G)| + (2p + 4)|C p+2 (G)| (2)
and

λ i ∈Sp(L(p,k)) λ p+2 i = w p+2 (C p ) + (2p + 4) (3)
= 0, n 3 = 1, n 1 = 1, n 2 = n -2.
As the sum of the degrees of a graph is even, the vertex of degree 1 and the vertex of degree 3 belongs to the same connected component. If G is not connected there is a 2regular connected component (ie a cycle) which is impossible (2 is not an eigenvalue of G). As a result, G is a connected graph with degree distribution equal to (1, 2, 2, 2, ..., 2, 2, 3), so G is a lollipop and, by theorem 15, G is isomorphic to L(p, k).

3 The even lollipop is determined by its spectrum.

Following the same method as the one used for the odd case, to prove that the even lollipop is determined by its spectrum we show that a graph cospectral with an even lollipop:

• is connected (and then it contains no isolated vertices).

• has a 4-cycle if and only if it is cospectral with a L(4, k).

For the second point the difficulty is to prove that a graph cospectral with a L(4, k) has a 4-cycle.

To lighten the section some technical proofs have been detailed in appendix.

Connectivity

Using results of section 2.2 we easily obtain the following property:

Property 2. ∀a, b, c ∈ N, Q Cp (2) = 0, Q P k (2) = k + 1, Q S a,b,c (2) = a + b + c + 2 -abc, Q S 1,1,a (2) = 4
The following theorem gives a better bound than the theorem 12 on spectral radius of a lollipop L(p, k) when p ≥ 4.

Theorem 17. i) Let G be a graph cospectral with L(p, k) with p ≥ 6, then λ 1 (G) < 2.17. ii) Let G be a graph cospectral with L(4, k), then λ 1 (G) < 2 + 2 √ 2.
Proof. Just follow the proof of theorem 12 mutatis mutandis.

Let P (p 1 , p 2 , p 3 ) be the graph obtained by identifying the three pendant vertices of S p 1 +1,p 2 +1,p 3 +1 (an example is given in figure 6). Theorem 18. The graph P (p 1 , p 2 , p 3 ) cannot be an induced subgraph of a graph G cospectral with an even lollipop.

0 0 1 1 0 0 1 1 0 0 1 1 00 00 00 11 11 11 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Proof. Sketch of the proof :

We first show that for some values of p 1 , p 2 and p 3 we have λ 1 (P (p 1 , p 2 , p 3 )) > 2 + 2 √ 2 and in these cases P (p 1 , p 2 , p 3 ) cannot be an induced subgraph of G.

For the others cases we compute

Q P (p 1 ,p 2 ,p 3 ) (2).
• if Q P (p 1 ,p 2 ,p 3 ) (2) ≥ 0 then P (p 1 , p 2 , p 3 ) and a fortiori G (interlacing theorem) possesses two eigenvalues greater than 2 which contradicts that G is cospectral with a lollipop (theorem 11) .

• if Q P (p 1 ,p 2 ,p 3 ) (2) < 0 then we show that P (p 1 , p 2 , p 3 ) cannot be a connected component of G so there is a vertex x not in P (p 1 , p 2 , p 3 ) adjacent to a vertex y of P (p 1 , p 2 , p 3 ) and we prove that this graph so constructed cannot be an induced subgraph of G.

A detailed proof is given in appendix A.

Theorem 19. Let G be a graph cospectral with an even lollipop. Then G is connected.

Proof. The graph G has as many edges as vertices, so if G is not connected, it possesses at least two cycles. The subgraph induced by the two cycles of minimal length is C a ∪ C b , B(a, b), H(a, b) or P (p 1 , p 2 , p 3 ) but this is impossible (theorems 14 and 18). Corollary 3. A graph cospectral with an even lollipop is unicyclic.

The even lollipop L(p, k), p ≥ 6, is determined by its spectrum

Let G be a graph cospectral with an even lollipop L(p, k), p ≥ 6. In order to copy the proof of theorem 16 concerning the odd lollipop we have to show that |C 4 (G)| = 0 (G does not have a 4-cycle), this is the aim of the following proposition.

Proposition 3. A graph cospectral with an even lollipop L(p, k), p ≥ 6 does not have a 4-cycle.

Proof. Let G be a graph cospectral with an even lollipop L(p, k), p ≥ 6 and suppose that G has a 4-cycle. As G is connected, unicyclic and has at least 6 vertices then one of the graph drawn in figure 7 is an induced subgraph of G and we check that the spectral radius of theses graphs is greater than 2.17. We can now state:

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1
Theorem 20. The even lollipop L(p, k), p ≥ 6, is determined by its spectrum.

The even lollipop L(4, k) is determined by its spectrum

Let G be a graph cospectral with L(4, k), the main point is to show that the converse implication of previous proposition 3 holds, that is G has a 4-cycle. The key theorem of this part requires to study the cospectrality of some classes of unicyclic graphs with a lollipop L(4, k), this is done in the sections 3.3.2, 3.3.3, 3.3.4, 3.3.5.

Our toolbox: some results on L(4, k)

In the following we are going to prove that L(4, k) is not cospectral with some unicyclic graphs. For that purpose we use several tools detailed in this section: counting closed walks of length 6, 8 or 10, evaluating the characteristic polynomial in 1 or 2, using the fact that a lollipop has only one eigenvalue greater than 2. Proposition 4. i) For L(4, k), k > 1 we have:

i λ 6 i = 20n + 96 ii) For L(4, k), k > 2 we have: i λ 8 i = 70n + 596 iii) For L(4, k), k > 3 we have i λ 10 i = 252n + 3360 Proof. Counting closed walks, we check that i) For k > 1, |P 2 (L(4, k))| = n, |P 3 (L(4, k))| = n+ 1, |P 4 (L(4, k))| = n+ 2, |C 4 (L(4, k))| = 1, |L(4, 1)(L(4, k))| = 1. ii) Moreover, for k > 2, |P 5 (L(4, k))| = n -1, |S 1,1,1 (L(4, k))| = 3, |S 1,1,2 (L(4, k))| = 3, |L(4, 2)(L(4, k))| = 1. iii) Moreover, for k > 3, |P 6 (L(4, k))| = n -2, |S 1,2,2 (L(4, k))| = 2, |S 1,1,3 (L(4, k))| = 1, |L(4, 2)(L(4, k))| = 1, |L(4, 3)(L(4, k))| = 1 and apply proposition 1. Property 3. We have Q Pp (1) = Q P p (1) and Q Cp (1) = Q C p (1)
where p is p modulo 6 and:

Q P 0 (1) = 1 Q C 0 (1) = 0 Q P 1 (1) = 1 Q C 1 (1) = -1 Q P 2 (1) = 0 Q C 2 (1) = -3 Q P 3 (1) = -1 Q C 3 (1) = -4 Q P 4 (1) = -1 Q C 4 (1) = -3 Q P 5 (1) = 0 Q C 5 (1) = -1 Proof. According to property 1, Q Pp (1) = Q P p-1 (1) -Q P p-2 (1) = -Q P p-3 (1) = Q P p-6 (1) and Q Cp (1) = Q P p-1 (1) -2Q P p-2 (1) -2. Then we can easily compute Q P i and Q C i for 0 ≤ i ≤ 5.
Property 4. We have:

Q P k (0) = (-1) k 2 if k is even 0 if k is odd and if k is odd we have R(0) = (-1) k-1 2 k+1 2 where R(X) = Q P k (X) X .
Proof. Proofs by induction with the relation

Q P k (X) = XQ P k-1 (X) -Q P k-2 (X).
Proposition 5. We have:

Q L(4,k) (1) =                1 if n ≡ 0[6] 3 if n ≡ 1[6] 2 if n ≡ 2[6] -1 if n ≡ 3[6] -3 if n ≡ 4[6] -2 if n ≡ 5[6] Proof. Theorem 4 gives Q L(4,k) (X) = Q C 4 (X)Q P k (X)-Q P 3 (X)Q P k-1 (X) so Q L(4,k) (1) = -3Q P k (1) + Q P k-1 (1)
and we conclude with property 3.

Proposition 6. Q L(4,k) (2) = -4n + 16. Proof. Q L(4,k) (X) = Q C 4 (X)Q P k (X) -Q P 3 (X)Q P k-1 (X) and with property 2 we have Q L(4,k) (2) = -4k = -4n + 16.
Remark : This proposition can be generalized for all lollipops :

Q L(p,k) (2) = -pk. Proposition 7. If n = 4 + k is even then 0 is an eigenvalue of L(4, k) with multiplicity 2 and R(0) = (-1) k 2 +1 n where R(X) = Q L(4,k) (X) X 2 . Proof. Since Q L(4,k) (X) = Q C 4 (X)Q P k (X) -P 3 (X)Q P k-1 (X) we have R(X) = (X 2 -4)Q P k (X) -(X 2 -2) Q P k-1 (X)
X and property 4 gives the result.

Unicyclic graphs with exactly three vertices of maximal degree 3 whose only one belongs to the cycle

Let T be a tree with exactly two vertices of maximal degree 3. Let G 1 be the set of the coalescences of T with a pendant vertex as distinguished vertex and a cycle C p , p ≥ 6. In the following we assume that the vertex of degree 3 belonging to the cycle is denoted by u and v, w are the other two vertices of degree 3 such that v is between u and w; x, y, z are the pendant vertices of G such that d(z, v) < d(z, w) and d(x, w) ≤ d(y, w). An example is given in figure 8. The aim of this section is to show the following theorem whose proof is summed up in

0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 u v w z x y Figure 8: A graph G ∈ G 1
As L(4, k) cannot be cospectral with a non-bipartite graph we suppose in the following that a graph G ∈ G 1 is bipartite (the length of the cycle is even).

Proposition 8. Let G ∈ G 1 . If one of the following properties is true: i) d(u, v) > 2 ii) d(u, v) = 2, d(v, w) > 1 and d(y, w) > 2 iii) d(u, v) = 2, d(v, w) ≥ 4, d(y, w) ≥ 2 then G is not cospectral with a lollipop.

Proof.

Let p be the length of the cycle of G. If one of these properties is true then G possesses an induced subgraph with twice the eigenvalue 2. By the interlacing theorem it cannot be cospectral with a lollipop (theorem 11).

This subgraph is

C p ∪ T r (for an r ∈ N) in the case i), C p ∪ S 1,3,3 in ii) and C p ∪ S 1,2,5 in iii). Proposition 9. Let G ∈ G 1 . If one of the following properties is true: i) d(u, v) = 1, d(v, w) = 1, ii) d(u, v) = 1 and d(v, w) > 1 and ( d(v, z) > 1 or d(x, w) > 1 or d(y, w) > 1), iii) d(u, v) > 1 and d(v, w) > 1 and ( (d(v, z) > 1 and d(y, w) > 1) or d(x, w) > 1), iv) d(v, w) = 1 and ( d(v, z) > 1 or d(y, w) > 1 or d(x, w) > 1), v) p = 6. then λ i ∈Sp(G) λ 6 i > 20n + 96
and G cannot be cospectral with L(4, k).

Proof. For the cases from i) to iv) we have

|P 2 (G)| = n, |P 3 (G)| = n+3, |S 1,1,1 (G)| = 3, |P 4 (G)| > n + 4 and apply proposition 1. For the case v) we have |P 2 (G)| = n, |P 3 (G)| = n + 3, |S 1,1,1 (G)| = 3, |P 4 (G)| > n + 2, |C 6 (G)| = 1

and apply proposition 1.

Graph Tool

Prop.

p = 6 λ 6 i 9 v) p ≥ 8 d(u, v) = 1 d(v, w) = 1 λ 6 i 9 i) d(v, w) > 1 d(v, z) > 1 or d(x, w) > 1 or d(y, w) > 1 λ 6 i 9 ii) d(v, z) = 1 and d(x, w) = 1 and d(y, w) = 1 Q G (1) 10
d(u, v) = 2 d(x, w) = 1 d(y, w) = 1 Q G (2) 12 d(y, w) = 2 d(v, z) > 1 d(v, w) = 1 λ 6 i 9 iv) d(v, w) > 1 λ 6 i 9 iii) d(v, z) = 1 d(v, w) = 1 λ 6 i 9 iv) 2 ≤ d(v, w) ≤ 3 λ 8 i 11 d(v, w) ≥ 4 λ 2 ≥ 2 8 iii) d(y, w) > 2 d(v, w) = 1 λ 6 i 9, iv) d(v, w) > 1 λ 2 ≥ 2 8 ii) d(x, w) > 1 d(v, w) = 1 λ 6 i 9 iv) d(v, w) > 1 λ 6 i 9 iii) d(u, v) > 2 λ 2 ≥ 2 8 i)
Table 1: Proof of theorem 21 using a case disjunction over the possibilities for the values of d.

Proposition 10. Let G ∈ G 1 such that d(u, v) = 1 and d(w, x) = d(w, y) = d(v, z) = 1.
Then G cannot be cospectral with L(4, k).

Proof. Let G ∈ G 1 , with n = p + q vertices where p is the length of the cycle. We have:

Q G (X) = Q Cp (X)Q S 1,1,q-3 (X) -XQ P p-1 (X)Q S 1,1,q-5 (X) = XQ Cp (X)(Q P q-1 (X) -Q P q-3 (X)) -X 2 Q P p-1 (X)(Q P q-3 (X) -Q P q-5 (X))
Using property 3 we compute Q G (1), the result depends on p and q which are p and q modulo 6 and are summed up into the following table:

H H H H H H p q 0 1 2 3 4 5 0 0 0 0 0 0 0 2 -1 -5 -4 1 5 4 4 -5 -7 -2 5 7 2
Comparing this results with proposition 5 ( n = p + q) we conclude that G cannot be cospectral with L(4, k).

Proposition 11. Let G ∈ G 1 such that p ≥ 8, d(u, v) = 2, 2 ≤ d(v, w) ≤ 3, d(y, w) = 2, d(v, z) = 1, d(x, w) = 1. Then G cannot be cospectral with L(4, k). Proof. We have |P 2 (G)| = n, |P 3 (G)| = n + 3, |P 4 (G)| = n + 4, |S 1,1,2 (G)| = 7, |P 5 (G)| = n + 6 if d(v, w) = 2 and |P 5 (G)| = n + 5 if d(v,
w) ≥ 3 and by proposition 1:

λ 8 i = 70n + 588 + 16|C 8 (G)| if d(v, w) = 2 70n + 580 + 16|C 8 (G)| if d(v, w) = 3
• If d(v, w) = 2 then, by proposition 4, G cannot be cospectral with L(4, k).

• If d(v, w) = 3 then, by proposition 4, G is cospectral with L(4, k) only if p = 8. We then check that such a graph G (drawn on figure 9) is not cospectral with L(4, 13) by comparing spectral radii (see tables 11 and 12 in appendix).

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 000000000000 111111111111 00 11 0 0 1 1 0 0 1 1 Figure 9: Proposition 12. Let G ∈ G 1 such that d(u, v) = 2, d(x, w) = d(y, w) = 1. Then Q G (2) = -4p and G cannot be cospectral with a lollipop L(4, k)
Proof. Set b = d(v, w) and a = d(z, v), using theorems 4 and 6 we have

Q G (X) = Q Cp (X)Q T (X) -Q P p-1 (X)Q S 1,1,a+b-1 (X)
(where T is a tree) and using property 2 we get Q G (2) = 0p × 4 = -4n + 4(np). As np > 4, proposition 6 implies that G cannot be cospectral with a lollipop L(4, k).

3.3.3

Unicyclic graphs with exactly three vertices of maximum degree 3 whose exactly two belongs to the cycle.

Let T be a tree with exactly one vertex w of maximum degree 3 and L(p, k), p ≥ 6, a lollipop (the vertex of degree 3 is denoted by v and the pendant vertex by z). Let G 2 be the set of coalescences of a lollipop with a vertex u of degree 2 of the cycle as distinguished vertex and T with a pendant vertex as distinguished vertex. The pendant vertices different from z are denoted by x and y such that d(x, w) ≤ d(y, w). Such a graph is drawn in figure 10. The aim of this section is to show the following theorem whose proof is summed up in table 2. Table 2: Proof of theorem 22 using a case disjunction over the possibilities for the values of d. An empty cell in the column tool means that the proof uses more than three tools.

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 v u w x y z Figure 10: A graph G ∈ G 2 Graph Tool Propo- sition p = 6 λ i 13 v) p ≥ 8 d(u, v) = 1 d(v, z) > 1 or d(x, w) > 1 or d(y, w) > 1 λ i 13 ii) d(w, u) = 1 λ i 13 iii) d(v, z) =
Theorem 22. A L(4, k) cannot be cospectral with a graph G ∈ G 2 .

As in the previous section we can assume the length of the cycle of G is even.

Proposition 13. Let G ∈ G 2 . If
Proposition 14. Let G ∈ G 2 such that p ≥ 8, d(u, v) > 1, d(u, w) > 1, d(z, v) = 1, d(w, x) = d(w, y) = 1, then i λ 6 i < 20n + 96 and G cannot be cospectral with a lollipop L(4, k). Proof. The subgraphs M of G with w 6 (G) > 0 are P 2 , P 3 , P 4 , S 1,1,1 and |P 2 (G)| = n, |P 3 (G)| = n + 3, |S 1,1,1 (G)| = 3, |P 4 (G)| = n + 3 and we apply proposition 1. Proposition 15. Let G ∈ G 2 such that d(u, v) = 1, d(z, v) = 1, d(w, y) = 1, d(w, u) > 1, then G is not cospectral with L(4, k).

Proof.

Since d(w, x) ≤ d(w, y) = 1 we have d(w, x) = 1. Let α = d(u, w) (so n = p + α + 3), by theorem 4 we get:

Q G (X) = Q L(p,1) (X)Q S 1,1,α-1 (X) -Q Pp (X)Q S 1,1,α-2 (X) = XQ Cp (X) -Q P p-1 (X) Q S 1,1,α-1 (X) -Q Pp (X)Q S 1,1,α-2 (X)
and (with property 2)

Q G (2) = -8p-4. So Q G (2) = Q L(4,k) (2) if and only if -8p-4 = -4n + 16 that is α = p + 2.
As a consequence

Q G(X) = XQ Cp (X) -Q P p-1 (X) Q S 1,1,p+1 (X) -Q Pp (X)Q S 1,1,p (X) = XQ Cp (X) -Q P p-1 (X) X Q P p+3 (X) -Q P p+1 (X) -Q Pp (X)X Q P p+2 (X) -Q Pp (X)
By property 3 we have (let's note that n = 2p + 5):

• If p = 0 (so n = 5) then Q G (1) = 1. • If p = 2 (so n = 3) then Q G (1) = -4. • If p = 4 (so n = 1) then Q G (1) = 0.
where p and n are p and n modulo 6. And by proposition 5, G is not cospectral with L(4, k).

Proposition 16. Let G ∈ G 2 such that d(u, v) > 1, d(w, x) = d(w, y) = d(v, z) = d(u, w) = 1, then G cannot be cospectral with L(4, k).
Proof. Set a = d(u, v) and b = pa. We have:

Q G (X) = Q L(p,1) (X)Q P 3 (X) -X 2 Q S 1,a-1,b-1 (X) = XQ Cp (X) -Q P p-1 (X) Q P 3 (X) -X 2 Q S 1,a-1,b-1 (X)
and

Q G (2) = -4p -4(2a + 2b -ab). As n = p + 4 we have Q G (2) + 4n -16 = -4(2p -ab) so Q G (2) + 4n -16 = 0 if and only if ab = 2p.
• If a = 2 then 2b = 4 + 2b, impossible.

• If a = 3 then b = 6 and p = 9, p odd is impossible.

• If a = 4 then b = 4 and p = 8 we check that this graph is not cospectral with L(4, 8).

• If a > 4 then as p ≤ 2b we have 2pab < 0.

As a result G is not cospectral with L(4, k).

Proposition 17. Let G ∈ G 2 such that p ≥ 8, d(u, v) > 1, d(w, u) > 1, d(w, y) > 1, d(w, x) = d(v, z) = 1. Then G is not cospectral with a lollipop L(4, k). Proof. Let a = d(u, v), b = p -a, α = d(u, w), β = d(w, y) ≥ 2.
We have a ≤ b and p ≤ 2b and n = p

+ α + β + 2. Q G (X) = Q L(p,1) (X)Q S 1,α-1,β (X) -Q S 1,a-1,b-1 (X)Q S 1,α-2,β (X) = XQ Cp (X) -Q P p-1 (X) Q S 1,α-1,β (X) -Q S 1,a-1,b-1 (X)Q S 1,α-2,β (X)
Using property 2 we obtain

Q G (2) = -p(α + 2β -αβ + 2) -(2a + 2b -ab)(α + 3β -αβ + 1)
The following inequality will be useful:

ab = (a -1)(b -1) + p -1 ≥ b -1 + p -1 ≥ 3 2 p -2.
The main argument of this proof is that Q G (2) = -4n + 16 so G cannot be cospectral with a lollipop L(4, k) (proposition 6).

• Case β = 2. Q G (2) -(-4n + 16) = (3α -16)p + (7 -α)ab + 4α. -If α = 2 then Q G (2) -(-4n + 16) = -10p + 5ab + 8 = 0 (otherwise 5 divides 8) -If α = 3 then Q G (2)-(-4n+16) = -7p+4ab+12. If a ≥ 4 then -7p+4ab+12 > 0 (because p ≤ 2b). If a = 3 then -7p + 4ab + 12 = 5b -9 = 0 (because b ∈ N). If a = 2 then -7p + 4ab + 12 = b -2 = 0 (because a + b = p ≥ 8).
-

If 4 ≤ α ≤ 7 then Q G (2) -(-4n + 16) ≥ (3α -16)p + (7 -α)( 3 2 p -2) + 4α ≥ ( 3 2 α - 11 2
)p -14 + 6α

≥ p 2 + 10 > 0 -If α > 7 then the disjoint union C p ∪ S 1,2,5
is an induced subgraph of G with twice the eigenvalue 2 and by the interlacing theorem and theorem 11, G is not cospectral with a lollipop.

• Case β ≥ 3 :

-α = 2. We have |P 2 (G)| = n, |P 3 (G)| = n + 3, |P 4 (G)| = n + 4, |S 1,1,2 (G)| = 7, |P 5 (G)| = n + 6 if a > 2 and |P 5 (G)| = n + 7 if a = 2. By proposition 1 we have λ 8 i = 70n+588+16c 8 if a > 2 and in that case G in not cospectral with L(4, k) (proposition 4). If a = 2 then Q G (2) = -4p -4(β + 3) = -4n + 4 = -4n + 16. -α = 3. Q G (
* If β = 4 then Q G (2) = ab > 0 and Q L(4,k) (2) < 0 * If β = 3 then Q G (2) = 2(ab -2p), n = p + 9 and Q G (2) -(-4n + 16) = 2ab + 20 > 0 -α > 4.
The disjoint union C p ∪ S 1,3,3 is an induced subgraph of G with twice the eigenvalue 2 and by the interlacing theorem and theorem 11, G is not cospectral with a lollipop.

Property 5. Let r ∈ R, r > 2, we have Q Pn (r) = α 1 β n 1 + α 2 β n 2 with β 1 = r+ √ r 2 -4 2 > 1, β 2 = r- √ r 2 -4 2 < 1, α 1 = r-β 2 β 1 -β 2 > 1, α 2 = 1 -α 1 < 0.
Proof. Let (u n ) n∈N be the sequence u n = Q Pn (r). We have u n = ru n-1u n-2 , so u n = α 1 β n 1 +α 2 β n 2 where β 1 , β 2 are roots of X 2 -rX +1 and we note that 1 = u

0 = α 1 +α 2 , r = u 1 = α 1 β 1 + α 2 β 2 . Lemma 3. Let G ∈ G 2 with d(u, v) = 2, d(w, x) = d(w, y) = 1, d(v, z) > 1, d(u, w) > d(v, z), then G is not cospectral with a L(4, k).
Proof. Let α = d(u, w), l = d(v, z), we have n = p + α + l + 2. Applying theorem 5 to the vertex at distance 1 of u and v, we have:

Q G (X) = XQ S 1,1,n-4 (X) -Q P l (X)Q S 1,1,α+p-3 (X) -Q P l+p-2 (X)Q S 1,1,α-1 (X) -2Q P l Q S 1,1,α-1
and applying theorem 5 to the vertex of degree 2 of the cycle of L(4, k) we have:

Q L(4,k) (X) = XQ S 1,1,n-4 (X) -2Q P n-2 (X) -2Q P n-4 (X) Noting that Q S 1,1,c = X(Q P c+2 (X) -Q Pc (X)) and Q P n-2 (X) + Q P n-4 (X) = XQ P n-3 (X) we have: Q G (X) -Q L(4,k) (X) = -XQ P l (X)Q P α+p-1 (X) + XQ P l (X)Q P α+p-3 (X) -XQ P l+p-2 (X)Q P α+1 (X) + XQ P l+p-2 (X)Q P α-1 (X) -2Q P l (X)Q P α+1 (X) + 2Q P l (X)Q P α-1 (X) + 2XQ P n-3 (X)
According to the previous property, we have for r > 2:

Q G (r) -Q L(4,k) (r) = -rα 2 1 β n-3 1 -rα 2 2 β n-3 2 -rα 1 α 2 β α+p-1-l 1 -rα 1 α 2 β α+p-1-l 2 +rα 2 1 β n-5 1 + rα 2 2 β n-5 2 + rα 1 α 2 β α+p-3-l 1 + rα 1 α 2 β α+p-3-l 2 -rα 2 1 β n-3 1 -rα 2 2 β n-3 2 -rα 1 α 2 β l+p-2 1 β α+1 2 -rα 1 α 2 β l+p-2 2 β α+1 1 +rα 2 1 β n-5 + rα 2 2 β n-5 + rα 1 α 2 β l+p-2 1 β α-1 2 + rα 1 α 2 β l+p-2 2 β α-1 1 +2rα 1 β n-3 1 + 2rα 2 β n-3 2 Let x = α + p -l -1 and y = |l + p -α -1|, we have x > y. Q G (r) -Q L(4,k) (r) = 2r (α 1 -α 2 1 )β 2 1 + α 2 1 β n-5 1 + 2r (α 2 -α 2 2 )β 2 2 + α 2 2 β n-5 2 -rα 1 α 2 (β x 1 -β x-2 1 -β y 1 + β y-2 1 ) -rα 1 α 2 (β x 2 -β x-2 2 -β y 2 + β y-2 2 )
but we have the four following equalities:

α 1 α 2 = α 1 -α 2 1 = -1 r 2 -4 (α 1 -α 2 1 )β 2 1 + α 2 1 = 0 (α 2 -α 2 2 )β 2 2 + α 2 2 = 0 β 2 = β -1 1 22 so Q G (r) -Q L(4,k) (r) = r r 2 -4 β x 1 -β x-2 1 -β y 1 + β y-2 1 + β -x 1 -β -x+2 1 -β -y 1 + β -y+2 1 As lim r→+∞ β x 1 -β x-2 1 -β y 1 +β y-2 1 +β -x 1 -β -x+2 1 -β -y 1 +β -y+2 1 r = +∞ (note that x > 2)
we have lim

r→+∞ Q G (r) -Q L(4,k) (r) = +∞
and G is not cospectral with L(4, k).

Proposition 18. Let G ∈ G 2 with p ≥ 8, d(u, v) > 1, d(w, x) = d(w, y) = 1, d(v, z) > 1, d(u, w) > 1, then G is not cospectral with a L(4, k).
Proof.

We distinguish the following cases :

• case 1 : d(u, v) > 2
G (2). Let a = d(u, v), b = p -a, α = d(u, w), l = d(v, z). Q G (X) = Q L(p,l) (X)Q S 1,1,α-1 (X) -Q S a-1,b-1,l (X)Q S 1,1,α-2 (X) = P Cp (X)Q P l (X) -Q P p-1 (X)Q P l-1 (X) Q S 1,1,α-1 (X) -Q S a-1,b-1,l (X)Q S 1,1,α-2 (X)
Using property 2 we have

Q G (2) + 4n -16 = -8lp + 4abl + 4α + 4l -8 and G is cospectral with L(4, k) only if Q G (2) + 4n -16 = 0 that is α = l(2p -ab -1) + 2.
• For case 3 we have α = 2 so 2pab + 1 = 0 and a is odd. If a = 3 then b = 5 and p = 8. We have

|P 2 (G)| = n, |P 3 (G)| = n + 3, |P 4 (G)| = n + 4, |P 5 (G)| = n + 7, |S 1,1,1 (G)| = 3, |S 1,1,2 (G)| = 7, |C 8 (G)| = 1. So λ 8 i = 70n
+ 612 and in this case G is not cospectral with L(4, k) (proposition 4). If a ≥ 5 then 2pab -1 ≤ 4b -5b -1 < 0 and this finishes the case 3.

• For case 2, |P 2 (G)| = n, |P 3 (G)| = n+3, |P 4 (G)| = n+4, |S 1,1,1 (G)| = 3, |S 1,1,2 (G)| = 7, |P 5 (G)| = n + 5 , |L(4, 1)(G)| = 0, |L(4,
2)(G)| = 0 so (proposition 1) λ 8 i = 70n + 580 + 16c 8 and G is cospectral with L(4, k) only if p = 8. We have l = 2 and α = l(2pab -1) + 2 so the graphs that can be cospectral with L(4, k) are the ones with a = 3, b = 5 so α = 2, impossible, or a = 4, b = 4 so α = 0, impossible.

• For case 5, G is cospectral with L(4, k) only if α = 3l + 2, but this is impossible according to lemma 3.

3.3.4

Unicyclic graphs with exactly three vertices of maximum degree 3, all of them belonging to the cycle.

Let G 3 be the set of the graphs G obtained in the following way:

• Do the coalescence of a lollipop L(p, k), p ≥ 6, k ≥ 1 with a vertex of degree 2 of the cycle as distinguished vertex and a path with a pendant vertex as distinguished vertex.

• Do the coalescence of the previous graph with a vertex of the cycle of degree 2 as distinguished vertex and a path with a pendant vertex as distinguished vertex.

We denote by u 1 , u 2 , u 3 the three vertices of degree 3 and by x 1 , x 2 , x 3 the pendant vertices such that d(x i , u i ) = min j d(x i , u j ). Un example is given in figure 11 The aim of this section is to show the following theorem whose proof is summed up in table 3 :

Theorem 23. A lollipop L(4, k) cannot be cospectral with a graph G ∈ G 3 .
As in the previous sections we assume that the cycle of G is even.

Graph

Tool

Proposition p = 6

λ i 19 iv) ∃i, j, i = j : d(x i , u i ) > 1 and d(x j , u j ) > 1 λ i 19 i) ∃r, s, t, r = s, s = t, r = t, : d(u r , u s ) = 1 and d(u s , u t ) = 1 λ i 19 ii)
p ≥ 8 and ∃i, j, k two by two distinct ∃r, s, t two by two distinct:

d(x i , u i ) = 1 d(x j , u j ) = 1 d(x k , u k ) ≥ 1 d(u r , u s ) > 1 d(u s , u t ) > 1 d(x k , u k ) = 1 d(u r , u t ) > 1 λ i 20 d(u r , u t ) = 1 d(u r , u s ) = 2 or d(u s , u t ) = 2 λ i 21 d(u r , u s ) > 2 and d(u s , u t ) > 2 λ i 21 d(x k , u k ) > 1 d(u r , u t ) = 1 λ i 19 iii) d(u r , u t ) > 1 d(x k , u k ) = 2 λ i 22 d(x k , u k ) > 2 ∀l 1 , l 2 , d(u l 1 , u l 2 ) > 2 λ i 23 iii) ∃r, s, t d(u r , u s ) = 2 and d(u r , u t ) > 2 and d(u s , u t ) > 2 λ i 23 ii) d(u i , u j ) = 2 and d(u j , u k ) = 2 p = 8 λ i 23 i) p ≥ 10 λ 10 i 24 d(u i , u k ) = 2 and d(u j , u k ) = 2 Q G (2) and R(0)
25 Table 3: Proof of theorem 23 using a case disjunction over the possibilities for the values of d. R denotes the polynomial

R(X) = Q G (X)
i) ∃i, j, i = j : d(x i , u i ) > 1, d(x j , u j ) > 1, ii) ∃r, s, t, r = s, r = t, s = t : d(u r , u s ) = d(u s , u t ) = 1, iii) ∃i, r, t : d(x i , u i ) > 1, d(u r , u t ) = 1, iv) p = 6, then i λ 6 i > 20n + 96
and G cannot be cospectral with a lollipop L(4, k).

Proof. and G cannot be cospectral with a lollipop L(4, k).

For cases i) to iii) we have |P 2 (G)| = n, |P 3 (G)| = n + 3, |S 1,1,1 (G)| = 3, |P 4 (G)| > n + 4 and we apply proposition 1. For case iv) we have |P 2 (G)| = n, |P 3 (G)| = n + 3, |S 1,1,1 (G)| = 3, |P 4 (G)| > n + 2, |C 6 (G)| =
Proof. We have

|P 2 (G)| = n, |P 3 (G)| = n + 3, |P 4 (G)| = n + 3, |S 1,1,1 (
G)| = 3 and no p-cycle for p ≤ 6. We conclude with proposition 1.

The following three propositions compute λ 8 i for some G ∈ G 3 , their proofs are based on counting motifs in M 8 (G) which is done in a summary table 4.

Proposition 21. Let G ∈ G 3 such that p ≥ 8, ∀i, d(u i , x i ) = 1, and ∃r, s, t two by two distinct : d(u r , u t ) = 1, d(u r , u s ) > 1, d(u s , u t ) > 1. Then: i λ 8 i = 70n + 588 + 16c 8 if d(u r , u s ) =
Proposition 22. Let G ∈ G 3 such that p ≥ 8, ∃i, j, k : d(u i , x i ) = d(u j , x j ) = 1, d(u k , x k ) = 2.
We distinguish the three following cases

• case 1 : ∃r, s, t, r = s, r = t, s = t: d(u r , u s ) = d(u s , u t ) = 2.
• case 2 : ∃r, s, t, r = s, r = t, s = t: d(u r , u s ) = 2 and d(u r , u t ) > 2 and d(u s , u t ) > 2.

• case 3: ∀s, t, d(u s , u t ) > 2. Proof. Using table 4, we apply proposition 1 to compute i λ 8 i . Under the hypotheses of the proposition, the only cases for which λ 8 i = 70n + 596 is when c 8 = 1 in case 2. These cases are drawn in figure 13 and we check that they are not cospectral with L(4, 8) by comparing spectral radii (see tables 11 and 12 in appendix).

Then:

Proposition 23. Let G ∈ G 3 such that p ≥ 8, ∃i, j, k : d(u i , x i ) = d(u j , x j ) = 1, d(u k , x k ) > 2.
We distinguish the three following cases

• case 1 : ∃r, s, t, r = s, r = t, s = t: d(u r , u s ) = d(u s , u t ) = 2.
• case 2 : ∃r, s, t, r = s, r = t, s = t: d(u r , u s ) = 2 and d(u r , u t ) > 2 and d(u s , u t ) > 2. and G cannot be cospectral with a lollipop in the cases 2 and 3 and in the case 1 if c 8 = 1.

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
The two following propositions solve the case 1 of proposition 23 when c 8 = 0.

Proposition 24. Let G ∈ G 3 such that p ≥ 10, ∃i, j, k :

d(u i , x i ) = d(u j , x j ) = 1, d(u k , x k ) > 2, d(u i , u j ) = d(u j , u k ) = 2. Then: i λ 10 i = 252n + 3340 + 20c 10 if d(u k , x k ) = 3 252n + 3350 + 20c 10 if d(u k , x k ) > 3
where c 10 = |C 10 (G)|. And G cannot be cospectral with L(4, k).

Proof. We have

|P 2 (G)| = n, |P 3 (G)| = n + 3, |P 4 (G)| = n + 4, |P 5 (G)| = n + 7, |P 6 (G)| = n + 6 if d(u k , x k ) = 3, |P 6 (G)| = n + 7 if d(u k , x k ) >3, |S 1,1,1 (G)| = 3, |S 1,1,2 (G)| = 7, |S 1,2,2 (G)| = 5, |S 1,1,3 (G)| = 11
, and no others subgraphs M such that w k (M) > 0. We then apply proposition 1. The only case for which λ 10 i = 252n + 3360 is for the graph of figure 14, and we check that it is not cospectral with L(4, 11) by comparing spectral radii (see tables 11 and 12 in appendix). 4: Count of the motifs of some graphs G ∈ G 3 . We denote by G a (resp. G b , G c ) a graph described in proposition 21 (resp. 22, 23).

0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 Figure 14: M w 8 (M) |M(G a )| |M(G b )| |M(G c )| P 2 2 n
Proposition 25. Let G ∈ G 3 such that p ≥ 10, ∃i, j, k : d(u i , x i ) = d(u j , x j ) = 1, d(u k , x k ) > 2, d(u i , u k ) = d(u j , u k ) = 2. Then G cannot be cospectral with L(4, k).
Proof. Let G be a graph cospectral with L(4, k) and let q = d(u k , x k ) (we have n = p + q + 2). Applying theorem 5 to the vertex u k , we have:

Q G (X) = XQ T p+1 (X)Q Pq (X) -2Q S 1,1,p-3 (X)Q Pq (X) -Q T p+1 (X)Q P q-1 (X) -2X 2 Q Pq (X)
Property 2 gives Q G (2) = -16(q + 1) and according to proposition 6 G is cospectral with a lollipop L(4, k) only if -16(q + 1) = -4n + 16 ie p = 3q + 6 and q is necessarily even.

Using Q S 1,1,c (X) = X(Q P c+2 (X) -Q Pc (X)) we have that if c is odd then 0 is an eigenvalue of S 1,1,c with multiplicity 2 and if R(X) = Q S 1,1,c (X) X then R(0) = (-1) c+1 2 (c+2). The relation Q Tn (X) = XQ S 1,1,n-4 (X) -XQ S 1,1,n-2 (X) implies that 0 is an eigenvalue of T n with multiplicity 2. Let R(X) = Q G (X) X 2 . Property 4 gives R(0) = -2p if q ≡ 0[4] -2p + 4 if q ≡ 0[4]
If q ≡ 0[4] then according to proposition 7, G is cospectral with a lollipop L(4, k) only if -2p = -n ie p = q + 2 which contradicts p = 3q + 6. If q ≡ 2[4] then according to proposition 7, G is cospectral with a lollipop L(4, k) only if -2p + 4 = -n ie p = q + 6 which contradicts p = 3q + 6.

Unicyclic graphs without vertices of degree 3 and only one vertex of maximum degree 4

The graph γ p,k 1 ,k 2 is the coalescence of a lollipop L(p, k 1 ) with the vertex of degree 3 as distinguished vertex and a path P k 2 +1 with a pendant vertex as distinguished vertex (cf figure 15 for an example).

Proposition 26. For a graph γ p,k 1 ,k 2 with p > 4 we have:

i λ 6 i =    20n + 96 + 12c 6 if k 1 = k 2 = 1 20n + 108 + 12c 6 if k 1 > 1, k 2 = 1 20n + 120 + 12c 6 if k 1 > 1, k 2 > 1 where c 6 = |C 6 (G)|. Proof. We have |P 2 (G)| = n, |P 3 (G)| = n + 3, |S 1,1,1 (G)| = 4 and • |P 4 (G)| = n + 2 if k 1 = k 2 = 1 • |P 4 (G)| = n + 4 if k 1 > k 2 = 1 0 0 1
• |P 4 (G)| = n + 6 if k 1 ≥ k 2 > 1
and we apply proposition 1.

Proposition 27. A lollipop L(4, k) cannot be cospectral with a graph γ p,1,1 .

Proof. The graphs L(4, k) and γ p,1,

1 have n = k + 4 = p + 2 vertices. Let us show that Q L(4,k) (2) = P γ p,1,1 (2)
. Using twice the theorem 6:

P γ p,1,1 (X) = XQ L(p,1) (X) -XQ P p-1 (X) = X(XQ Cp (X) -Q P p-1 (X)) -XQ P p-1 (X)
And by proposition 2, P γ p,1,1 (2) = -4p = -4n + 8 which contradicts Q L(4,k) (2) = -4n + 16 (proposition 6).

Theorem 24. A lollipop L(4, k) cannot be cospectral with γ p,k 1 ,k 2 , p > 4.

Proof. It is a straightforward consequence of propositions 26 and 27.

Key theorem

Theorem 25. Let G be a graph cospectral with a lollipop L(4, k) then G possesses a 4-cycle.

Proof.

Let G be a graph cospectral with L(4, k) then G is connected, unicyclic and bipartite (so the length of the cycle is even). Let n j be the number of vertices of degree j, j ∈ {1, 2, 3, 4}, of G (remind by theorem 13 that the maximum degree of G is less than or equal to 4). We have (by proposition 2), We know that n = n 1 + n 2 + n 3 + n 4 and 2m = 2n = n 1 + 2n 2 + 3n 3 + 4n 4 (the sum of the degrees is twice the number of edges) so n = n 2 + 2n 3 + 3n 4 and n 1 = n 3 + 2n 4 . We get:

4n + 12 = 4(n + n 3 + 3n 4 ) + 8c

and then 2c = 3n 3 -3n 4 .

If c = 0 then there are two cases:

• n 4 = 1, n 3 = 0, so n 1 = 2 and G = γ p,k 1 ,k 2 with n = p + k 1 + k 2
By theorem 24, G cannot be cospectral with γ p,k 1 ,k 2 ; this case is impossible.

• n 4 = 0, n 3 = 3, so

n 1 = 3 and G ∈ G 1 ∪ G 2 ∪ G 3 .
But by theorems 21, 22 and 23 this is impossible.

As a result c = 0 and G has a 4-cycle.

Following the proof of theorem 16 for odd lollipop, we can now state:

Theorem 26. The lolipop L(4, k) is determined by its spectrum.

Conclusion

In this paper we give a way to count closed walks, which is relevant to show that two graphs cannot be cospectral. That provides a new approach to show that the odd lollipops are determined by their spectrum and following this same idea we have proved that even lollipops are also determined by their spectrum. However this is far to be as simple as the odd case and we had to develop several tools to show the non-cospectrality of two given graphs. The most difficult case, as it was noted in [START_REF] Haemers | Spectral characterizations of lollipop graphs[END_REF][START_REF] Van Dam | Developments on spectral characterizations of graphs[END_REF], is for the lollipops L(4, k) where connectivity and presence of a 4-cycle are quite long to establish.

A Appendix

A.2 Proof of theorem 18

First, we notice the following relations which will be useful to prove lemmas 5 and 8 and whose proof is straightfoward by induction on p. Proof. On one hand λ 1 (P (0, 1, 1)) > 2 and λ 1 (P (1, 1, 1)) > 2. On the other hand, if there exists p i ≥ 2 (we assume p 3 ≥ 2) then the lollipop L(p 1 + p 2 + 2, 1) is an induced subgraph of P (p 1 , p 2 , p 3 ). Since λ 1 (L(p 1 + p 2 + 2, 1)) > 2 (theorem 11) the interlacing theorem gives the result.

∀p > 0, Q Pp (α) > βQ P p-1 (α) (4)
Applying theorem 5 to a vertex of degree 3 of P (p 1 , p 2 , p 3 ) we can get the following expression of the characteristic polynomial of P (p 1 , p 2 , p 3 ), p i > 0 which will be useful for the next results.

Q P (p 1 ,p 2 ,p 3 ) (X) = XQ Sp 1 ,p 2 ,p 3 (X) -Q S p 1 -1,p 2 ,p 3 (X) -Q S p 1 ,p 2 -1,p 3 (X) -Q S p 1 ,p 2 ,p 3 -1 (X) -2Q Pp 1 (X) -2Q Pp 2 (X) -2Q Pp 3 (X) (5)
where

Q S a,b,c (X) = XQ Pa (X)Q P b (X)Q Pc (X) -Q P a-1 (X)Q P b (X)Q Pc (X) -Q Pa (X)Q P b-1 (X)Q Pc (X) -Q Pa (X)Q P b (X)Q P c-1 (X) (6) Lemma 5. If p 1 ≤ 3, p 2 ≤ 3 then ∀p ∈ N : λ 1 (P (p 1 , p 2 , p)) > 2 + 2 √ 2.
Proof. According to theorem 7 it is sufficient to prove the result for p 1 = 3, p 2 = 3. Let α = 2 + 2 √ 2. We shall show that Q P (3,3,p) (α) < 0. Using equations ( 5) and ( 6) and

Q P p-2 (X) = XQ P p-1 (X) -Q Pp (X), Q P 2 (X) = X 2 -1, Q P 3 (X) = X 3 -2X and Q P 4 (X) = X 4 -3X 2 + 1, we get: Q P (3,3,p) (X) = Q Pp (X) X 8 -9X 6 + 24X 4 -20X 2 +Q P p-1 (X) -X 7 + 8X 5 -16X 3 + 8X -4(X 3 -2X) so Q P (3,3,p) (α) = (16 -16 √ 2)Q Pp (α) + α(16 -8 √ 2)Q P p-1 (α) -8 √ 2α = -16 + 16 √ 2 -Q Pp (α) + α √ 2 Q P p-1 (α) -8 √
2α < 0 (by eq.( 4) )

As a result λ 1 (P (3, 3, p)) > α.

Lemma 6. If p 1 ≤ 2, p 2 ≤ 4 then ∀p ∈ N : λ 1 (P (p 1 , p 2 , p)) > 2.2 > 2 + 2 √ 2
Proof. Mutatis mutandis the proof is the same as the one of lemma 5.

Lemma 7. For p 2 , p 3 > 0, p 1 ∈ {0, 1} we have λ 1 (P (p 1 , p 2 , p 3 )) > 2 + 2 √ 2.

Proof. Let α = 2 + 2 √ 2. According to theorem 7 it is sufficient to prove the result for P (1, p, p) where p = max(p 2 , p 3 ). Applying theorem 5 to a vertex at distance one of the two vertices of degree 3 we have:

Q P (1,p,p) (X) = XQ C 2p+2 (X) -2Q P 2p+1 (X) -4Q Pp (X) = X XQ P 2p+1 (X) -2Q P 2p (X) -2 -2Q P 2p+1 (X) -4Q Pp (X) = (X 2 -2)Q P 2p+1 (X) -2XQ P 2p (X) -4Q Pp (X) -2X
But (theorem 5 applied to a vertex at distance p of a pendant vertex in the graphs P 2p+1 and P 2p ):

Q P 2p+1 (X) = X Q 2 Pp (X) -2Q Pp (X)Q P p-1 (X) and Q P 2p (X) = XQ Pp (X)Q P p-1 (X) -Q 2 P p-1 (X) -Q Pp (X)Q P p-2 (X) So Q P (1,p,p) (X) = X 2 -2 XQ 2 Pp (X) -2XQ Pp (X)Q P p-1 (X) -2X XQ Pp (X)Q P p-1 (X) -Q 2 P p-1 (X) -Q Pp (X)Q P p-2 (X) -4Q Pp (X) -2X = Q Pp (X) (X 3 -4X)Q Pp (X) + (4 -2X 2 )Q P p-1 (X) -4 +2XQ 2 P p-1 (X) -2X
Using Q Pp (α) > βQ P p-1 (α) (equation ( 4)), we get

Q P (1,p,p) (α) < Q Pp (α) (α 3 -4α)Q Pp (α) + (4 -2α 2 + 2α β )Q P p-1 (α) -4 -2α
we then notice that 4-2α 2 + 2α β -α 3 +4α = β and by equation ( 4) we have Q P (1,p,p) (α) < 0.

Lemma 8. Given P (2, p 2 , p 3 ) with p 3 ≥ 3, denote by u and v the two vertices of degree 3. Let y be a vertex at distance 2 from u and at distance greater than or equal to 2 from v, we define P (2, p 2 , p 3 ) as the graph obtained by adding to P (2, p 2 , p 3 ) a pendant vertex x to y. We have λ

1 ( P (2, p 2 , p 3 )) > 2 + 2 √ 2.
Proof. Let α = 2 + 2 √ 2. By theorem 7 it is sufficient to prove the result for p 2 = p 3 = p = max{p 2 , p 3 }. The aim of the proof is to show that Q P (2,p,p) (α) < 0. The following equations will be useful:

Q S 2,a,b (α) = (α 2 -1)Q P a+b+1 (α) -αQ Pa (α)Q P b (α) Q P 2p+1 (α) = αQ 2 Pp (α) -2Q Pp (α)Q P p-1 (α) Q P 2p (α) = Q 2 Pp (α) -Q 2 P p-1 (α) Q P 2p-1 (α) = αQ P 2p (α) -Q P 2p+1 (α) = -αQ 2 P p-1 (α) + 2Q Pp (α)Q P p-1 (α) and we deduce Q S 2,p,p (α) = (α 3 -2α)Q 2 Pp (α) -2(α 2 -1)Q Pp (α)Q P p-1 (α) Q S 2,p,p-1 (α) = (α 2 -1)Q 2 Pp (α) -(α 2 -1)Q 2 P p-1 (α) -αQ Pp (α)Q P p-1 (α) Q S 2,p+1,p-1 (α) = (α 3 -α)Q 2 Pp (α) + (-3α 2 + 2)Q Pp (α)Q P p-1 (α) + αQ 2 P p-1 (α) Theorem 5 gives Q P (2,p,p) (α) = αQ P (2,p,p) (α) -Q H (α)
where H = P (2, p, p)\{x, y} Equation 5 gives

Q P (2,p,p) (α) = αQ S 2,p,p (α) -Q S 1,p,p (α) -2Q S 2,p,p-1 (α) -4Q Pp (α) -2Q P 2 (α) but Q S 1,p,p (α) = 1 α (Q S 2,p,p (α) + Q S 0,p,p (α)) so αQ P (2,p,p) (α) = (α 2 -1)Q S 2,p,p (α) -2αQ S 2,p,p-1 (α) -Q P 2p+1 (α) -4αQ Pp (α) -2αQ P 2 (α) = (α 5 -5α 3 + 3α)Q 2 Pp (α) + (2α 3 -2α)Q 2 P p-1 (α) +(-2α 4 + 6α 2 )Q Pp (α)Q P p-1 (α) -4αQ Pp (α) -2αQ P 2 (α) Theorem 5 gives Q H (α) = α 2 Q S 2,p,p-2 (α) -αQ S 1,p,p-2 (α) -αQ S 2,p-1,p-2 (α) -Q S 2,p,p-2 (α) -2αQ P p-2 (α) but Q S 2,p,p-2 (α) = αQ S 2,p,p-1 (α) -Q S 2,p,p (α), αQ S 1,p,p-2 (α) = Q S 2,p,p-2 (α) + Q S 0,p,p-2 (α) and Q S 2,p-1,p-2 (α) = (α 2 -1)Q S 2,p,p-1 (α) -αQ S 2,p-1,p+1 (α) so Q H (α) = -αQ S 2,p,p-1 (α) -(α 2 -2)Q S 2,p,p (α) + α 2 Q S 2,p-1,p+1 (α) -Q P 2p-1 (α) -2αQ P p-2 (α) = (2α 3 -3α)Q 2 Pp (α) + (2α 3 )Q 2 P p-1 (α) +(-α 4 -3α 2 + 2)Q Pp (α)Q P p-1 (α) -2αQ P p-2 (α)
So we have:

Q P (2,p,p) (α) = (α 5 -7α 3 + 6α)Q 2 Pp (α) -2αQ 2 P p-1 (α) +(-α 4 + 9α 2 -2)Q Pp (α)Q P p-1 (α) +2αQ P p-2 (α) -4αQ Pp (α) -2αQ P 2 (α)
Equation ( 4) gives 2αQ P p-2 (α) -4αQ Pp (α) < 0. Lets us show that xQ 2 Pp (α) + yQ 2 P p-1 (α) + zQ Pp (α)Q P p-1 (α) < 0 with x = α 5 -7α 3 + 6α, y = -2α, z = -α 4 + 9α 2 -2. Note that y z+βx = -β, where β is defined in equation ( 4).

xQ 2 Pp (α) + yQ 2 P p-1 (α) + zQ Pp (α)Q Pp (α) = Q Pp (α) xQ Pp (α) -βxQ P p-1 (α) + Q P p-1 (α) (z + βx)Q Pp (α) + yQ P p-1 (α) = Q Pp (α)x Q Pp (α) -βQ P p-1 (α) + Q P p-1 (α)(z + βx) Q Pp (α) -βQ P p-1 (α) < 0 because (z+βx)(Q Pp (α)-βQ P p-1 (α)) -x(Q Pp (α)-βQ P p-1 (α))
= z+βx -x < β and we use equation ( 4).

Lemma 9. Given P (2, p 2 , p 3 ) with p 3 ≥ 3, denote by u and v the two vertices of degree 3. Let y be a vertex at distance 1 from u and at distance greater than or equal to 1 from v, we denote by P (2, p 2 , p 3 ) the graph obtained by adding to P (2, p 2 , p 3 ) a pendant vertex x to y. We have λ 1 ( P (2, p 2 , p 3 )) > 2 + 2 √ 2.

Proof. A direct consequence of theorem 7 and lemma 8.

Theorem 18. For p 1 , p 2 , p 3 > 0, P (p 1 , p 2 , p 3 ) cannot be an induced subgraph of a graph cospectral with an even lollipop.

Proof. Without loss of generality we assume p 1 ≤ p 2 ≤ p 3 . In order to lead a proof by contradiction, let P (p 1 , p 2 , p 3 ) be an induced subgraph of G cospectral with an even lollipop. As G is bipartite, P (p 1 , p 2 , p 3 ) doesn't have odd cycles and the p i 's are all odd or all even. Using equations ( 5) and property 2 we obtain:

Q P (p 1 ,p 2 ,p 3 ) (2) = p 1 p 2 p 3 -p 1 p 2 -p 1 p 3 -p 2 p 3 -3p 1 -3p 2 -3p 3 -5 i) First assume that p 1 , p 2 , p 2 are odd.
By lemma 7 we have p 1 ≥ 3 and by lemma 5 we have p 2 ≥ 5.

• If p 1 = 3 and p 2 = 5 then Q P (p 1 ,p 2 ,p 3 ) (2) = 4p 3 -44 ≥ 0 if p 3 ≥ 11 • If p 1 = 3 and p 2 ≥ 7 then Q P (p 1 ,p 2 ,p 3 ) (2) ≥ 2p 3 -14 ≥ 0 (because p 3 ≥ p 2 ≥ 7) • If 5 ≤ p 1 ≤ p 2 ≤ p 3 then Q P (p 1 ,p 2 ,p 3 ) (2) ≥ p 3 -5 ≥ 0. Q P (p 1 ,p 2 ,p 3 ) (2
) ≥ 0 implies that P (p 1 , p 2 , p 3 ) has two eigenvalues greater than or equal to 2 (we already know by lemma 4 that P (p 1 , p 2 , p 3 ) has at least one eigenvalue strictly greater than 2) and since a lollipop has only one eigenvalue greater than 2 (theorem 11), the interlacing theorem provides a contradiction except when p 1 = 3, p 2 = 5 and p 3 ∈ {5, 7, 9}.

Assume now that p 1 = 3, p 2 = 5 and p 3 ∈ {5, 7, 9}. According to table 7, λ 1 (P (3, 5, p 3 )) > 2.17 and so P (3, 5, p 3 ) cannot be an induced subgraph of a graph cospectral with L(p, k) for p ≥ 6 (theorem 17). Moreover P (3, 5, p 3 ) cannot be a connected component of a graph cospectral with L(4, k) because λ 1 (P (3, 5, p 3 )) < 2.195 while λ 1 (L(4, k)) ≥ λ 1 (L(4, 5)) > 2.195 when k ≥ 5. So there is a new vertex x adjacent to one vertex y of P (3, 5, p 3 ) (and only one because otherwise there exists r, s ∈ N such that P (1, r, s) is an induced subgraph of G which is impossible by lemma 7). Let H be the subgraph induced by P (3, 5, p 3 ) and x, denote by u and v the two vertices of degree 3 in P (3, 5, p 3 ).

1. If y = u or y = v then the graph T drawn on figure 16 is an induced subgraph of H and λ

1 (T ) ≥ 2.20 > 2 + 2 √ 2 > λ 1 (L(p, k)
) and H cannot be an induced subgraph of G. As a result P (p 1 , p 2 , p 3 ) with p i 's odd cannot be an induced subgraph of G.

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Figure
ii) We now assume that p 1 , p 2 , p 3 are even.

By lemma 7 we have p 1 ≥ 2.

• If p 1 = 2 and p 2 ≤ 4 then by lemma 6 P (p 1 , p 2 , p 3 ) cannot be an induced subgraph of G.

• If p 1 = 2 and p 2 = 6 then Q

P (p 1 ,p 2 ,p 3 ) (2) = p 3 -41 ≥ 0 if p 3 ≥ 42 • If p 1 = 2 and p 2 = 8 then Q P (p 1 ,p 2 ,p 3 ) (2) = 3p 3 -51 ≥ 0 if p 3 ≥ 18 • If p 1 = 2 and p 2 = 10 then Q P (p 1 ,p 2 ,p 3 ) (2) = 5p 3 -61 ≥ 0 if p 3 ≥ 14 • If p 1 = 2 and p 2 ≥ 12 then Q P (p 1 ,p 2 ,p 3 ) (2) ≥ 2p 3 -11 ≥ 0 (because p 3 ≥ 12) • If p 1 = 4 and p 2 = 4 then Q P (p 1 ,p 2 ,p 3 ) (2) = 5p 3 -45 ≥ 0 if p 3 ≥ 10 • If p 1 = 4 and p 2 ≥ 6 then Q P (p 1 ,p 2 ,p 3 ) (2) ≥ 4p 3 -17 ≥ 0 (because p 3 ≥ 6) • If 6 ≤ p 1 ≤ p 2 ≤ p 3 then Q P (p 1 ,p 2 ,p 3 ) (2) ≥ 9p 3 -5 ≥ 0.
As in the proof of the odd case, if Q P (p 1 ,p 2 ,p 3 ) (2) ≥ 0 then P (p 1 , p 2 , p 3 ) has two eigenvalues greater than or equal to 2 and cannot be an induced subgraph of G. We are now going to study the remaining cases for p 1 = 2 and p 1 = 4. First case p 1 = 2 :

The only unsolved cases we are going to consider here are for p 2 ∈ {6, 8, 10} with the corresponding constraints on p 3 . According to table 6, the spectral radius of these remaining cases is greater than 2.17 and so the corresponding graphs cannot be an induced subgraph of a graph cospectral with L(p, k), p ≥ 6. As it was detailed in the proof of the odd case, none of these graphs is a connected component of a graph cospectral with L(4, k) and so there is a new vertex x adjacent to one and only one vertex y of P (2, p 2 , p 3 ). Let H be the subgraph induced by P (2, p 2 , p 3 ) and x. With the same notations and arguments as for the odd case, H cannot be an induced subgraph of G when min{d(y, u), d(y, v)} ≥ 5 or y = u or y = v. Moreover if min{d(y, u), d(y, v)} ≤ 2 then by lemmas 9 and 8, λ 1 (H) > 2 + 2 √ 2 so H cannot be an induced subgraph of a lollipop. We are now going to examine the two last tricky cases: min{d(y, u), d(y, v)} = 3 and min{d(y, u), d(y, v)} = 4.

• If min{d(y, u), d(y, v)} = 3, we can assume that d(y, v) = 3. Let {b, c} = {p 2 , p 3 } such that y is a vertex belonging to a path of length c + 1 of P (2, b, c) between u and v. Then applying theorem 6 to x we get Q H (X) = XQ P (2,b,c) (X) -Q P (2,b,c)\{y} (X) and applying theorem 5 to v we have: • If y ′ = y then x ′ is not adjacent to another vertex of P (2, a, b) otherwise there exists r, s ∈ N such that P (1, r, s) is an induced subgraph of G which is impossible by lemma 7 and x ′ is not adjacent to x otherwise G contains a triangle (impossible because G is bipartite). Hence x ′ is a pendant in H ′ . The graph H ′ then contains C q ∪ S 4 (for q ≥ 3) as an induced subgraph and so has two eigenvalues greater than 2 which is impossible. • Assume that y ′ = x. If x ′ is adjacent to another vertex z of H distinct from y ′ and y, then by the previous cases we necessarily have min{d(z, u), d(z, v)} = 4. Either the graph S 1,3,3 ∪ S 2,2,2 or C 4 ∪ C q is an induced subgraph of H ′ and has two eigenvalues greater than 2 and cannot be an induced subgraph of G.

Q P (2,b,c)\{y} (X) = XQ P 2 (X)Q S 2,b,c-3 (X) -Q P 2 (X)Q S 1,b,c-3 (X) -Q P 2 (X)Q S 2,b-1,c-3 (X) -Q P 1 (X)Q S 2
• If y ′ = y and y ′ = x then by the previous cases we necessarily have min{d(y ′ , u), d(y ′ , v)} = 4. If x ′ is adjacent to another vertex z in H distinct from y ′ and y then by the previous cases we necessarily have min{d(z, u), d(z, v)} = 4 and either S 2,2,2 ∪ S 1,2,5 or C r ∪ C s is an an induced subgraph of H ′ and has two eigenvalues greater than 2 and cannot be an induced subgraph of G. If x ′ is not adjacent to another vertex of H then the graph T n ∪ C q or the graph S 1,3,3 ∪ S 1,3,3 is an induced subgraph of H ′ and has two eigenvalues greater than 2 and cannot be an induced subgraph of G. * If 10 ≤ b ≤ c then Q H (2) > 0 and H has two eigenvalues greater than 2 and cannot be an induced subgraph of G.

Second case: p 1 = 4. We have p 2 = 4 and p 3 ∈ {4, 6, 8}.

According to table 8, λ 1 (P (4, 4, p 3 )) > 2.17 and so P (4, 4, p 3 ) cannot be an induced subgraph of a graph cospectral with L(p, k) for p ≥ 6 (theorem 17). Moreover λ 1 (P (4, 4, 4)) > 2 + 2 √ 2 and P (4, 4, 4) cannot be an induced subgraph of a graph cospectral with L(4, k). When p 3 ∈ {6, 8}, P (4, 4, p 3 ) cannot be a connected component of a graph cospectral with L(4, k) because λ 1 (P (4, 4, p 3 )) < 2.1854 while λ 1 (L(4, k)) ≥ λ 1 (L(4, 3)) > 2.1888 when k ≥ 3. So there is a new vertex x adjacent to one vertex y of P (4, 4, p 3 ) (and only one because otherwise there exists r, s ∈ N such that P (1, r, s) is an induced subgraph of G which is impossible by lemma 7). Let H be the subgraph induced by P (4, 4, p 3 ) and x, these graphs H are summed up in table 10 which shows that that H cannot be an induced subgraph of G because either H has two eigenvalues greater than 2 or H has a spectral radius greater than 2 + 2 √ 2.

A.

Figure 3 :

 3 Figure 3: T n

i λ 6 i 10 i=

 610 = 12|C 6 (G)| + 2|P 2 (G)| + 12|P 3 (G)| + 6|P 4 (G)| + 12|S 1,1,1 (G)| +48|C 4 (G)| + 12|L(4, 1)(G)|ii) If G is a graph without C p , p ∈ {3, 5, 6, 7} and of maximal degree 3 then:i λ 8 i = 2|P 2 (G)| + 28|P 3 (G)| + 32|P 4 (G)| + 8|P 5 (G)| + 72|S 1,1,1 (G)| + 16|S 1,1,2 (G)| +264|C 4 (G)| + 112|L(4, 1)(G)| + 16|L(4, 2)(G)| + 16|C 8 (G)|iii) If G is a graph without C p , p ∈ {3, 5, 6, 7, 8, 9}, of maximal degree 3 and such thatδ(u) = δ(v) = 3, u = v ⇒ d(u, v) > 1, then: i λ 2|P 2 (G)| + 60|P 3 (G)| + 120|P 4 (G)| + 60|P 5 (G)| + 10|P 6 (G)| + 300|S 1,1,1 (G)| +140|S 1,1,2 (G)| + 20|S 1,2,2 (G)| + 20|S 1,1,3 (G)| + 1320|C 4 (G)| +840|L(4, 1)(G)| + 180|L(4, 2)(G)| + 20|L(4, 3)(G)| + 20|C 10 (G)|

  ,b,c 's with a + b + c ≤ p 2 and we have |S e ′ a,b,c (L(p ′ , k ′ ))| ≤ |S e a,b,c (L(p, k))|. • the C p 's and 0 = |C e ′ p (L(p ′ , k ′ ))| < |C e p (L(p, k))| = 1. So, | W| < | W′ | and |W| < |W ′ | which concludes the proof.

Figure 6 :

 6 Figure 6: P(4,7,6)

Figure 7 :

 7 Figure 7: Unicyclic graphs with six vertices and having a 4-cycle

1 Q 1 d

 11 1 and d(x, w) = 1 and d(y, w) = 1 and d(w, u) > (x, w) > 1 or (d(y, w) > 1 and d(z, v) > 1) , z) = 1 and d(y, w) = 1 Q G (2) 16 d(u,w)¿1 d(v, z) = 1 and d(y, w) = 1 λ i 14 d(v, z) = 1 and d(y, w) > 1 17 d(v, z) > 1 and d(y, w) = 1 18

  one of the following properties is true i) d(x, w) > 1 or (d(y, w) > 1 and d(z, v) > 1), ii) d(u, v) = 1 and (d(z, v) > 1 or d(y, w) > 1), iii) d(u, v) = 1 and d(u, w) = 1, iv) d(u, w) = 1 and (d(z, v) > 1 or d(y, w) > 1), v)p=6, then i λ 6 i > 20n + 96and G cannot be cospectral with a lollipop L(4, k).Proof. For all cases we have|P 2 (G)| = n, |P 3 (G)| = n + 3, |S 1,1,1 (G)| = 3.Moreover, for the cases i) to iv) |P 4 (G)| > n + 4 and for the case v) |P 4 (G)| > n + 2 and |C 6 (G)| = 1 and we apply proposition 1.

  2) + 4n-16 = -p(-β + 5)-(2p -ab) ×4 + 4(p + β + 5)-16 = p(β -9) + 4ab + 4β + 4. But β ≥ 3 and ab ≥ 3 2 p -2, so Q G (2) + 4n -16 ≥ 4β -4 > 0. α = 4. * If β ≥ 5 the disjoint union C p ∪ S 1,2,5 is an induced subgraph of G with twice the eigenvalue 2 and by the interlacing theorem and theorem 11, G is not cospectral with a lollipop.

2 • 2 • 2 • 2 • 2 •

 22222 and d(u, w) > 2 and d(z, v) > case 2 : d(u, v) > 2 and d(u, w) > 2 and d(z, v) = case 3 : d(u, v) > 2 and d(u, w) = 2 and d(z, v) > case 4 : d(u, v) > 2 and d(u, w) = 2 and d(z, v) = case 5 : d(u, v) = For cases 1 and 4 we have |P 2 (G)| = n, |P 3 (G)| = n + 3, |P 4 (G)| = n + 4, |S 1,1,1 (G)| = 3, |S 1,1,2 (G)| = 7, |P 5 (G)| = n + 6 , |L(4, 1)(G)| = 0, |L(4, 2)(G)| = 0 so (proposition 1) λ 8 i = 70n + 588 + 16c 8 and G is not cospectral with L(4, k) (proposition 4). • For cases 2, 3 and 5, let us compute Q

Figure 11 :

 11 Figure 11: A graph G ∈ G 3

1 and we apply proposition 1 .

 1 Proposition 20. Let G ∈ G 3 such that p > 6, ∀i, r, s, d(u i , x i ) = 1, d(u r , u s ) > 1. Then i λ 6 i = 20n + 90

Figure 12 :

 12 Figure 12:

  + 16c 8 for the case 1 70n + 580 + 16c 8 for the case 2 70n + 572 for the case 3 and G cannot be cospectral with a lollipop L(4, k).

i λ 4 i

 4 = 8c + 2n + 4(n 2 + 3n 3 + 6n 4 ) were c = 1 if G has a 4-cycle and c = 0 otherwise. Moreover for L(4, k) we have i λ 4 i = 8 + 2n + 4(n + 1) so 4n + 12 = 4(n 2 + 3n 3 + 6n 4 ) + 8c

where α = 2 + 2 √ 2 and β = √ 2 2

 22 α. Obviously equation 4 is true if we replace β by β ′ ≤ β. Lemma 4. λ 1 (P (p 1 , p 2 , p 3 )) > 2.

-•--

  ,b,c-3 (X) -2Q P 2 (X)Q P c-3 (X) Using equation[START_REF] Doob | The complement of the path is determined by its spectrum[END_REF] and property 2 which gives the value in 2 of the characteristic polynomials of paths and T -shape trees we obtain:Q H (2) = bc -5b + 4c -56 If b ≤ c * If b = 6 (so c ≥ 6) then Q H (2) = 10c -86 so if c ≥ 10,H has two eigenvalues greater than 2 and cannot be and induced subgraph of G. Otherwise for c = 8 we check that λ 1 (H) ∼ 2.2050 > 2 + 2 √ 2 and so H cannot be an induced subgraph of G for c ≤ 8. * If c ≥ b ≥ 8 then Q H (2) ≥ 7c -56 ≥ 0 and H has two eigenvalues greater than 2 and cannot be an induced subgraph of G. -If b ≥ c * If c = 6 then Q H (2) = b -32 so if b ≥ 32 then H has two eigenvalues greater than 2 and cannot be an induced subgraph of G. Otherwise we check that for b = 30 we have λ 1 (H) ∼ 2.2071 > 2 + 2 √ 2 and so H cannot be an induced subgraph of G for b ≤ 30. * If 8 ≤ c ≤ b then Q H (2) ≥ 4c -32 ≥ 0 and H has two eigenvalues greater than 2 and cannot be an induced subgraph of G. If min{d(y, u), d(y, v)} = 4, note that c ≥ 8 (otherwise y is at distance less than 4 from u or v). In the same way as previously we compute Q H (2): Q H (2) = b+9c-86. If b ≤ c * If b = 6 then Q H (2) = 9c -80. So if c ≥ 10 then H has two eigenvalues greater than 2 and cannot be an induced subgraph of G. Otherwise we check that for c = 8 we have λ 1 (H) ∼ 2.2014 > 2 + 2 √ 2. * If b = 8 then Q H (2) = 9c -78. So if c ≥ 10 then H has two eigenvalues greater than 2 and cannot be an induced subgraph of G. The case c = b = 8 is considered further in the proof. * If 10 ≤ b ≤ c then Q H (2) > 0 and H has two eigenvalues greater than 2 and cannot be an induced subgraph of G. If b ≥ c * If c = 8 then Q H (2) = b -14. So if b ≥ 14 then H has two eigenvalues greater than 2 and cannot be an induced subgraph of G. Otherwise we check for c = 8 and 8 ≤ b ≤ 12 that λ 1 (H) < 2.196 so H cannot be a connected component of G because for k ≥ 6 λ 1 (L(4, k)) ≥ λ 1 (L(4, 6)) > 2.196. And so there is a new vertex x ′ adjacent to a vertex y ′ of H. Let H ′ be the graph induced by H and x ′ .

  Let n i be the number of vertices of degree i for i ∈ {1, 2, 3, 4}. We have n = n 1 + n 2 + n 3 + n 4 and 2n = n 1 + 2n 2 + 3n 3 + 4n 4 (the sum of the degrees is twice the number of edges), so n 1 = n 3 + 2n 4 .

	Now, we can prove the main theorem of this section:
	Theorem 16. Let G be a graph cospectral with L(p, k), p odd. Then G is isomorphic to
	L(p, k).
	i = 8|C 4 (G)| + 2m + 4(n 2 + 3n 3 + 6n 4 ) and by Proof. Moreover by proposition 2, λ i ∈Sp(G) λ 4 theorem 2, |C 4 (G)| = 0. As λ i ∈Sp(G) λ 4 i we get n 2 + 3n 3 + 6n 4 = n + 1 i = λ i ∈ ( L(p,k)) λ 4 and then 1 = -n 1 + 2n 3 + 5n 4 . So we have 1 = n 3 + 3n 4 and then n 4
	If |L(p, 1)(G)| = 0 then C p or C p with (at least) a chord is a connected component of G. But the first case is impossible because 2 is not an eigenvalue of G and the second case
	is impossible because there are no odd cycles of length less than p in G. So the equality
	of (2) and (3) implies that |L(p, 1)(G)| = 1 and |C p+2 (G)| = 0. If we suppose that there is a 4-cycle in G, since |L(p, 1)(G)| = 1 the subgraph induced by C p and C 4 is C p ∪ C 4 or H(p, 4) but this is impossible by theorem 14.

table 1 :

 1 Theorem 21. The lollipop L(4, k) cannot be cospectral with a graph G ∈ G 1 .

	00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 0 0 0

  Proof. Using table 4, we apply proposition 1 to compute i λ 8i . The only case for which λ 8 i = 70n+ 596 is when ∀i, d(u i , x i ) = 1, ∃r, s, t two by two distinct : d(u r , u t ) = 1, d(u r , u s ) > 2, d(u s , u t ) > 2 and c 8 = 1. This case is drawn in figure12and we check that it is not cospectral with L(4, 7) by comparing spectral radii (see tables 11 and 12 in appendix).

		00 00 00 11 11 11 00 00 00 00 00 00 11 11 11 11 11 11	00 00 00 11 11 11	00 00 00 11 11 11
	00 00 00 11 11 11		00 00 00 11 11 11
	00 00 00 11 11 11	00 00 00 11 11 11	00 00 00 11 11 11	00 00 00 11 11 11
					2 or d(u s , u t ) = 2
	70n + 580 + 16c 8 otherwise
	and G cannot be cospectral with a L(4, k).

Table

				n	n
	P 3	28	n + 3	n + 3	n + 3
	P 4	32	n + 4	n + 4	n + 4
	P 5	8	n + 4 case 1 n + 3 case 2	n + 6 case 1 n + 5 case 2 n + 4 case 3	n + 7 case 1 n + 6 case 2 n + 5 case 3
	S 1,1,1	72	3	3	3
	S 1,1,2	16	8	7	7
	C 4	264	0	0	0
	L(4, 1)	112	0	0	0
	L(4, 2)	16	0	0	0
				c 8 case 1	c 8 case 1
	C 8	16	c 8	c 8 case 2	c 8 case 2
				0 case 3	0 case 3
				70n + 588 + 16c 8	70n + 596 + 16c 8
			70n + 588 + 16c 8	for the case 1	for the case 1
	i λ 8 i =	for the case 1 70n + 580 + 16c 8	70n + 580 + 16c 8 for the case 2	70n + 588 + 16c 8 for the case 2
			for the case 2	70n + 572	70n + 580
				for the case 3	for the case 3

Table 5 :

 5 Number of covering closed walks on a given graph.

	A.1 Counting covering closed walks
	M	w 6 (M) w 8 (M) w 10 (M)
	P 2	2	2	2
	P 3	12	28	60
	P 4	6	32	120
	P 5	0	8	60
	P 6	0	0	10
	C 4	48	264	1320
	C 6	12
	C 8	0	16
	C 10	0	0	20
	S 1,1,1	12	72	300
	S 1,1,2	0	16	140
	S 1,1,3	0	0	20
	S 1,2,2	0	0	20
	L(4, 1)	12	112	840
	L(4, 2)	0	16	180
	L(4, 3)	0	0	20

Table 6 :

 6 [START_REF] Van Dam | Developments on spectral characterizations of graphs[END_REF] Tables of some graphs eigenvalues The two largest eigenvalues of P (2, p 2 , p 3 ) with a 4 decimal place accuracy.

			00 00 11 11	2 vertices	00 00 11 11			H H H H H H p 2 p 3 6	6 2.1987 1.9122	8 2.1921 1.9426	10 2.1891 1.19604
	00 00 11 11	00 00 11 11	00 00 11 11 00 00 11 11 00 00 11 11 00 00 11 11 p 2 vertices	00 00 11 11	00 00 11 11	8	2.1921 1.9426	2.1853 1.9666	2.1822 1.19805
		00 00 11 11 00 00 11 11 00 00 11 11 00 00 00 00 11 11 00 00 00 11 11 00 11 11 00 11 11 00 11 11 p vertices		10	2.1891 1.9604	2.1822 1.9805	2.1790 1.9922
								12	2.1878 1.9716	2.1808 1.9891	2.1776 1.9994
								14	2.1872 1.9790	2.1802 1.9947	2.1770 2.0041
								16	2.1870 1.9842	2.1800 1.9986	2.1767 2.0072
								40	2.1868 1.9999
	00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 p 2 11 p	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 3 vertices 11 11 00 00 00 11 11 11 00 00 00 11 11 11 vertices vertices	00 00 00 11 11 11	H H H H H H p 3 p 2 5 7	5 2.1940 1.9319 2.1847 1.9696	7 2.1847 1.9696 2.1753 2.0000
								9	2.1804 1.9890	2.1709 2.0153
								11	2.1785 2.0000	2.1689 2.0237

Table 7 :

 7 The two largest eigenvalues of P (3, p 2 , p 3 ) with a 4 decimal place accuracy.

Graph Eigenvalues 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

2.2346 2.0117

Table 9: The two largest eigenvalues of some graphs H with a 4 decimal place accuracy. Note that the spectral radius increases when the number of vertices between two vertices of degree 3 decreases (theorem 7).

Graph

Eigenvalues

2.2037 1.9737

2.1925 2.0191

2.1889 2.0000

2.2025

Graph Spectral radius


Marie Guionie

Aurélien Thorette

Marco Romanelli

Anthony Carré

Hen Goulc'

Emmanuel Loas

Laurent Pinsard

Benoît Lablonde

Mehdi Cadier

Marc Alouini

Vallet

Phase-locking and delay-induced instabilities in a dualfrequency fiber laser

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Phase-locking and delay-induced instabilities in a dualfrequency fiber laser M. Guionie, 1 A. Thorette, 1 M. Romanelli, 1* A. Carré, 1 G. Loas, 1 E. Pinsard, 2 L. Lablonde, 2 B. Cadier, 2 M. Alouini, 1 M. Vallet, [START_REF] Guionie | Beat note stabilization in dual-polarization DFB fiber lasers by an optical phaselocked loop[END_REF] and M. Brunel 1

1 Univ Rennes, CNRS, Institut FOTON UMR 6082, F-35000 Rennes, France [START_REF] Thorette | Linewidth enhancement factor measurement based on FM-modulated optical injection: application to rare-earth-doped active medium[END_REF] iXblue Photonics, F-22300 Lannion, France *corresponding author: marco.romanelli@univ-rennes1.fr Abstract We show that the polarization modes of a dual-frequency fiber laser can be efficiently phaselocked using optical frequency-shifted feedback, leading to a stable optically-carried microwave clock signal. We also show that a delay-induced instability, characterized by periodic pulses in the envelope of the beat-note signal, takes place inside the phase-locking range. This observation agrees with the prediction of a delayed rate equation model.

Dual-frequency fiber lasers (DFFL) are attractive thanks to their compactness, ruggedness, and ease of integration. In particular, they are attractive sources for microwave photonics. Indeed, because of the birefringence induced by the UV photo-inscription of the Bragg gratings, these lasers can oscillate on two polarization modes with a frequency splitting in the GHz range.. This produces RF beatings in the emitted optical power having a good spectral purity (typically the instantaneous linewidth of the RF beat signal is of a few kHz in the free-running regime).

For applications such as the generation and distribution of a clock signal, further stabilization of the beating is mandatory. We have shown recently that it can be obtained with an optical phase-locked-loop using the pump power as an actuator [1]. In this contribution, we present another locking scheme, namely a passive scheme (in the sense that no active electronic control is required) based on optical feedback and taking advantage of the laser synchronization dynamics. The experimental setup is sketched in Fig. 1. The DFFL is a 33 mm-long Er 3+ -doped fiber into which phase-shifted Bragg grating was photo-induced. The intensity transmission coefficients of the resulting mirrors are estimated to be -34 dB and -57 dB, respectively. The laser is pumped at 976 nm through a pump/signal combiner (not shown in the Figure ), and emits at 1547 nm two orthogonally-polarized fields at frequencies ν x and ν y , with a total output power of about 100 µW. The frequency difference is measured to be close to 1 GHz. The optical feedback loop is composed of a polarization controller (PC), a fibered polarization-maintaining polarizing beam splitter (PBS), an electro-optical modulator (EOM), and an erbium-doped fiber amplifier (EDFA). The EOM is driven by a low-noise microwave synthesizer oscillating at the frequency f LO , such that the sideband at frequency ν x + f LO is almost resonant with the ν y mode. Under suitable conditions, the ν y mode locks to the optically injected sideband; as a result, the beating at frequency ν y -ν x locks to the master oscillator signal at frequency f LO .

We have observed that such a passive locking scheme produces robust phase-locking, with a large locking range (typically around 4 MHz). The width of the locking range is such that phase-locking is maintained over several days in a laboratory environment. The phase-locked beating has a sub-Hz linewidth; its phase noise is limited at low frequency by the phase noise of the master oscillator, and the measured phase noise level was -104 dBc/Hz at 1 kHz offset from the 1 GHz carrier. Furthermore, we have found that a dynamical instability takes place in this system. As shown in Fig. 2, it is experimentally found that for small, positive detunings, the amplitude of the RF oscillations is no longer constant: strong amplitude modulation develops, resulting in periodic self-pulsing of the envelope of the RF signal. A noticeable feature of this instability is that it occurs inside the phase-locking range: as the detuning between the master oscillator and the natural beating frequency is further increased, phase-locking is recovered. These features are well reproduced by a delayed rate-equation model [2]. The numerical analysis indicates that the time delay associated to the feedback loop, even if it is small compared to the laser intrinsic timescale, is essential in inducing the bifurcation to the self-pulsing regime. Furthermore, the Henry α factor [2] must also be taken into account, as is suggested by the asymmetric behaviour with respect to the detuning. In conclusion, we have demonstrated that a stabilization loop based on frequency-shifted optical feedback is effective in order to lock a DFFL on an external local oscillator, thus achieving a high-spectral purity optically-carried microwave clock. Perspectives for future works include scaling the device to higher carrier frequencies, with or without an external oscillator. We have also shown that an interesting dynamical instability takes place inside the phase-locking range. The analysis of this instability needs to be refined, for instance by analyzing the role of noise.

Figure 1 :

 1 Figure 1: Frequency-shifted feedback scheme. Modulation sideband fed back at ν x + f LO interacts with ν y mode

Figure 2 :

 2 Figure 2: (a) Experimental spectrogram of the RF beating. The frequency f LO of the local oscillator is scanned from 1.012 GHz to 1.018 GHz. The frequency of the free-running beating is slightly below 1.015 GHz. (b) Corresponding numerical simulation. The free-running beating is shifted to 6 MHz for convenience. (c) Periodic self-pulsing of the beat-note envelope occurring in the instability region (numerical simulation).

The authors acknowledge the financial support of DGA (ANR-16-ASTR-0016), and of Région Bretagne, FEDER, Rennes Metropole (CPER SOPHIE-Photonique).