PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of springeropenLink to Publisher's site
Journal of Inequalities and Applications
 
J Inequal Appl. 2017; 2017(1): 73.
Published online 2017 April 11. doi:  10.1186/s13660-017-1348-5
PMCID: PMC5388782

On the Laplacian spectral radii of Halin graphs

Abstract

Let T be a tree with at least four vertices, none of which has degree 2, embedded in the plane. A Halin graph is a plane graph constructed by connecting the leaves of T into a cycle. Thus the cycle C forms the outer face of the Halin graph, with the tree inside it. Let G be a Halin graph with order n. Denote by μ(G) the Laplacian spectral radius of G. This paper determines all the Halin graphs with μ(G) ≥ n − 4. Moreover, we obtain the graphs with the first three largest Laplacian spectral radius among all the Halin graphs on n vertices.

Keywords: Halin graphs, Laplacian spectral radius

Introduction

In this paper, we consider simple and undirected connected graphs. Let GG(VE) be a simple graph with n vertices and m edges. Let NG(v) be the set of vertices adjacent to v in G and d(v) = |NG(v)| be the degree of v. As usual, we denote by Δ and δ the maximum and minimum degree of G, respectively. Denote by G[S] the induced subgraph of G. Let G − v be the graph obtained from G by deleting the vertex v ∈ V(G). Similarly, G − e denote the graph obtained from G by deleting an edge e ∈ G. Let G1 and G2 be two vertex disjoint graphs. The graph G1 ∪ G2 is the graph with vertex set V(G1) ∪ V(G2) and edge set E(G1) ∪ E(G2). The join of graphs G1 and G2 is the graph G1 ∨ G2 obtained from G1 ∪ G2 by joining each vertex of G1 with every vertex of G2. As usual, we denote by Pn, Cn and Kn the path, cycle and complete graph on n vertices, respectively.

A Halin graph is a plane graph constructed as follows. Let T be a tree on at least four vertices. All vertices of T have degree 1 or at least 3. The vertices with degree 1 are called leaves. Let C be a cycle connecting the leaves of T in such a way that C forms the boundary of the unbounded face. We always say the tree T is the characteristic tree of G and the cycle C is the primary cycle. Moreover, the vertices of C are called exterior vertices and the other vertices are called interior vertices. The Halin graphs was introduced by Halin [1]. We call K1 ∨ Cn−1 the wheel graph, denoted by Wn. Clearly, Wn is the unique Halin graph with only one interior vertex. In particular, we use H(t1t2) and H(t1t2t3t4) to denote the Halin graphs with two interior vertices and three interior vertices, respectively (see Figure 1).

Figure 1
Halin graphs H(t1t2) and H(t1t2t3t4) .

For a graph G, we assume d1 ≥ d2 ≥  ⋯  ≥ dn is the degree sequence of G and D(G) = diag(d1d2, …, dn) is the diagonal matrix of vertex degree. Let A(G) be the adjacency matrix. The Laplacian matrix of G is defined as L(G) = D(G)−A(G). Obviously, L(G) is a positive semi-definite symmetric matrix, and its eigenvalues are denoted by μ1(G) ≥ μ2(G) ≥  ⋯  ≥ μn(G) = 0. Moreover, μ(G) = μ1(G) is called the Laplacian spectral radius of G. Let Gc be the complement graph of G. It is well known that

μi(Gc) = n − μni(G) for i = 1, 2, …, n − 1.

Consequently, we obtain a trivial upper bound of the Laplacian spectral radius: μ(G) ≤ n. Let G be a Halin graph on n vertices, μ(G) ≥ Δ(G) + 1 ≥ 4, the equality holds if and only if G ≅ W4.

The Laplacian eigenvalues of G can be used in several physical and chemical problems. Many researchers pay attention to the Laplacian spectra of graphs (see [211]). Halin graph is very important in the mathematical literature. In this paper we study the Laplacian spectral radii of Halin graphs. The following are our main results.

Theorem 1.1

Let G be a Halin graph on n vertices.

  • (i) n ≥ μ(G) > n − 1 if and only if GWn.
  • (ii) n − 1 ≥ μ(G) > n − 2 if and only if GH(n − 4, 2).
  • (iii) n − 2 ≥ μ(G) > n − 3 if and only if G ∈ {H(n − 5, 3), H(2, 2, 1, 0)}.
  • (iv) n − 3 ≥ μ(G) ≥ n − 4 if and only if G ∈ {H(n − 6, 4), H(3, 2, 1, 1), H(n − 6, 2, 1, 0), H(2, 2, t3t4)} where t3t4 ≥ 2.
  • (v) If G ∉ {WnH(n − 4, 2), H(n − 5, 3)}, μ(Wn) > μ(H(n − 4, 2)) > μ(H(n − 5, 3)) > μ(G).

Preliminaries

In order to prove the theorem, we present some lemmas which will be used frequently in the proof.

Lemma 2.1

[7]

Let G be a connected graph on n vertices with at least one edge. Then μ(G) ≥ Δ(G) + 1 with equality holding if and only if Δ(G) = n − 1.

Lemma 2.2

[12]

Let G be a graph and q(G) be the signless Laplacian spectral radius. Then μ(G) ≤ q(G). Moreover, if G is connected, then the equality holds if and only if G is a bipartite graph.

Lemma 2.3

[13]

Let G be a simple connected graph with n vertices and degree sequence d1 ≥ d2 ≥  ⋯  ≥ dn. Then

q(G)min1in{d1+2di1+(2did1+1)2+8(i1)(d1di)2}.

Lemma 2.4

[2]

Let G be a connected graph. Then

μ(G) ≤ max {d(u) + d(v)∣uv ∈ E(G)}.

Moreover, the equality holds if and only if G is a regular bipartite graph or a semiregular bipartite graph.

For a graph G, we denote by m(v) the average of degrees of the vertices adjacent to v, that is,

m(v)=uN(v)d(u)d(v).

As usual, d(v)m(v) is called the 2-degree of vertex v.

Lemma 2.5

[6, 8]

Let G be a simple graph. Then

μ(G)max{d(u)(d(u)+m(u))+d(v)(d(v)+m(v))d(u)+d(v)|uvE(G)}.

If G is connected, then equality holds if and only if G is a regular bipartite graph or a semiregular bipartite graph.

Lemma 2.6

[14]

Let G be a Halin graph with k interior vertices. Then |E(G)| = 2n − k − 1 and n ≥ 2k + 2.

First, we discuss the Halin graphs with at least four interior vertices.

Lemma 2.7

Let G be a Halin graph with k interior vertices. If k ≥ 4, then μ(G) < n − 4.

Proof

Let G be a Halin graph with the primary cycle C. It follows from Lemma 2.6 that n ≥ 2k + 2 ≥ 10. Consider any edge uv ∈ E(G). If uv ∈ V(C), then d(u) + d(v) = 6 ≤ n − 4. If u ∈ V(C) and v ∉ V(C). Suppose that d(v) = t + 1. Note that t + 1 + 3(k − 1)−2(k − 1) = tk ≥ t + 4, there are at least t + 4 vertices in C. Then n − k = |V(C)| ≥ t + 4, and thus d(u) + d(v) = t + 1 + 3 ≤ n − k ≤ n − 4. If uv ∉ V(C), and let d(u) = t1 + 1 and d(v) = t2 + 1. Similarly, t1 + 1 + t2 + 1 + 3(k − 2)−2(k − 1) = t1t2k − 2 ≥ t1t2 + 2, so there are at least t1t2 + 2 vertices in C. Then n − k = |V(C)| ≥ t1t2 + 2, and therefore d(u) + d(v) = t1 + 1 + t2 + 1 ≤ n − k ≤ n − 4. In each case, we always have d(u) + d(v) ≤ n − 4. It follows from Lemma 2.4 that μ(G) < n − 4.

Next, we consider the Halin graphs with three interior vertices. Let GH(t1t2t3t4) and t1 ≥ t2 ≥ 2. Let u, v and w be three interior vertices. For simplicity, we may take tt3t4 ≥ 1. It is clear that d(u) = t1 + 1, d(v) = t + 2, d(w) = t2 + 1 and ntt1t2 + 3.

Lemma 2.8

Let GH(t1t2t3t4) be a Halin graph with t1 ≥ t2 ≥ 3. Then μ(G) < n − 4.

Proof

For t2 ≥ 4, it can easily be seen that n ≥ 12 and

{t=n(t1+t2+3)n11,t1=n(t+t2+3)n8,t2=n(t+t1+3)n8.

Consider all types of edges in G. Let u ∈ N(u) ∩ V(C), v ∈ N(v) ∩ V(C) and w ∈ N(w) ∩ V(C). It is obvious that d(u) = d(v) = d(w) = 3. Then it follows that

d(u)+d(v)=t1+t+3=nt2n4;d(v)+d(w)=t2+t+3=nt1n4;d(u)+d(u)=t1+1+3=t1+4n8+4=n4;d(w)+d(w)=t2+1+3=t2+4n8+4=n4;d(v)+d(v)=t+2+3n11+5=n6.

If xy is an edge in C, then d(x) + d(y) = 6 ≤ n − 4. Consequently, we have d(x) + d(y) ≤ n − 4 for each edge xy ∈ E(G). Then it follows from Lemma 2.4 that μ(G) < n − 4 in this case.

If t2 = 3, then t1 ≥ t2 = 3 and ntt1t2 + 3 ≥ t1 + 7. In this case, we use the bound in Lemma 2.5 to prove the result. Let u ∈ N(u) ∩ V(C), v ∈ N(v) ∩ V(C) and w ∈ N(w) ∩ V(C). Note that

{d(u)=t1+1,d(v)=t+2=nt14,d(w)=4,d(u)=d(v)=d(w)=3.

The 2-degree of each vertex is as follows:

{d(u)m(u)=n+2t14,d(v)m(v)=3n2t113,d(w)m(w)=nt1+5,d(u)m(u)=t1+7,d(v)m(v)=nt1+2,d(w)m(w)=10.

For all types of edges in G, consider the index in Lemma 2.5. Let exy be an edge of G. Put

f(e)=f(xy)=d(x)(d(x)+m(x))+d(y)(d(y)+m(y))d(x)+d(y).

For simplicity, we use type uu to denote the edges uiuj ∈ E(G) where uiuj ∈ N(u) ∩ V(C). Similarly, we define the symbol vv and ww. Then we will prove that the inequality f(e) ≤ n − 4 holds. Note that each edge of G belongs to the one below (the types uw and vv may not exist).

  • uv:
    f(uv)=d(u)(d(u)+m(u))+d(v)(d(v)+m(v))d(u)+d(v)=(t1+1)2+n+2t14+(nt14)2+3n2t113n3.
    Then f(uv) ≤ n − 4 if and only if (2t13)n2t12+10t112. Since n ≥ t1 + 7, it is easy to verify that (2t13)n(2t13)(t1+7)2t12+10t112 when t1 ≥ 9. So we have f(uv) ≤ n − 4 when t1 ≥ 9.
    If t1 = 8 and n ≥ 16, then (2t13)n208>196=2t12+10t112. Hence f(uv) ≤ n − 4.
    If t1 = 7 and n ≥ 15, then (2t13)n2t12+10t112. Hence f(uv) ≤ n − 4.
    An argument similar to the above shows that f(uv) ≤ n − 4 when {t1=6,n14, {t1=5,n13, {t1=4,n12, and {t1=3,n12.
    Thus we conclude that inequality f(uv) ≤ n − 4 holds with
    {t19,t1=8andn16,t1=7andn15,t1=6andn14,t1=5andn13,t1=4andn12,t1=3andn12.
  • vw:
    f(vw)=(nt14)2+3n2t113+16+nt1+5nt1.
    Then f(vw) ≤ n − 4 if and only if t1nt12+t1+24. The inequality f(vw) ≤ n − 4 holds with
    {t14,t1=3andn12.
  • uu:
    f(uu)=(t1+1)2+n+2t14+9+t1+7t1+4.
    Then f(uu) ≤ n − 4 if and only if (t1+3)nt12+9t1+29. The inequality f(uu) ≤ n − 4 holds with
    {t18,t1=7andn15,t1=6andn14,t1=5andn13,t1=4andn12,t1=3andn11.
  • vv:
    f(vv)=(nt14)2+3n2t113+9+nt1+2nt11.
    Then f(vv) ≤ n − 4 if and only if (t11)nt12+t1+10. The inequality f(vv) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • ww:
    f(ww)=nt1+407.
    Then f(ww) ≤ n − 4 if and only if 6nt1 ≥ 68. The inequality f(ww) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • uv:
    f(uv)=n+276.
    Then f(uv) ≤ n − 4 if and only if 5n ≥ 51. The inequality f(uv) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • vw:
    f(vw)=nt1+306.
    Then f(vw) ≤ n − 4 if and only if 5nt1 ≥ 54. The inequality f(vw) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • uw:
    f(uw)=t1+356.
    Then f(uw) ≤ n − 4 if and only if 6n − t1 ≥ 59. The inequality f(uw) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • uu:
    f(uu)=9+t1+73.
    Then f(uu) ≤ n − 4 if and only if 3n − t1 ≥ 28. The inequality f(uu) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • vv:
    f(vv)=9+nt1+23.
    Then f(vv) ≤ n − 4 if and only if 2nt1 ≥ 23. The inequality f(vv) ≤ n − 4 holds with
    t1 ≥ 3.
  • ww:
    f(ww)=193.
    Then f(ww) ≤ n − 4 if and only if 3n ≥ 31. The inequality f(vv) ≤ n − 4 holds with
    {t14,t1=3andn11.

We summarize what has been discussed above as follows.

  • If t1 ≥ 9, then max {f(e)|e ∈ E(G)} ≤ n − 4. Moreover, since G is not a bipartite graph, it follows from Lemma 2.5 that μ(G) < n − 4.
  • If t1 = 8, then n ≥ 15. When n ≥ 16, we have max {f(e)|e ∈ E(G)} ≤ n − 4. Hence μ(G) < n − 4. When n = 15, that is, GH(8, 3, 1, 0). Note that μ(H(8, 3, 1, 0)) ≈ 10.0680 < n − 4. Thus μ(G) < n − 4 when t1 = 8.
  • If t1 = 7, then n ≥ 14. When n ≥ 15, we infer that max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 14, then GH(7, 3, 1, 0). Since μ(H(7, 3, 1, 0)) ≈ 9.0913 < n − 4, it follows that μ(G) < n − 4 when t1 = 7.
  • If t1 = 6, then n ≥ 13. When n ≥ 14, we have max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 13, then GH(6, 3, 1, 0). By the fact that μ(H(6, 3, 1, 0)) ≈ 8.1298 < n − 4, it follows that μ(G) < n − 4 when t1 = 6.
  • If t1 = 5, then n ≥ 12. When n ≥ 13, we infer that max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 12, then GH(5, 3, 1, 0). Since μ(H(5, 3, 1, 0)) ≈ 7.2022 < n − 4, it follows that μ(G) < n − 4 when t1 = 5.
  • If t1 = 4, then n ≥ 11. When n ≥ 12, we infer that max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 11, then GH(4, 3, 1, 0). Now that μ(H(4, 3, 1, 0)) ≈ 6.3694 < n − 4, it follows that μ(G) < n − 4 when t1 = 4.
  • If t1 = 3, then n ≥ 10. When n ≥ 12, we infer that max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 11, then GH(3, 3, 2, 0) or H(3, 3, 1, 1). If n = 10, then GH(3, 3, 1, 0). Note that μ(H(3, 3, 2, 0)) ≈ 6.1116 < n − 4, μ(H(3, 3, 1, 1)) ≈ 6.4142 < n − 4 and μ(H(3, 3, 1, 0)) ≈ 5.8577 < n − 4. Therefore μ(G) < n − 4 in this case.

Thus we have derived that μ(G) < n − 4 when t2 = 3. This completes the proof.

Lemma 2.9

Let GH(t1t2t3t4) be a Halin graph with t1 ≥ t2 = 2.

  1. If t1 = 2 or n − 6, then μ(G) > n − 4.
  2. If 3 ≤ t1 ≤ n − 7 and G ≠ H(3, 2, 1, 1), then μ(G) < n − 4.

Proof

For t2 = 2. If t1 = 2 or n − 6, then Δ(G) = n − 5. According to Lemma 2.1, it follows that μ(G) > Δ + 1 = n − 4. Therefore (1) holds.

Suppose 3 ≤ t1 ≤ n − 7. Obviously, n ≥ t1 + 7. We also use the bound in Lemma 2.5 to prove the result. Let u ∈ N(u) ∩ V(C), v ∈ N(v) ∩ V(C) and w ∈ N(w) ∩ V(C). Note that

{d(u)=t1+1,d(v)=nt13,d(w)=3,d(u)=d(v)=d(w)=3.

Then the 2-degree of each vertex is as follows:

{d(u)m(u)=n+2t13,d(v)m(v)=3n2t111,d(w)m(w)=nt1+3,d(u)m(u)=t1+7,d(v)m(v)=nt1+3,d(w)m(w)=9.

For all types of edges in G, consider the index in Lemma 2.5. Let exy be any one edge of G. Put

f(e)=f(xy)=d(x)(d(x)+m(x))+d(y)(d(y)+m(y))d(x)+d(y).

For simplicity, we use uu to denote the edges uu ∈ E(G) where uu ∈ N(u) ∩ V(C). Similarly, we define the symbol vv and ww. Then we will prove that the inequality f(e) ≤ n − 4 holds. Note that every edge of G belongs to the one below, and the types uw and vv exist in some circumstances.

  • uv:
    f(uv)=(t1+1)2+n+2t13+(nt13)2+3n2t111n2.
    Then f(uv) ≤ n − 4 if and only if (t12)nt12+4t16. The inequality f(uv) ≤ n − 4 holds with
    {t18,t1=7andn15,t1=6andn14,t1=5andn13,t1=4andn13,t1=3andn15.
  • vw:
    f(vw)=(nt13)2+3n2t111+9+nt1+3nt1.
    Then f(vw) ≤ n − 4 if and only if (t12)nt12t1+10. The inequality f(vw) ≤ n − 4 holds with
    {t14,t1=3andn16.
  • uu:
    f(uu)=(t1+1)2+n+2t13+9+t1+7t1+4.
    Then f(uu) ≤ n − 4 if and only if (t1+3)nt12+9t1+30. The inequality f(uu) ≤ n − 4 holds with
    {t19,t1=8andn16,t1=7andn15,t1=6andn14,t1=5andn13,t1=4andn12,t1=3andn11.
  • vv:
    f(vv)=(nt13)2+3n2t111+9+nt1+3nt1.
    Then f(vv) ≤ n − 4 if and only if (t12)nt12t1+10. The inequality f(vv) ≤ n − 4 holds with
    {t14,t1=3andn16.
  • ww:
    f(ww)=nt1+306.
    Then f(ww) ≤ n − 4 if and only if 5nt1 ≥ 54. The inequality f(ww) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • uv:
    f(uv)=n+286.
    Then f(uv) ≤ n − 4 if and only if 5n ≥ 52. The inequality f(uv) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • vw:
    f(vw)=nt1+306.
    Then f(vw) ≤ n − 4 if and only if 5nt1 ≥ 54. The inequality f(vw) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • uw:
    f(uw)=t1+346.
    Then f(uw) ≤ n − 4 if and only if 6n − t1 ≥ 58. The inequality f(uw) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • uu:
    f(uu)=9+t1+73.
    Then f(uu) ≤ n − 4 if and only if 3n − t1 ≥ 28. The inequality f(uu) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • vv:
    f(vv)=9+nt1+33.
    Then f(vv) ≤ n − 4 if and only if 2nt1 ≥ 24. The inequality f(vv) ≤ n − 4 holds with
    {t14,t1=3andn11.
  • ww:
    f(ww) = 6.
    Since n ≥ t1 + 7 ≥ 10, we have f(ww) ≤ n − 4.

So we have the following conclusions.

  • If t1 ≥ 9, then max {f(e)|e ∈ E(G)} ≤ n − 4. According to Lemma 2.5, it follows that μ(G) < n − 4.
  • If t1 = 8, then n ≥ 15. When n ≥ 16, we have max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 15, then GH(8, 2, 2, 0) or H(8, 2, 1, 1). Note that μ(H(8, 2, 2, 0)) ≈ 10.0928 < n − 4 and μ(H(8, 2, 1, 1)) ≈ 10.1016 < n − 4. Thus μ(G) < n − 4 when t1 = 8.
  • If t1 = 7, then n ≥ 14. When n ≥ 15, we have max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 14, then GH(7, 2, 2, 0) or H(7, 2, 1, 1). Note that μ(H(7, 2, 2, 0)) ≈ 9.1261 < n − 4 and μ(H(7, 2, 1, 1)) ≈ 9.1414 < n − 4. Hence μ(G) < n − 4 when t1 = 7.
  • If t1 = 6, then n ≥ 13. When n ≥ 14, we have max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 13, then GH(6, 2, 2, 0) or H(6, 2, 1, 1). Note that μ(H(6, 2, 2, 0)) ≈ 8.1820 < n − 4 and μ(H(6, 2, 1, 1)) ≈ 8.2113 < n − 4. Hence μ(G) < n − 4 when t1 = 6.
  • If t1 = 5, then n ≥ 12. When n ≥ 13, we have max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 12, then GH(5, 2, 2, 0) or H(5, 2, 1, 1). Note that μ(H(5, 2, 2, 0)) ≈ 7.2861 < n − 4 and μ(H(5, 2, 1, 1)) ≈ 7.3502 < n − 4. Hence μ(G) < n − 4 when t1 = 5.
  • If t1 = 4, then n ≥ 11. When n ≥ 13, we have max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 12, then GH(4, 2, 3, 0) or H(4, 2, 2, 1). If n = 11, then GH(4, 2, 2, 0) or H(4, 2, 1, 1). Note that μ(H(4, 2, 3, 0)) ≈ 6.8985 < n − 4, μ(H(4, 2, 2, 1)) ≈ 7.0131 < n − 4, μ(H(4, 2, 2, 0)) ≈ 6.5037 < n − 4 and μ(H(4, 2, 1, 1)) ≈ 6.6518 < n − 4. Therefore μ(G) < n − 4 when t1 = 4.
  • If t1 = 3, then n ≥ 10. When n ≥ 15, we have max {f(e)|e ∈ E(G)} ≤ n − 4. If n = 10, 11, 12, 13, 14, then G ∈ ℍ = {H(3, 2, 2, 0), H(3, 2, 1, 1), H(3, 2, 3, 0), H(3, 2, 2, 1), H(3, 2, 4, 0), H(3, 2, 3, 1), H(3, 2, 2, 2), H(3, 2, 5, 0), H(3, 2, 4, 1), H(3, 2, 3, 2), H(3, 2, 6, 0), H(3, 2, 5, 1), H(3, 2, 4, 2), H(3, 2, 3, 3)}.
    Note that μ(H(3, 2, 1, 1)) ≈ 6.2470 > n − 4 and if G ∈ ℍ∖{H(3, 2, 1, 1)} then μ(G) < n − 4 (see Table 1). This implies that if t1 = 3 and G ≠ H(3, 2, 1, 1), then μ(G) < n − 4.
    Table 1
    The Laplacian spectral radii of some Halin graphs with three interior vertices

Consequently, we infer that (2) holds. This completes the proof.

For Halin graphs with three interior vertices. From the proof of the above lemmas, we see that only H(3, 2, 1, 1), H(2, 2, t3t4) and H(n − 6, 2, 1, 0) have the Laplacian spectral radii greater than n − 4. Clearly, n − 4 < μ(H(3, 2, 1, 1)) < n − 3 (see Table 1).

Lemma 2.10

Let G ∈ {H(2, 2, t3t4), H(n − 6, 2, 1, 0)}, where t3t4 ≥ 2, then μ(G) ≤ n − 3. If GH(2, 2, 1, 0), then n − 3 < μ(G) < n − 2.

Proof

It is clear that H(2, 2, t3t4) and H(n − 6, 2, 1, 0) have the same degree sequence:

(d1d2, …, dn) = (n − 5, 3, 3, …, 3).

Let G ∈ {H(2, 2, t3t4), H(n − 6, 2, 1, 0)}. By Lemmas 2.2 and 2.3, we have

μ(G)<min1in{d1+2di1+(2did1+1)2+8(i1)(d1di)2}n5+61+(6(n5)+1)2+8(n53)2=n+(n12)2+8(n8)2.

If n ≥ 11, it is easy to check that

n3n+(n12)2+8(n8)2.

Therefore μ(G) < n − 3. If 8 ≤ n ≤ 10, then G ∈ {H(2, 2, 1, 0), H(2, 2, 2, 0), H(2, 2, 1, 1), H(3, 2, 1, 0), H(2, 2, 3, 0), H(2, 2, 2, 1), H(4, 2, 1, 0)}. If GH(2, 2, 1, 0), then n − 3 < μ(G) < n − 2. Otherwise, μ(G) ≤ n − 3 (see Table 1). This lemma follows.

Now we consider the Halin graphs with two interior vertices. Let GH(t1t2) and t1 ≥ t2 ≥ 2. Note that t1n − t2 − 2 ≥ t2, then n ≥ 2t2 + 2.

Lemma 2.11

Let GH(t1t2) be a Halin graph with t1 ≥ t2 ≥ 5. Then μ(G) < n − 4.

Proof

Suppose u and v are the two interior vertices. Let u ∈ N(u) ∩ V(C) and v ∈ N(v) ∩ V(C). Note that

{d(u)=nt21,d(v)=t2+1,d(u)=d(v)=3.

Then the 2-degree of each vertex is as follows:

{d(u)m(u)=3n2t25,d(v)m(v)=n+2t21,d(u)m(u)=nt2+5,d(v)m(v)=t2+7.

For all types of edges in G, consider the index in Lemma 2.5. Let exy be any one edge of G. We may take

f(e)=f(xy)=d(x)(d(x)+m(x))+d(y)(d(y)+m(y))d(x)+d(y).

For simplicity, we use uu to denote the edges uu ∈ E(G) where uu ∈ N(u) ∩ V(C). Similarly, we define the symbol vv. It is clear that every edge of G belongs to the one below.

  • uv:
    f(uv)=(nt21)2+3n2t25+(t2+1)2+n+2t21n.
    Then f(uv) ≤ n − 4 if and only if (t23)nt22+2t22. The inequality f(uu) ≤ n − 4 holds with
    {t27,t2=6andn16,t2=5andn17.
  • uu:
    f(uu)=(nt21)2+3n2t25+9+nt2+5nt2+2.
    Then f(uu) ≤ n − 4 if and only if (t24)nt225t2+18. The inequality f(uu) ≤ n − 4 holds with
    {t26,t2=5andn18.
  • vv:
    f(vv)=(t2+1)2+n+2t21+9+t2+7t2+4.
    Then f(vv) ≤ n − 4 if and only if (t2+3)nt22+9t2+32. The inequality f(vv) ≤ n − 4 holds with
    {t26,t2=5andn13.
  • uv:
    f(uv)=n+306.
    Then f(uv) ≤ n − 4 if and only if 5n ≥ 54. If t2 ≥ 5, f(uv) ≤ n − 4.
  • uu:
    f(uu)=18+2(nt2+5)6.
    Then f(uu) ≤ n − 4 if and only if 2nt2 ≥ 26. If t2 ≥ 5, f(uu) ≤ n − 4.
  • vv:
    f(vv)=18+2(t2+7)6.
    Then f(vv) ≤ n − 4 if and only if 3n − t2 ≥ 28. If t2 ≥ 5, f(vv) ≤ n − 4.

Thus we infer that max {f(e)|e ∈ E(G)} ≤ n − 4 if t2 ≥ 7, {t2=6,n16, or {t2=5,n18. According to Lemma 2.5, it follows that μ(G) < n − 4. Otherwise,

G ∈ {H(5, 5), H(6, 5), H(6, 6), H(7, 5), H(7, 6), H(8, 5), H(9, 5), H(10, 5)}.

It is easy to see that μ(G) < n − 4 in this case (see Table 2). This completes the proof.

Table 2
The Laplacian spectral radii of some Halin graphs with two interior vertices

Lemma 2.12

Let GH(n − 6, 4) be a Halin graph with n ≥ 10 vertices. Then n − 4 < μ(G) < n − 3.

Proof

Since Δ(G) = n − 5, it follows from Lemma 2.1 that μ(G) > n − 4. The degree sequence of G is (d1d2, …, dn) = (n − 5, 5, 3, …, 3). From Lemmas 2.2 and 2.3, we have

μ(G)<min1in{d1+2di1+(2did1+1)2+8(i1)(d1di)2}d1+2d21+(2d2d1+1)2+8(d1d2)2=n+4+(n16)2+8(n10)2.

If n ≥ 19, then we get

n3n+4+(n16)2+8(n10)2.

Therefore μ(G) < n − 3 when n ≥ 19. If n ≤ 18, then GH(t1, 4) where t1 = 4, 5, 6, …, 12. It is easy to check that μ(G) < n − 3 (see Table 2). Thus we complete the proof.

Lemma 2.13

Let GH(n − 5, 3) be a Halin graph with n ≥ 8 vertices. Then n − 3 < μ(G) ≤ n − 2. Moreover, the right equality holds if and only GH(3, 3).

Proof

The degree sequence of G is (d1d2, …, dn) = (n − 4, 4, 3, …, 3). It follows from Lemma 2.1 that μ(G) > Δ(G) + 1 = n − 3. From Lemmas 2.2 and 2.3, we have

μ(G)<min1in{d1+2di1+(2did1+1)2+8(i1)(d1di)2}d1+2d21+(2d2d1+1)2+8(d1d2)2=n+3+(n13)2+8(n8)2.

If n ≥ 14, then

n2n+3+(n13)2+8(n8)2.

Therefore μ(G) < n − 3. If n ≤ 13, then GH(t1, 3) where t1 = 3, 4, 5, …, 8. It is clear that μ(H(3, 3)) = n − 2 and μ(H(t1, 3)) < n − 2 where t1 = 4, 5, …, 8 (see Table 2). Thus we complete the proof.

Lemma 2.14

Let GH(n − 4, 2) be a Halin graph with n ≥ 6 vertices. Then n − 2 < μ(G) ≤ n − 1. Moreover, the right equality holds if and only GH(2, 2).

Proof

The degree sequence of G is (d1d2, …, dn) = (n − 3, 3, 3, …, 3). It follows from Lemma 2.1 that μ(G) > Δ(G) + 1 = n − 2. From Lemmas 2.2 and 2.3, we have

μ(G)<min1in{d1+2di1+(2did1+1)2+8(i1)(d1di)2}d1+2d21+(2d2d1+1)2+8(d1d2)2=n+2+(n10)2+8(n6)2.

If n ≥ 9, then

n1n+2+(n10)2+8(n6)2.

Therefore μ(G) < n − 1. If n ≤ 8, then GH(2, 2), H(3, 2) or H(4, 2). It is clear that μ(H(2, 2)) = n − 1, μ(H(3, 2)) < n − 1 and μ(H(4, 2)) < n − 1 (see Table 2). Thus we complete the proof.

Now we are ready to present the proof of Theorem 1.1. In fact, from the previous lemmas, it is easy to obtain the main result. For the sake of completeness, we provide a brief proof.

Proof of Theorem 1.1

Let G be a Halin graph. We make a summary of Lemmas 2.6-2.14.

If G has k ≥ 4 interior vertices, then μ(G) < n − 4.

If G has three interior vertices, then μ(G) < n − 4 when G ∉ {H(2, 2, t3t4), H(n − 6, 2, 1, 0), H(3, 2, 1, 1)}, where t3t4 ≥ 1; if G ∈ {H(2, 2, t3t4), H(n − 6, 2, 1, 0), H(3, 2, 1, 1)}, where t3t4 ≥ 2, then n − 4 < μ(G) ≤ n − 3; if GH(2, 2, 1, 0), then n − 3 < μ(G) < n − 2.

If G has two interior vertices, then μ(G) < n − 4 when

G ∉ {H(n − 6, 4), H(n − 5, 3), H(n − 4, 2)}.

On the other hand, we have n − 4 < μ(H(n − 6, 4)) < n − 3, n − 3 < μ(H(n − 5, 3)) ≤ n − 2, n − 2 < μ(H(n − 4, 2)) ≤ n − 1 and μ(H(n − 5, 3)) > μ(H(2, 2, 1, 0)).

If G has one interior vertex, then GWn and μ(Wn) = n.

It is now obvious that the theorem holds.

Remark 3.1

From the proof, we see that there is no graph with n − 1 < μ(G) < n. If μ(G) = n − 1 iff GH(2, 2). If μ(G) = n − 2 iff GH(3, 3). There is no graph with μ(G) = n − 4.

Remark 3.2

Let H(n − t − 2, t) be a Halin with n vertices and n ≥ 2t + 2. Then Δ = n − t − 1, so μ(H(n − t − 2, t)) > n − t. The degree sequence is (n − t − 1, t + 1, 3, …, 3), then if n ≥ 5t − 1, we have

μ(H(nt2,t))d1+2d21+(2d2d1+1)2+8(d1d2)2nt+1.

That is, for an integer k, when n is sufficiently large, then n − t < μ(H(n − t − 2, t)) ≤ n − t + 1. From this we propose the following conjecture.

Conjecture 3.1

Let H(t1t2) be a Halin graph with two interior vertices and order n, where nt1t2 + 2 and t1 ≥ t2. Then

  1. n − t2 < μ(H(t1t2)) ≤ n − t2 + 1;
  2. μ(H(t1t2)) < μ(H(t1 + 1, t2 − 1)).

Conclusions

We determine all the Halin graphs with μ(G) ≥ n − 4. Moreover, we also obtain the graphs with the first three largest Laplacian spectral radius among all the Halin graphs on n vertices. Considering the further order of the Laplacian spectral radius of Halin graphs is still an interesting and important problem.

Acknowledgements

This project is supported by NSF of China (Nos.11201432), Henan Natural Science Foundation of Basic Research (162300410072), the Foundation to the Educational Committee of Henan (15A110003).

Footnotes

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

HCJ carried out the proofs of main results in the manuscript. JX participated in the design of the study and drafted the manuscripts. All the authors read and approved the final manuscripts.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Halin R. Über simpliziable Zerfallungen beliebiger. Math. Ann. 1964;156:216–225. doi: 10.1007/BF01363288. [Cross Ref]
2. Anderson W, Morley T. Eigenvalues of the Laplacian of a graph. Linear Multilinear Algebra. 1985;18:141–145. doi: 10.1080/03081088508817681. [Cross Ref]
3. Bıyıkoğlu T, Leydold J. Semiregular trees with minimal Laplacian spectral radius. Linear Algebra Appl. 2010;432:2335–2341. doi: 10.1016/j.laa.2009.06.014. [Cross Ref]
4. Das KCh. Sharp lower bounds on the Laplacian eigenvalues of trees. Linear Algebra Appl. 2004;384:155–169. doi: 10.1016/j.laa.2004.01.012. [Cross Ref]
5. Liu M, Liu B. Some results on the Laplacian spectrum. Comput. Math. Appl. 2010;59:3612–3616. doi: 10.1016/j.camwa.2010.03.058. [Cross Ref]
6. Li J, Zhang X. On Laplacian eigenvalues of a graph. Linear Algebra Appl. 1998;285:305–307. doi: 10.1016/S0024-3795(98)10149-0. [Cross Ref]
7. Merris R. Laplacian matrices of graphs: a survey. Linear Algebra Appl. 1994;197-198:143–176. doi: 10.1016/0024-3795(94)90486-3. [Cross Ref]
8. Pan Y. Sharp upper bounds for the Laplacian graph eigenvalues. Linear Algebra Appl. 2002;355:287–295. doi: 10.1016/S0024-3795(02)00353-1. [Cross Ref]
9. Simic SK, Stanic Z. On some forests determined by their Laplacian or signless Laplacian spectrum. Comput. Math. Appl. 2009;58:171–178. doi: 10.1016/j.camwa.2009.04.005. [Cross Ref]
10. Teranishi Y. Subgraphs and the Laplacian spectrum of a graph. Linear Algebra Appl. 2011;435:1029–1033. doi: 10.1016/j.laa.2011.02.019. [Cross Ref]
11. Yuan X, Shan H, Liu Y. On the Laplacian spectral radii of trees. Discrete Math. 2009;309:4241–4246. doi: 10.1016/j.disc.2008.12.026. [Cross Ref]
12. Zhang X, Luo R. The spectral radius of triangle-free graphs. Australas. J. Comb. 2002;26:33–39.
13. Yu G, Wu Y, Shu J. Sharp bounds on the signless Laplacian spectral radii of graphs. Linear Algebra Appl. 2011;434:683–687. doi: 10.1016/j.laa.2010.09.029. [Cross Ref]
14. Shu J, Hong Y. The upper bound for the spectral radius of outplanar graphs and Halin graphs. Chin. Ann. Math., Ser. A. 2000;21(6):677–682.

Articles from Springer Open Choice are provided here courtesy of Springer