✦ LIBER ✦

A note on Negami's polynomial invariants for graphs

✍ Scribed by James G. Oxley

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 296 KB
Volume: 76
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90326-9

No coin nor oath required. For personal study only.

✦ Synopsis

Negami has introduced two polynomials for graphs and proved a number of properties of them. In this note, it is shown that these polynomials are intimately related to the well-known Tutte polynomial. This fact is used, together with a result of Brylawski, to answer a question of Negami.

The matroid and graph terminology used here will follow Welsh [lo] and Bondy and Murty [l] with the following differences. If M is a matroid, then E(M) and r will denote its ground set and its rank function, respectively. If e is an element of M, then M\e and M/e will denote the deletion and contraction of e from M. The same notation will be used when deleting or contracting an edge from a graph G; the complement of G will be denoted G.

The Tutte polynomial of a matroid M is defined by TT(M; x, y) = 2 (x -l)"-(A'(y _ l)Wl-"A'.

📜 SIMILAR VOLUMES

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

A note on possible extensions of Negami'

A note on possible extensions of Negami's conjecture

✍ Hlin?n�, Petr 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 2 views

A graph H is a cover of a graph G, if there exists a mapping ϕ from V (H) onto V (G) such that for every vertex v of G, ϕ maps the neighbors of v in H bijectively onto the neighbors of ϕ(v) in G. Negami conjectured in 1987 that a connected graph has a finite planar cover if and only if it embeds in

A Note on Polynomial Reduction

✍ Alyson Reeves; Bernd Sturmfels 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 137 KB

The reduction relation modulo a marked set of polynomials is Noetherian if and only if the marking is induced from an admissible term order.

A note on polynomial maps

✍ Ram Karan; L.R. Vermani 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 293 KB

Note on Choudum's “chromatic bounds for

Note on Choudum's “chromatic bounds for a class of graphs”

✍ Medha Javdekar 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract If a graph __G__ has no induced subgraph isomorphic to __K__~1,3′~ __K__~5~‐__e__, or a third graph that can be selected from two specific graphs, then the chromatic number of __G__ is either __d__ or __d__ + 1, where __d__ is the maximum order of a clique in __G__.

A note on Winkler's algorithm for factor

A note on Winkler's algorithm for factoring a connected graph

✍ Bernhard Hochstrasser 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 529 KB

Hochstrasser, B., A note on Winkler's algorithm for factoring a connected graph, Discrete Mathematics 109 (1992) 127-132. Let the connected graph G be canonically embedded into a Cartesian product fl,,, CF. We improve a method of Winkler (1987) for partitioning I in a way suitable for finding the un