PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 95 (109) (2014), 189–199 DOI: 10.2298/PIM1409189N

AN ASYMPTOTICALLY TIGHT BOUND ON THE Q-INDEX OF GRAPHS WITH FORBIDDEN CYCLES

Vladimir Nikiforov

Communicated by Slobodan Simić

Abstract. Let G be a graph of order n and let q(G) be the largest eigenvalue of the signless Laplacian of G. It is shown that if k ⩾ 2, n > 5k^{2}, and q(G) ⩾ n + 2k − 2, then G contains a cycle of length l for each l ∈ {3, 4, …, 2k + 2}. This bound on q(G) is asymptotically tight, as the graph K_{k} ∨ \overline{K}_{n−k} contains no cycles longer than 2k and

q(K_{k} ∨ \overline{K}_{n−k} ) > n + 2k − 2 − \frac{2k(k − 1)}{n + 2k − 3} .

The main result gives an asymptotic solution to a recent conjecture about the maximum q(G) of a graph G with forbidden cycles. The proof of the main result and the tools used therein could serve as a guidance to the proof of the full conjecture.

1. Introduction

Given a graph G, the Q-index of G is the largest eigenvalue q(G) of its signless Laplacian Q(G). In this note we give an asymptotically tight upper bound on q(G) of a graph G of a given order, with no cycle of specified length. Let us start by recalling a general problem in spectral extremal graph theory:

How large can q(G) be if G is a graph of order n, with no subgraph isomorphic to some forbidden graph F?

This problem has been solved for several classes of forbidden subgraphs; in particular, in [9] it has been solved for forbidden cycles C_{4} and C_{5}. In addition, it seems a folklore result that q(G) > n implies the existence of C_{3}, and this bound is exact in view of the star of order n. For longer cycles, a general conjecture has been stated in [9], which we reiterate next to clarify the contribution of the present note.

2010 Mathematics Subject Classification: 15A42; 05C50.

Key words and phrases: signless Laplacian; maximum eigenvalue; forbidden cycles; spectral extremal problems.

Let S_{n,k} be the graph obtained by joining each vertex of a complete graph of order k to each vertex of an independent set of order n − k; in other words, S_{n,k} = K_{k} ∨\overline{K}_{n−k} . Also, let S_{n,k}^{+} be the graph obtained by adding an edge to S_{n,k} .

Conjecture 1. Let k ⩾ 2 and let G be a graph of sufficiently large order n. If G has no C_{2k+1} , then q(G) < q(S_{n,k} ), unless G = S_{n,k} . If G has no C_{2k+2} , then q(G) < q(S_{n,k}^{+} ), unless G = S_{n,k}^{+} .

Conjecture 1 seems difficult, but not hopeless. It is very likely that it will be solved completely in the next couple of years. Thus, one of the goals of this note is to make some suggestions for such a solution and to emphasize the relevance of some supporting results.

The starting point of our work is the observation that both q(S_{n,k} ) and q(S_{n,k}^{+} ) are very close to n + 2k − 2 whenever n is large. In fact, the difference between these values is Ω(1/n), as can be seen from the following proposition.

Proposition 2. If k ⩾ 2 and n > 5k^{2}, then

n + 2k − 2 − \frac{2(k^{2} − k)}{n + 2k + 2} > q(S_{n,k}^{+} ) > q(S_{n,k} ) > n + 2k − 2 − \frac{2(k^{2} − k)}{n + 2k − 3} .

These bounds prompt a weaker, yet asymptotically tight version of Conjecture 1, which we shall prove in this note.

Theorem 3. Let k ⩾ 2, n > 6k^{2}, and let G be a graph of order n. If q(G) ⩾ n + 2k − 2, then G contains cycles of length 2k + 1 and 2k + 2.

Before going further, let us note a corollary of Theorem 3.

Corollary 4. Let k ⩾ 2, n > 6k^{2}, and let G be a graph of order n. If q(G) ⩾ n+2k −2, then G contains a cycle of length l for each l ∈ {3, 4, …, 2k +2}.

Indeed, if l ⩾ 5, the conclusion follows immediately from Theorem 3. For l ∈ {3, 4}, recall the bound q(G) ⩽ max{d_{u} + d_{v} : {u, v} ∈ E(G)}. In view of q(G) ⩾ n + 2, there must be an edge {u, v} belonging to two triangles; hence G contains both C_{3} and C_{4}.

Even though Theorem 3 is weaker than Conjecture 1, our proof is not too short. To emphasize its structure, we have extracted a few important points into separate statements, which we give next.

Lemma 5. If G is a graph with no P_{2k+1} , then for each component H of G, either v(H) = 2k or e(H) ⩽ (k − 1)v(H).

Write K_{2k} + v for the graph obtained by joining a vertex v to a single vertex of the complete graph K_{2k}.

Lemma 6. Let v be a vertex of a graph G of order n. If G contains no P_{2k+1} with both endvertices different from v, then 2e(G) − d_{v} ⩽ (2k − 1)(n − 1), unless G is a union of several copies of K_{2k} and one K_{2k} + v.

We also need bounds on q(G) for some special classes of graphs. Since the known upper bounds did not work in these cases, we came up with a few technical results giving the required bounds.

AN ASYMPTOTIC BOUND ON THE Q-INDEX 191

Lemma 7. Let the integers k, p, m, and n satisfy

k ⩾ 2, m ⩾ 1, p ⩾ 0, n = 2kp + m, n ⩾ 6k + 13.

Let H be a graph of order m and let F be the union of p disjoint graphs of order 2k, which are also disjoint from H. Let G be the graph obtained by taking F ∪ H and joining some vertices of F to a single vertex w of H. If

(1)  q(H) ⩽ m + 2k − 2 + \frac{6pk}{n + 3} ,

then q(G) ⩽ n + 2k − 2, with equality holding if and only if equality holds in (1).

The reason for Lemma 7 being so technical is that it must support the proof of the following two quite different corollaries.

Corollary 8. Let k, p, and n be integers such that k ⩾ 2, p ⩾ 0, and n = 2(p+1)k+2. Let G = K_{1}∨((pK_{2k})∪K_{2k+1} ). If n ⩾ 6k+13, then q(G) < n+2k−2.

Given a graph G and u ∈ V (G), write G−u for the graph obtained by removing the vertex u.

Corollary 9. Let k ⩾ 2, G be a graph of order n, and w ∈ V (G). Suppose that for each component C of G − w, either v(C) = 2k or e(C) ⩽ (k − 1)v(C). If n ⩾ 6k + 13, then q(G) < n + 2k − 2.

In the next section we outline some notation and results needed in our proofs. The proofs themselves are given in Section 3.

2. Notation and supporting results

For graph notation and concepts undefined here we refer the reader to [2]. For introductory and reference material on the signless Laplacian see the survey of Cvetković [5] and its references. In particular, let G be a graph, and X and Y be disjoint sets of vertices of G. We write:

- V (G) for the set of vertices of G, E(G) for the set of edges of G, and e(G) for |E(G)|;

- G[X] for the graph induced by X, and e(X) for e(G[X]);

- e(X, Y) for the number of edges joining vertices in X to vertices in Y;

- Γ_{u} for the set of neighbors of a vertex u, and d_{u} for |Γ_{u}|.

We write P_{k}, C_{k}, and K_{k} for the path, cycle, and complete graph of order k.

Given a graph G and a vertex u ∈ V (G), note that

∑_{v∈Γ_{u}} d_{v} = 2e(Γ_{u}) + e(Γ_{u}, V (G) ∖ Γ_{u}).

Below we shall use this fact without reference.

2.1. Some useful theorems. Here we state several known results, all of which are used in the proof of Theorem 3. We start with two classical theorems of Erdős and Gallai [7].

Theorem 10. Let k ⩾ 1. If G is a graph of order n, with no P_{k+2} , then e(G) ⩽ kn/2, with equality holding if and only if G is a union of disjoint copies of K_{k+1} .

Theorem 11. Let k ⩾ 2. If G is a graph of order n, with no C_{k+1} , then e(G) ⩽ k(n − 1)/2, with equality holding if and only if G is a union of copies of K_{k}, all sharing a single vertex.

For connected graphs Kopylov [10] has enhanced Theorem 10 as follows.

Theorem 12. Let k ⩾ 1, and let G be a connected graph of order n.

(i) If n ⩾ 2k + 2 and G contains no P_{2k+2} , then

e(G) ⩽ max\{ kn − k(k + 1)/2, \binom{2k}{2} + (n − 2k)\} ;

(ii) If n ⩾ 2k + 3 and G contains no P_{2k+3} , then

e(G) ⩽ max\{ kn − k(k + 1)/2 + 1, \binom{2k + 1}{2} + (n − 2k − 1)\} .

We refer the reader to the more recent paper [1], where the conditions for equality in Kopylov’s bounds are determined as well.

We shall use the following sufficient condition for Hamiltonian cycles, proved by Ore [13].

Theorem 13. If G is a graph of order n ⩾ 3 and e(G) > \binom{n−1}{2} + 1, then G has a Hamiltonian cycle.

The following structural extension of Theorem 10 has been established in [12].

Theorem 14. Let k ⩾ 1 and let the vertices of a graph G be partitioned into two sets A and B. If 2e(A) + e(A, B) > (2k − 1)|A| + k|B|, then there exists a path of order 2k + 1 with both endvertices in A.

We finish this subsection with two known upper bounds on q(G). The proof of Theorem 3 will be based on a careful analysis of the following bound on q(G), which can be traced back to Merris [11]. The case of equality was established in [8].

Theorem 15. For every graph G,

q(G) ⩽ max\{ d_{u} + \frac{1}{d_{u}} ∑_{v∈Γ_{u}} d_{v} : u ∈ V (G)\} .

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

Finally, let us mention the following corollary, due to Das [6].

Theorem 16. If G is a graph with n vertices and m edges, then

q(G) ⩽ \frac{2m}{n − 1} + n − 2,

with equality holding if and only if G is either complete, or is a star, or is a complete graph with one isolated vertex.

In the next section we prove our main results.

3. Proofs

In the proofs given below there are several instances where the bounds can be somewhat improved at the price of more involved arguments and calculations. Such improvements seem not too worthy unless geared towards the complete solution of Conjecture 1. Instead, we tried to keep the exposition concise, so that the main points are more visible.

Proof of Proposition 2. It is known that

q(S_{n,k} ) = \frac{1}{2} ( n + 2k − 2 + \sqrt{(n + 2k − 2)^{2} − 8(k^{2} − k)} ) .

Hence, we see that

q(S_{n,k} ) − (n + 2k − 2) = −\frac{4(k^{2} − k)}{n + 2k − 2 + \sqrt{(n + 2k − 2)^{2} − 8(k^{2} − k)}}

> −\frac{2(k^{2} − k)}{n + 2k − 3} ,

and also

q(S_{n,k} ) − (n + 2k − 2) < −\frac{2(k^{2} − k)}{n + 2k − 2} .

To bound q(S_{n,k}^{+} ) let x = (x_{1}, …, x_{n}) be a unit eigenvector to q(S_{n,k}^{+} ) and let x_{1}, …, x_{k} be the entries corresponding to the vertices of degree n − 1 in S_{n,k}^{+} . Let k+1 and k+2 be the vertices of the extra edge of S_{n,k}^{+} . By symmetry, x_{1} = ⋯= x_{k} and x_{k+1} = x_{k+2} . Using the eigenequations for Q(G) and the fact that

q(S_{n,k}^{+} ) > q(S_{n,k} ) > n + 2k − 2 − \frac{2(k^{2} − k)}{n + 2k − 3} > n + k − 1,

we see that

x_{k+1}^{2} = \frac{k^{2}x_{1}^{2}}{(q(S_{n,k}^{+} ) − k − 2)^{2}} < \frac{k}{(q(S_{n,k} ) − k − 2)^{2}} < \frac{k}{(n − 3)^{2}} .

Next, comparing the quadratic forms ⟨Q(S_{n,k}^{+} )x, x⟩ and ⟨Q(S_{n,k} )x, x⟩ of the matrices Q(S_{n,k}^{+} ) and Q(S_{n,k} ), we see that

q(S_{n,k}^{+} ) − (x_{k+1} + x_{k+2} )^{2} = ⟨Q(S_{n,k}^{+} )x, x⟩ − (x_{k+1} + x_{k+2} )^{2}
= ⟨Q(S_{n,k} )x, x⟩ ⩽ q(S_{n,k} ).

Thus, after some algebra, we get

q(S_{n,k}^{+} ) < q(S_{n,k} ) + \frac{4k}{(n − 3)^{2}} < n + 2k − 2 − \frac{2(k^{2} − k)}{n + 2k − 2} + \frac{4k}{(n − 3)^{2}}

< n + 2k − 2 − \frac{2(k^{2} − k)}{n + 2k + 2} ,

completing the proof of Proposition 2. □

Proof of Lemma 5. Let H be a component of G. Set m = v(H) and assume that m ≠ 2k. We shall show that e(H) < (k − 1)m. If m ⩽ 2k − 1, then

e(H) ⩽ \binom{m}{2} = \frac{m(m − 1)}{2} ⩽ (k − 1)m,

as claimed. If m ⩾ 2k + 1, then clause (ii) of Theorem 12 implies that e(H) is at most

max\{ (k − 1)m − ((k − 1)^{2} + (k − 1))/2 + 1, \binom{2k − 1}{2} + (m − 2k − 1)\} .

This bound splits into

e(H) ⩽ (k − 1)m − ((k − 1)^{2} + (k − 1))/2 + 1 ⩽ (k − 1)m,

and

e(H) ⩽ \binom{2k − 1}{2} + (m − 2k + 1) = (2k − 1)(k − 2) + m ⩽ (k − 1)m.

Thus, in all cases we see that e(H) ⩽ (k − 1)m, completing the proof of Lemma 5.

□

Proof of Lemma 6. Assume for a contradiction that

2e(G) − d_{v} ⩾ (2k − 1)(n − 1) + 1,

and that G has no path of order 2k+1 with both endvertices different from v. Write H for the component containing v and let F be the union of the other components of G. Since P_{2k+1} ⊈ F, Theorem 10 implies that

(2)  2e(F) ⩽ (2k − 1)v(F),

and so

2e(H) − d_{v} ⩾ (2k − 1)(v(H) − 1) + 1.

Noting that

2e(H) − d_{v} = ∑_{u∈V (H)∖{v}} d_{u} ⩽ (v(H) − 1)^{2},

we find that v(H) ⩾ 2k + 1. Assume that v(H) ⩾ 2k + 2. Since

2e(H) ⩾ (2k − 1)(v(H) − 1) + 1 + d_{v} > (2k − 1)(v(H) − 1),

Theorem 11 implies that H contains a cycle C of order m ⩾ 2k. If m ⩾ 2k +1, then obviously there is a P_{2k+1} with both endvertices different from v, so let m = 2k. Choose a vertex w ∈ V (H) such that w ≠ v and w ∉ C. There exists a shortest path P joining w to a vertex u ∈ C. By symmetry, we can index the vertices of C as u = u_{1}, u_{2}, …, u_{2k}. Take u_{0} in P at distance 1 from C. Then the sequences u_{0}, u_{1}, u_{2}, …, u_{2k} and u_{0}, u_{1}, u_{2k}, …, u_{2} induce paths of order 2k +1. Since v must be an endvertex to each of them, we see that u_{0} = v. But w ≠ v, hence P contains a vertex u_{−1} at distance 2 from C. Now the sequence u_{−1} , u_{0}, u_{1}, u_{2}, …, u_{2k−1} induces a path of order 2k+1 with both endvertices different from v, a contradiction completing the proof whenever v(H) ⩾ 2k + 2. It remains to consider the case v(H) = 2k + 1. In this case H is not Hamiltonian, as otherwise there is a path of order 2k + 1 with both endvertices different from v; hence, Theorem 13 implies that e(H) ⩽ k(2k − 1) + 1 and so

2k(2k − 1) + 2 − d_{v} ⩾ e(H) − d_{v} ⩾ (2k − 1)2k + 1.

This is possible only if d_{u} = 1 and e(H) = k(2k − 1) + 1. Since H − v is complete, obviously, H = K_{2k} + v. In addition, in (2) we have 2e(F) = (2k − 1)v(F), and so the condition for equality in Theorem 10 implies that G is a union of several copies of K_{2k} and one copy of K_{2k} + v, completing the proof of Lemma 6. □

Proof of Lemma 7. Let q := q(G); assume for a contradiction that q ⩾ n + 2k − 2, and let x = (x_{1}, …, x_{n}) be a unit eigenvector to q. From the eigenequation for Q(G) and the vertex w we see that

(q − n + 1)x_{w} ⩽ (q − d_{w})x_{w} ⩽ ∑_{i∈V (G)∖\{w\}} x_{i} ⩽ \sqrt{(n − 1)(1 − x_{w}^{2})} ,

and in view of q ⩾ n + 2k − 2, it follows that

(3)  x_{w}^{2} ⩽ \frac{n − 1}{(q − n + 1)^{2} + n − 1} < \frac{n − 1}{n − 1 + (2k − 1)^{2}} ⩽ 1 − \frac{9}{n + 8} .

On the other hand, let u ∈ V (F) be such that x_{u} = max{x_{v} : v ∈ V (F)}. Set x := x_{u} and note that the eigenequation for u implies that

qx = d_{u}x + ∑_{i∼u} x_{i} = d_{u}x + x_{w} + ∑_{{i,u}∈E(F)} x_{i}
⩽ 2kx + x_{w} + (2k − 1)x = (4k − 1)x + x_{w}.

Hence, the inequality q ⩾ n + 2k − 2 implies that x ⩽ \frac{x_{w}}{q−4k−1} ⩽ \frac{x_{w}}{n−2k−1} . Next, expanding the quadratic form ⟨Q(G)x, x⟩, we find that

q = ∑_{\{i,j\}∈E(G)} (x_{i} + x_{j})^{2} ⩽ ∑_{\{i,j\}∈E(G_{0} )} (x_{i} + x_{j})^{2} + 2kp(x + x_{w})^{2} + 4p\binom{2k}{2} x^{2}

⩽ q(G_{0}) + 2kp(x + x_{w})^{2} + 4pk(2k − 1)x^{2}

= q(G_{0}) + 2pkx_{w}^{2} + 4pkxx_{w} + 2pk(4k − 1)x^{2}

⩽ q(G_{0}) + 2pk ( 1 + \frac{2}{n − 2k − 1} + \frac{4k − 1}{(n − 2k − 1)^{2}} ) x_{w}^{2}.

Now, plugging here the bound (3), we get

(4)  q ⩽ q(G_{0}) + 2pk ( 1 + \frac{3}{n − 2k − 1} ) ( 1 − \frac{9}{n + 8} )

⩽ q(G_{0}) + 2pk + 6pk ( \frac{1}{n − 2k − 1} − \frac{3}{n + 8} )

= q(G_{0}) + 2pk − 6pk ( \frac{2n − 6k − 13}{(n − 2k − 1)(n + 8)} ) .

Note that, in view of n ⩾ 6k + 13 and k ⩾ 2, we have

\frac{2n − 6k − 13}{(n − 2k − 1)(n + 8)} ⩾ \frac{n}{(n − 2k − 1)(n + 8)} ⩾ \frac{n}{(n − 5)(n + 8)} > \frac{1}{n + 3} .

Plugging this inequality back in (4) and using (1), we obtain

n + 2k − 2 ⩽ q ⩽ q(G_{0}) + 2pk − \frac{6pk}{n + 3}

⩽ m + 2k − 2 + \frac{6pk}{n + 3} + 2pk − \frac{6pk}{n + 3} = n + 2k − 2.

Hence q ⩽ n + 2k − 2, with equality holding if and only if equality holds in (1). The proof of Lemma 7 is completed. □

Proof of Corollary 8. We shall apply Lemma 7 with H = K_{2k+2} and F = pK_{2k}. Clearly 2pk = n − 2k − 2 and so

q(H) = q(K_{2k+2} ) = 4k + 2 < v(H) + 2k − 2 + \frac{3(n − 2k − 2)}{n + 3}

= v(H) + 2k − 2 + \frac{6kp}{n + 3} .

In the derivation above we use that the inequality n ⩾ 6k + 13 implies that 3n − 6k − 6 > 2(n + 3). The conditions for Lemma 7 are met and so q(G) < n + 2k − 2, completing the proof of Corollary 8. □

Proof of Corollary 9. Let F be the union of all components of G − w having order exactly 2k, and let p be their number, possibly zero. Let H be the graph induced by the vertices in V (G) ∖ V (F). Note that the hypothesis of Corollary 9 implies that e(H − w) ⩽ (k − 1)(m − 1) and so

e(H) ⩽ e(H − w) + m − 1 ⩽ (k − 1)(m − 1) + m − 1 = k(m − 1).

Now, from Theorem 16 we get

(5)  q(H) ⩽ \frac{2e(H)}{m − 1} + m − 2 ⩽ \frac{2k(m − 1)}{m − 1} + m − 2

= v(H) + 2k − 2 ⩽ v(H) + 2k − 2 + \frac{6kp}{n + 3} .

Since n ⩾ 6k + 13, we can apply Lemma 7, obtaining

q(G) < n + 2k − 2,

unless equality holds in (5). Equality in (5) implies that p = 0, that is to say G = H. Also, by the condition for equality in Theorem 16, we see that G is either complete, or is a star, or is a complete graph with one isolated vertex. Since q(G) = n+2k−2, G cannot be a star. If G is complete, then n+2k−2 = 2n−2 and so n = 2k, contradicting that n ⩾ 6k + 13. For the same reason n + 2k − 2 < 2n − 4 and so G cannot be a complete graph with one isolated vertex either. Corollary 9 is proved. □

Proof of Theorem 3. For short, set q := q(G) and V := V (G). Assume for a contradiction that G is a graph of order n > 6k^{2}, with q ⩾ n + 2k − 2, and suppose that C_{2k+1} ⊈ G or C_{2k+2} ⊈ G. We may and shall suppose that G is edge maximal, because edge addition does not decrease the Q-index. In particular, this assumption implies that G is connected.

Let w be a vertex for which the expression

d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i}

is maximal. We shall show that

(6)  d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i} ⩽ n + 2k − 2.

This is enough to prove Theorem 3, unless

q = d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i}.

However, G is connected, so if equality holds in (6) Theorem 15 implies that G is regular or bipartite semiregular; it is not hard to see that neither of these conditions can hold. Indeed, if G is bipartite, then q ⩽ n. If G is regular, then q = 2δ ⩽ n, as otherwise, Bondy’s theorem [2] implies that G is pancyclic. So to the end of the proof we shall focus on the proof of (6).

For short, set A = Γ_{w}, B = V (G) ∖ (Γ_{w} ∪ {w}), and G_{w} = G[V ∖ {w}]. Obviously, |A| = d_{w} and |A| + |B| = n − 1. First we shall prove that C_{2k+1} ⊂ G. Assume thus that C_{2k+1} ⊈ G; clearly P_{2k} ⊈ G[A], and so Theorem 10 implies that e(A) ⩽ (k − 1)|A|. Now

d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i} = |A| + 1 + \frac{2e(A) + e(A, B)}{|A|} ⩽ |A| + 1 + \frac{2(k − 1)|A| + |A||B|}{|A|}
⩽ |A| + 1 + 2k − 2 + |B| = n + 2k − 2.

This completes the proof that C_{2k+1} ⊂ G. The proof that C_{2k+2} ⊂ G is somewhat longer. Assume that C_{2k+2} ⊈ G and note that if d_{w} ⩽ 2k − 1, then

d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i} = d_{w} + Δ ⩽ 2k − 1 + n − 1 = n + 2k − 2,

so (6) holds. Thus, hereafter we shall assume that d_{w} ⩾ 2k. Further, note that the graph G_{w} contains no path with both endvertices in A, as otherwise C_{2k+2} ⊂ G. Hence, Theorem 14 implies that

2e(A) + e(A, B) ⩽ (2k − 1)|A| + k|B| = (k − 1)d_{w} + k(n − 1),

and therefore

d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i} = d_{w} + 1 + \frac{2e(A) + e(A, B)}{d_{w}}

⩽ d_{w} + 1 + \frac{(k − 1)d_{w} + k(n − 1)}{d_{w}} = d_{w} + k + \frac{k(n − 1)}{d_{w}} .

The function x + k(n − 1)/x is convex for x > 0; hence, the maximum of the expression d_{w} +k(n − 1) /d_{w} is attained for the minimum and maximum admissible values for d_{w}. Since d_{w} ⩾ 2k, in either case we find that

d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i} < n + 2k − 2,

unless d_{w} ⩾ n − 2. Therefore, to complete the proof we only need to consider the cases d_{w} = n − 2 and d_{w} = n − 1. First, suppose that d_{w} = n − 2 and let v be the vertex of G such that v ≠ w and v ∉ Γ_{w}. Note that G_{w} contains no path of order 2k + 1 with both endvertices different from v, as such a path would make a C_{2k+2} with w. Therefore, the hypothesis of Lemma 6 is satisfied, and so either

(7)  2e(A) + e(A, B) = 2e(G_{w}) − d_{v} ⩽ (2k − 1)(n − 2)

or G_{w} is a union of several copies of K_{2k} and one K_{2k} + v. If (7) holds, we see that

d_{w} + \frac{1}{d_{w}} ∑_{i∼w} d_{i} ⩽ n − 2 + 1 + \frac{2e(A) + e(A, B)}{n − 2}

⩽ n − 1 + \frac{(2k − 1)(n − 2)}{(n − 2)} = n + 2k − 2,

completing the proof of (6). On the other hand, if G_{w} is a union of several copies of K_{2k} and one K_{2k} + v, then G is a spanning subgraph of the graph G′ = K_{1} ∨ ((pK_{2k}) ∪ K_{2k+1} ), with p chosen so that n = 2(p + 1)k + 2. Since n ⩾ 6k^{2} + 1 ⩾ 6k + 13, we can apply Corollary 8 obtaining that

q(G) < q(G′) < n + 2k − 2,

which contradicts the assumption and completes the proof of Theorem 3 if d_{w} = n − 2.

Finally, let d_{w} = n − 1. Since G_{w} contains no P_{2k+1} , Lemma 5 implies that for each component C of G_{w}, either v(C) = 2k or e(C) ⩽ (k − 1)v(C). Since n ⩾ 6k^{2} + 1 ⩾ 6k + 13, the graph G satisfies the hypothesis of Corollary 9, and so

q(G) < n + 2k − 2,

completing the proof of Theorem 3. □

Acknowledgement. Thanks are due to the referee for helpful suggestions.

References

1. P. N. Balister, E. Győri, J. Lehel, R. H. Schelp, Connected graphs without long paths, Discrete Math. 308 (2008), 4487–4494.

2. B. Bollobás, Modern Graph Theory, Grad. Texts Math. 184, Springer-Verlag, New York, 1998.

3. J. Bondy, Pancyclic graphs I, J. Combin. Ser. B 11 (1971), 80–84.

4. J. A. Bondy, U. S. R. Murty, Graph Theory, Grad. Texts Math. 244, Springer-Verlag, New York, 2008.

5. D. Cvetković, Spectral theory of graphs based on the signless Laplacian, Research Report, (2010), available at: http://www.mi.sanu.ac.rs/projects/signless_L_reportApr11.pdf.

6. K. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285 (2004), 57–66.

7. P. Erdős, T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar 10 (1959), 337–356.

8. L. Feng, G. Yu, On three conjectures involving the signless laplacian spectral radius of graphs, Publ. Inst. Math., Nouv. Sér. 85 (2009), 35–38.

9. M. A. A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q-index: forbidden 4-cycle and 5-cycle, Electron. J. Linear Algebra 26 (2013), 905–916.

10. G. N. Kopylov, On maximal paths and cycles in a graph, Soviet Math. Dokl. 18 (1977), 593– 596.

11. R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 295 (1998), 33–35.

12. V. Nikiforov, Degree powers in graphs with a forbidden even cycle, Electron. J. Combin. 15 (2009), R107.

13. O. Ore, Note on Hamilton circuits, Am. Math. Monthly 67 (1960), 55.

Department of Mathematical Sciences (Received 03 10 2013) University of Memphis (Revised 13 02 2014) Memphis, TN 38152 USA

   vnikifrv@memphis.edu