✦ LIBER ✦

The Wiener polynomial of a graph

✍ Scribed by Bruce E. Sagan; Yeong-Nan Yeh; Ping Zhang

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 674 KB
Volume: 60
Category: Article
ISSN: 0020-7608
DOI: 10.1002/(sici)1097-461x(1996)60:5<959::aid-qua2>3.0.co;2-w

No coin nor oath required. For personal study only.

✦ Synopsis

The Wiener index is a graphical invariant that has found extensive application in chemistry. We define a generating function, which we call the Wiener polynomial, whose derivative is a q-analog of the Wiener index. We study some of the elementary properties of this polynomial and compute it for some common graphs. We then find a formula for the Wiener polynomial of a dendrimer, a certain highly regular tree of interest to chemists, and show that it is unimodal. Finally, we point out a connection with the Poincar6 polynomial of a finite Coxeter group. 0 1996 John Wiley & Sons, Inc.

the boiling point of paraffin. Since then, the index has been shown to correlate with a host of other properties of molecules (viewed as graphs). For more information about the Wiener index in chemistry and mathematics, see [2, 31, respectively.

We wish to define and study a related generating function. If q is a parameter, then the Wiener polynomial of G is et d ( u , v ) denote the distance between ver-L tices u and v in a graph G. Throughout this article, we assume that G is connected. The Wiener index of G is defined as

. Introduction and Elementary Properties

where the sum is over all unordered pairs { u , v} of distinct vertices in G. The Wiener index was first proposed by Wiener [l] as an aid to determining where the sum is taken over the same set of pairs as before. It is easy to see that the derivative of W(G; q ) is a q-analog of W(G) (see Theorem 1.1, number 5). In the rest of this section, we derive

📜 SIMILAR VOLUMES

On Wiener-type polynomials of thorn grap

On Wiener-type polynomials of thorn graphs

✍ Bo Zhou; Damir Vukičević 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract We derive the expressions of the ordinary, the vertex‐weighted and the doubly vertex‐weighted Wiener polynomials of a type of thorn graph, for which the number of pendant edges attached to any vertex of the underlying parent graph is a linear function of its degree. We also define varia

A Wiener Theorem for Orthogonal Polynomi

A Wiener Theorem for Orthogonal Polynomials

✍ V. Hosel; R. Lasser 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 202 KB

A well-known theorem by \(\mathrm{N}\). Wiener characterizes the discrete part of a complex Borel measure \(\mu \in \mathbf{M}(T)\) on the torus group \(T\). In this note an analoguous result is presented for orthonormal polynomial sequences \(\left(p_{n}\right)_{n \in n_{0}}\). For Jacobi polynomia

Tension polynomials of graphs

✍ Martin Kochol 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

The tension polynomial F G (k) of a graph G, evaluating the number of nowhere-zero Z k -tensions in G, is the nontrivial divisor of the chromatic polynomial G (k) of G, in that G (k) ¼ k c(G) F G (k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial I G

Graph Ramsey Theory and the Polynomial H

Graph Ramsey Theory and the Polynomial Hierarchy

✍ Marcus Schaefer 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 402 KB

In the Ramsey theory of graphs F Ä (G, H) means that for every way of coloring the edges of F red and blue F will contain either a red G or a blue H. Arrowing, the problem of deciding whether F Ä (G, H), lies in 6 p 2 =coNP NP and it was shown to be coNP-hard by Burr [Bur90]. We prove that Arrowing

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

On the Multiplicities of the Primitive I

On the Multiplicities of the Primitive Idempotents of a Q-Polynomial Distance-regular Graph

✍ Arlene A Pascasio 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 154 KB

and Terwilliger recently introduced the notion of a tridiagonal pair. We apply their results to distance-regular graphs and obtain the following theorem. THEOREM. Let denote a distance-regular graph with diameter D ≥ 3. Suppose is Q-polynomial with respect to the ordering E 0 , E 1 , . . . , E D of