A Class of Trees and its Wiener Index
- PDF / 322,447 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 65 Downloads / 173 Views
A Class of Trees and its Wiener Index Stephan G. Wagner
Received: 20 October 2004 / Accepted: 6 February 2006 # Springer 2006
Abstract 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 470 is the Wiener index of a member of this class. As a consequence, this proves a conjecture of Lepovic´ and Gutman. The paper also contains extremal and average results on the Wiener index of the studied class. Keywords trees . partitions . Wiener index Mathematics Subject Classifications (2000) 05C12 . 05C05
1. Introduction Let G denote a simple, connected tree. Throughout this paper, we will use the graph-theoretical notation from [1]. The Wiener index of G is defined by X dG ðu; vÞ; ð1Þ WðGÞ ¼ fu;vgVðGÞ
jVðGÞj
where dG ðu; vÞ denotes the distance of u and v. Obviously, WðGÞ= 2 gives the average distance between the vertices of G. It was first studied by Harold Wiener in 1947 for acyclic molecular graphs G. The Wiener index is one of the most popular topological indices in combinatorial chemistry. There is a lot of mathematical and chemical literature on the Wiener index, especially on the Wiener index of trees – [2] gives a summary of known results and open problems and conjectures. One major problem for many topological indices is the so-called Binverse’’ problem, i.e., finding a graph from a certain class given its index.
This work was supported by Austrian Science Fund project no. S-8307-MAT. S. G. Wagner ()) Department of Mathematics, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria e-mail: [email protected] Springer
120
Acta Appl Math (2006) 91: 119–132
A conjecture of Lepovic´ and Gutman [6] states that there is some bound M such that for all w M there is a tree T of Wiener index WðTÞ ¼ w. The proof of their conjecture will be the main result of this paper. To prove our result, we investigate a class of trees we will call Bstar-like.’’ It is the class of all trees with diameter 4. However, there is another class of trees – the trees with only one vertex of degree > 2 – that is also called Bstar-like’’ in some papers, e.g., [3]. The star-like trees of this paper have been studied in [5] for another topological index, and they turned out to be quite useful in that context. Here, we will even be able to give an easy and explicit construction of a tree T, given its Wiener index WðTÞ. In the second section, we will develop the necessary preliminaries for our theorems. The third section deals with an extremal result – we will characterize the star-like tree of maximal Wiener index. Section 4 will contain the proof of our main result. The last chapter is devoted to the asymptotical analysis of the Wiener index of star-like trees.
2. Preliminaries
DEFINITION 1. Let ðc1 ; . . . ; cd Þ be a partition of n. The star-like tree assigned to this partition is the tree v 2 v 1
v
where v1 ; . . . ; vd have degree c1 ; . . . ; cd respectively. It has exactly n edges. The
Data Loading...
