2017arXiv (Cornell University)Open access

On inverse Wiener interval problem of trees

Jelena Sedlar

Open full text 0 citations

Abstract

The Wiener index W(G) of a simple connected graph G is defined as the sum of distances over all pairs of vertices in a graph. We denote by W[T_{n}] the set of all values of Wiener index for a graph from class T_{n} of trees on n vertices. The largest interval of contiguous integers (contiguous even integers in case of odd n) is denoted by W^{int}[T_{n}]. In this paper we prove that both sets are of the cardinality (1/6)n^3+O(n^2) in the case of even n, while in the case of odd n we prove that the cardinality of both sets equals (1/(12))n^3+O(n^2) solving thus two conjectures posed in literature.

Open-access reader

About this research paper

What this paper is about

The Wiener index W(G) of a simple connected graph G is defined as the sum of distances over all pairs of vertices in a graph. We denote by W[T_{n}] the set of all values of Wiener index for a graph from class T_{n} of trees on n vertices. The largest interval of contiguous integers (contiguous even integers in case of odd n) is denoted by W^{int}[T_{n}]. In this paper we prove that both sets are of the cardinality (1/6)n^3+O(n^2) in the case of even n, while in the case of odd n we prove that the cardinality of both sets equals (1/(12))n^3+O(n^2) solving thus two conjectures posed in literature.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

The Wiener index W(G) of a simple connected graph G is defined as the sum of distances over all pairs of vertices in a graph. We denote by W[T_{n}] the set of all values of Wiener index for a graph from class T_{n} of trees on n vertices. The largest interval of contiguous integers (contiguous even integers in case of odd n) is denoted by W^{int}[T_{n}]. In this paper we prove that both sets are of the cardinality (1/6)n^3+O(n^2) in the case of even n, while in the case of odd n we prove that the cardinality of both sets equals (1/(12))n^3+O(n^2) solving thus two conjectures posed in literature.

Key concepts: Interval (graph theory), Inverse, Mathematics, Tree (set theory), Applied mathematics, Combinatorics, Geometry

Related papers

Back to paper searchBrowse research topicsOriginal source
On inverse Wiener interval problem of trees — Research Paper | ScholarLens