- Email: [email protected]

Maximum values of Szeged index and edge-Szeged index of graphs Ehsan Chiniforooshan Department of Computer Science and Software Engineering, Concordia University, Montreal, Quebec H3G 1M8, Canada. E-mail address:[email protected]

Baoyindureng Wu College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, P.R. China. E-mail address:[email protected]

Abstract The Szeged index is a graph invariant which is a natural generalization of Wiener index. In this note, we disprove two recent conjectures concerning with the maximum value of Szeged index of graphs, which are due to Khalifeh et al. (Europ. J. Combinatorics (2008), doi:10.1016/j.ejc.2008.09.019) and respectively, to Gutman et al. (Groat. Chem. Acta 81(2)(2008) 263-266) and prove a conjecture on Szeged index due to Klavzar et al. ( Appl. Math. Lett. 9(1996), 45-49), which states that the complete bipartite graph K n2 , n2 has maximum Szeged index among all connected graphs on n vertices. The last conjecture is previously proved by Dobrynin (Croat. Chem. Acta 70(3), 819-825), but our proof turns out to be much simpler and self-contained. Keywords: Szeged index, Wiener index

1

Introduction

All graphs considered here are ﬁnite, undirected and simple. We refer to [4] for unexplained terminology and notations. Let G = (V (G), E(G)) be a graph. 1

Supported by Canada Research Chair Program

1571-0653/$ – see front matter Crown Copyright © 2009 Published by Elsevier B.V. All rights reserved. doi:10.1016/j.endm.2009.07.067

406

E. Chiniforooshan, B. Wu / Electronic Notes in Discrete Mathematics 34 (2009) 405–409

|V (G)| and |E(G)| are called the order and the size of G, respectively. Let v be a vertex of G. The degree of v, denoted by dG (v), is the number of edges incident with v in G. The minimum degree δ(G) of G is min{d(v) : v ∈ V (G)}. The distance dG (u, v) of two vertices u, v ∈ V (G) is the length of shortest path connecting u and v in G. If there is no confusion, we simply use d(v) and d(u, v) instead of dG (v) and dG (u, v), respectively. We denote Nu (v) = {w ∈ V (G) : d(w, v) < d(w, u)}, namely, the set of vertices which are in a position closer to u than v in G. Let nu (v) = |Nu (v)|. Wiener index, W (G), of a connected graph G is W (G) = u,v∈V (G) d(u, v). We refer to [3] for theory and applications of Wiener index. As a generalization of Wiener index, Szeged index was put forward by Gutman [5]: Sz (G) =

nu (v)nv (u).

uv∈E(G)

For more about the Szeged index, readers are referred to [6] and [4]. The authors of [9] proposed: Conjecture 1.1 ([9]) The complete bipartite graph K n2 , n2 has maximum Szeged index among all connected graphs with n vertices. This conjecture is proved by Dobrynin [2]. His proof is based on two known theorems on the number of triangles in a connected graph, one of which is due to Bollobas [1], and the other is due to Nikiforov and Khadzhiivannov [11], independently, to Lovasz and Simimonvits [10]. In Section 3, we give much simpler, self-contained proof of this conjecture. Let G be a connected graph of order n and size m. Since nv (u)+nu (v) ≤ n for uv ∈ E(G), one has nv (u)nu (v) ≤ n2 n2 , and thus Sz(G) ≤ 14 n2 m. Khalifeh et al. [8] proved that if Sz(G) = 14 n2 m, then G is bipartite, δ(G) ≥ 2, n is even, and conjectured Conjecture 1.2 ([8]) For a connected graph of order n and size m, Sz(G) = 1 2 n m if and only if G is a bipartite regular graph. 4 We will give a counterexample for this conjecture in Section 2. Very recently Gutman and Ashraﬁ [6] introduced the edge version of Szeged index. Let w ∈ V (G) and e = xy ∈ E(G). Deﬁne the distance d(w, e) between w and e to be min{d(w, x), d(w, y)}, and for an edge uv ∈ E(G), mv (u) counts the number of edges of G whose distance to u is smaller than the distance to

E. Chiniforooshan, B. Wu / Electronic Notes in Discrete Mathematics 34 (2009) 405–409

407

v. Then the edge-Szeged index Sze (G) of G is mv (u)mu (v). Sze (G) = uv∈E(G)

The authors [6] determined the edge-Szeged index of several classes of graphs, for instance, Sze (Kn ) = 12 n(n − 1)(n − 2)2 for complete graph Kn and Sze (Ka,b ) = ab(a − 1)(b − 1) for complete bipartite graph Ka,b , and raised the following conjecture. Conjecture 1.3 ([6]) The complete graph Kn has the greatest edge-Szeged index among all n-vertex graphs. We will give counterexamples for this conjecture in Section 2.

2

Disproof of Conjectures 1.2 and 1.3

Let us start with a useful observation. Let G be a connected graph of order n and size m. As nv (u) + nu (v) ≤ n for any edge uv ∈ E(G), we have nu (v)nv (u) ≤ n2 n2 . It follows that Sz(G) = 14 n2 m if and only if nv (u) = nu (v) = n2 for every edge uv ∈ E(G).

u

v

Figure 1. A counterexample to Conjecture 1.2

The graph given in Figure 1 is a counterexample for Conjecture 1.2, because nv (u) = 8, but nu (v) = 6 and n = 14, which violates the above observation. Note that if G is a bipartite vertex-transitive graph then Sz(G) = 14 n2 m. So, one may expect that for a connected graph of order n and size m, Sz(G) = 1 2 n m if and only if G is a vertex transitive bipartite graph. However, this is 4 not true (consider K5,5 − E(C6 ∪ C4 )). Nevertheless, the following question remains open. Is there a connected non-regular bipartite graph G of order n and size m with Sz(G) = 41 n2 m ? Now we turn our attention to Conjecture 1.3. The following theorem shows that the expected value of Sze (G(n, p)), where G(n, p) denotes a random graph

408

E. Chiniforooshan, B. Wu / Electronic Notes in Discrete Mathematics 34 (2009) 405–409

of order n such that the probability of being an edge between any pair is p, is in Ω(n6 ), for any constant 0 < p < 1. The proof is omitted due to space limitations. Theorem 2.1 The expected edge-Szeged index of G(n, p) is at least n−2 n−4 5 4 2 n . p (1 − p) (2 − p) 2 2 2 Setting p =

√ 25− 185 22

in Theorem 2.1 results in the following corollary.

Corollary 2.2 For large enough integers n, there is an n-vertex graph with edge-Szeged index greater than 552 n6 . 106 There is also a deterministic way to obtain a graph with edge-Szeged index n 6 4 Ω(n ): let Cn be a cycle of length n and Cn be the graph on the vertex set of n Cn such that uv ∈ E(Cn4 ) if and only if dCn (u, v) ≤ n4 . Then, using a routine n

computation, one can see that Sze (Cn4 ) ≥

3

n6 . 3072

Proof of Conjecture 1.1

Theorem 3.1 Let G be a connected graph of order n. Then Sz(G) ≤ ( n2 n2 )2 , with equality if and only if G ∼ = K n2 , n2 . To prove Theorem 3.1, we need some preparation. Let G be connected graph of order n. For a vertex x ∈ V (G), deﬁne F (x) = {uv ∈ E(G) : d(x, u) = d(x, v)} and f (x) = |F (x)|, and for an edge uv ∈ E(G), H(uv) = {x ∈ V (G) : d(x, u) = d(x, v)} and h(uv) = |H(uv)|. It is easy to see that h(uv) ≤ n and f (x) = h(uv). x∈V (G)

uv∈E(G)

Theorem 3.1 follows from Lemma 3.2 and Lemma 3.3 below. The proofs of the following lemmas are easy and ommitted due to space limitation. Lemma 3.2 Let G be connected graph. Then for any vertex x ∈ V (G), n n f (x) ≤ . 2 2 Lemma 3.3 Let G be a connected graph of order n and size m. Then

uv∈E(G)

n n h(uv) h(uv) ≤ ( )2 , 2 2 2 2

E. Chiniforooshan, B. Wu / Electronic Notes in Discrete Mathematics 34 (2009) 405–409

409

with equality if and only if G ∼ = K n2 , n2 . Acknowledgment This paper was written while the second author was visiting Department of computer science and software engineering, Concordia University, Canada. He is very grateful to Prof. Vaˇ sek Chv´ atal for his hospitality. The ﬁnancial support from Chinese Scholarship Council is also appreciated.

References [1] B. Bollobas, Extremal graph theory, London, Academic Press, 1978, pp. 297. [2] A.A. Dobrynin, Graphs having the maximal value of the Szeged index, Croat. Chem. Acta 70(3)(1997), 819-825. [3] AA. Dobrynin, D. Entringer and I. Gutman, Wiener index of trees: theory and applications, A.A. Dobrynin, D. Entringer and I. Gutman, Acta Appl. Math. 66(2001) 211-249. [4] M.V. Diudea, M.S. Florescu, and P.V. Khadikar, Molecular Topology and Its Applications, EﬁCon Press, Bucharest, 2006. [5] I. Gutman, A formula fro the Wiener number of trees and its extension to grahps containing cycles, Graph Theory Notes N. Y. 27(1994), 9-15. [6] I. Gutman and Ali Reza Ashraﬁ, The edge version of the Szeged index, Croat. Chem. Acta 81(2)(2008), 263-266. [7] I. Gutman and A. Dobrynin, The Szeged index—a success story, Graph Theory Notes N. Y. 34(1998), 37-44. [8] M.H. Khalifeh, H. Youseﬁ-Azari, A.R. Ashraﬁ, S.G. Wagner, Some results on distance-based graph invariants, European Journal of Combinatorics (2008), doi:10.1016/j.ejc.2008.09.019. [9] S. Klavzar, A. Rajapake, I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math. Lett. 9(1996), 45-49. [10] L. Lovasz and M. Simonvits, in Studies in pure Math., pp. 459-495, Bikh¨ auser, Basel, 1983. [11] V.S. Nikiforov and N.G. Khadzhiivanov, Solution of the conjecture of P. Erdos on the number of triangles in a graphs with n vertices and [ n2 ] + l edges, C.R. Acad. Bulg. Sci 34(1981) 969-970.