✦ LIBER ✦

Polynomials on graphs

✍ Scribed by Paul M. Weichsel

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 462 KB
Volume: 93
Category: Article
ISSN: 0024-3795
DOI: 10.1016/s0024-3795(87)90323-5

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple graph with adjacency matrix A, and p(x) a polynomial with rational coefficients. If p(A) is the adjacency matrix of a graph, we denote that graph by p(G). We consider the question: Given a graph 6, which polynomials p(r) give rise to a graph p(G) and what are those graphs? We give a complete answer if G is a distance-regular graph. We then derive some general relations between the polynomials p(x), the spectrum of A, and the automorphism group of G.

📜 SIMILAR VOLUMES

Polynomial approximation on graphs

✍ A. G. O'Farrell; K. J. Preskenis; D. Walsh 📂 Article 📅 1983 🏛 Springer 🌐 English ⚖ 341 KB

On color polynomials of Fibonacci graphs

✍ Sherif El-Basil 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB

On color polynomials of Fibonacci graphs

✍ Sherif El-Basil 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB

A recursion exists among the coefficients of the color polynomials of some of the families of graphs considered in recent work of Balasubramanian and Ramaraj.' Such families of graphs have been called Fibonacci graphs. Application to king patterns of lattices is given. The method described here appl

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 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

Walks on Directed Graphs and Matrix Poly

Walks on Directed Graphs and Matrix Polynomials

✍ Miguel A. Méndez 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 166 KB

We give a matrix generalization of the family of exponential polynomials in one variable , k (x). Our generalization consists of a matrix of polynomials 8 k (X)= (8 (k) i, j (X)) n i, j=1 depending on a matrix of variables X=(x i, j ) n i, j=1 . We prove some identities of the matrix exponential pol