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.     

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 roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

Four new sums of graphs and their Wiener indices

The Wiener index is the sum of distances between all vertex pairs in a connected graph. This notion was motivated by various mathematical properties and chemical applications. In this paper we introduce four new operations on graphs and study the Wiener indices of the resulting graphs.     

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.     

欧拉图的hyper-Wiener指标

ε_n表示n个顶点欧拉图的集合.通过对欧拉图hyper-Wiener指标性质的研究,刻画了ε_n中具有最小和最大hyper-Wiener指标的极图.     

图的Hyper-Wiener指数的综述(英文)

设G是一个图.G的顶点u和v的距离是u和v之间最短路的长度.Wiener指数是G中所有无序顶点对之间距离之和,而Hyper-Wiener指数定义为WW(G)=?∑u,v∈V(G)d(u,v)+?∑u,v∈V(G)d2(u,v),式中的和取遍G的所有顶点对.本文总结了图的Hyper-Wiener指数的最近结论.     

The Wiener maximum quadratic assignment problem

We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one-dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP-hard in the ordinary sense and solvable in pseudo-polynomial time.Our approach also yields a polynomial time solution for the following problem from chemical graph theory: find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature.     

Reciprocal complementary Wiener numbers of trees, unicyclic graphs and bicyclic graphs

The reciprocal complementary Wiener number of a connected graph G is defined as

where V(G) is the vertex set, d(u,v|G) is the distance between vertices u and v, d is the diameter of G. We determine the trees with the smallest, the second smallest and the third smallest reciprocal complementary Wiener numbers, and the unicyclic and bicyclic graphs with the smallest and the second smallest reciprocal complementary Wiener numbers.     

On the Reverse Wiener Indices of Unicyclic Graphs

We determine the maximum values of the reverse Wiener indices of the unicyclic graphs with given cycle length, number of pendent vertices and maximum degree, respectively, and characterize the extremal graphs. We also determine the unicyclic graphs of given cycle length and diameter with minimum Wiener index.      

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

A Class of Trees and its Wiener Index

In this paper, we will consider the Wiener index for a class of trees that is connected to partitions of integers. Our main theorem is the fact that every integer is the Wiener index of a member of this class. As a consequence, this proves a conjecture of Lepović and Gutman. The paper also contains extremal and average results on the Wiener index of the studied class.This work was supported by Austrian Science Fund project no. S-8307-MAT.     

A problem of Földes and Puri on the Wiener process

Let be a real-valued Wiener process starting from 0, and be the right-continuous inverse process of its local time at 0. Földes and Puri [3] raise the problem of studying the almost sure asymptotic behavior of as tends to infinity, i.e. they ask: how long does stay in a tube before ``crossing very much" a given level? In this note, both limsup and liminf laws of the iterated logarithm are provided for .

     

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.