Szeged index, edge Szeged index, and semi-star trees

A semi-star tree is a star tree whose some edges may be replaced by paths of length more than one. In this paper we present some increasing and decreasing transformations for Szeged index of the semi-star trees. Then we introduce palm semi-star tree and uniform semi-star tree and show that they are extremal with respect to the Szeged index and edge Szeged index. In addition, we investigate the relation between the Szeged index and edge Szeged index for all trees.     

Estimating the Szeged index

Lower and upper bounds on Szeged index of connected (molecular) graphs are established as well as Nordhaus–Gaddum-type results, relating the Szeged index of a graph and of its complement.     

Use of the Szeged index and the revised Szeged index for measuring network bipartivity

We have revisited the Szeged index (Sz) and the revised Szeged index (Sz^∗), both of which represent a generalization of the Wiener number to cyclic structures. Unexpectedly we found that the quotient of the two indices offers a novel measure for characterization of the degree of bipartivity of networks, that is, offers a measure of the departure of a network, or a graph, from bipartite networks or bipartite graphs, respectively. This is because the two indices assume the same values for bipartite graphs and different values for non-bipartite graphs. We have proposed therefore the quotient Sz/Sz^∗ as a measure of bipartivity. In this note we report on some properties of the revised Szeged index and the quotient Sz/Sz^∗ illustrated on a number of smaller graphs as models of networks.     

Calculating the edge Wiener and edge Szeged indices of graphs

The edge Szeged and edge Wiener indices of graphs are new topological indices presented very recently. It is not difficult to apply a modification of the well-known cut method to compute the edge Szeged and edge Wiener indices of hexagonal systems. The aim of this paper is to propose a method for computing these indices for general graphs under some additional assumptions.     

On the differences between Szeged and Wiener indices of graphs

Let G be a connected graph and η(G)=Sz(G)−W(G), where W(G) and Sz(G) are the Wiener and Szeged indices of G, respectively. A well-known result of Klav?ar, Rajapakse, and Gutman states that η(G)≥0, and by a result of Dobrynin and Gutman η(G)=0 if and only if each block of G is complete. In this paper, a path-edge matrix for the graph G is presented by which it is possible to classify the graphs in which η(G)=2. It is also proved that there is no graph G with the property that η(G)=1 or η(G)=3. Finally, it is proved that, for a given positive integer k,k≠1,3, there exists a graph G with η(G)=k.     

On the edge Szeged index of bridge graphs

In this Note, we introduce a formula for the edge Szeged index of bridge graphs. Using this formula, the edge Szeged indices of several graphs are computed.     

Equiseparability on terminal Wiener index

The aim of this work is to explore the properties of the terminal Wiener index, which was recently proposed by Gutman et al. (2004) [3], and to show the fact that there exist pairs of trees and chemical trees which cannot be distinguished by using it. We give some general methods for constructing equiseparable pairs and compare the methods with the case for the Wiener index. More specifically, we show that the terminal Wiener index is degenerate to some extent.     

On the Wiener index of random trees

By a theorem of Janson, the Wiener index of a random tree from a simply generated family of trees converges in distribution to a limit law that can be described in terms of the Brownian excursion. The family of unlabelled trees (rooted or unrooted), which is perhaps the most natural one from a graph-theoretical point of view, since isomorphisms are taken into account, is not covered directly by this theorem though. The aim of this paper is to show how one can prove the same limit law for unlabelled trees by means of generating functions and the method of moments.     

Remarks on the Wiener index of unicyclic graphs

Unicyclic graphs are connected graphs with the same number of vertices and edges. Tang and Deng (J. Math. Chem. 43:60–74, 2008) considered the problem of classification of all unicyclic graphs with the first three smallest and largest Wiener indices. In this paper, by construction of some classes of unicyclic graphs, the classification of unicyclic graphs with the first three maximum and minimum Wiener indices is completed.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.