Article ID Journal Published Year Pages File Type
419941 Discrete Applied Mathematics 2013 5 Pages PDF
Abstract

The revised Szeged index of a graph GG is defined as Sz∗(G)=∑e=uv∈E(nu(e)+n0(e)/2)(nv(e)+n0(e)/2)Sz∗(G)=∑e=uv∈E(nu(e)+n0(e)/2)(nv(e)+n0(e)/2), where nu(e)nu(e) and nv(e)nv(e) are, respectively, the number of vertices of GG lying closer to vertex uu than to vertex vv and the number of vertices of GG lying closer to vertex vv than to vertex uu, and n0(e)n0(e) is the number of vertices equidistant to uu and vv. Hansen et al. used the AutoGraphiX and made the following conjecture about the revised Szeged index for a connected bicyclic graph GG of order n≥6n≥6: Sz∗(G)≤{(n3+n2−n−1)/4,if  n  is odd ,(n3+n2−n)/4,if  n  is even . with equality if and only if GG is the graph obtained from the cycle Cn−1Cn−1 by duplicating a single vertex. This paper is to give a confirmative proof to this conjecture.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,