The generating polynomial and Euler characteristic of intersection graphs

✍ Scribed by Yeong-Nan Yeh

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 580 KB
• Volume: 131
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)90393-x

✦ Synopsis

Let E" be n-dimensional Euclidean space. A molecular space is a family of unit cubes in E". Any molecular space can be represented by its intersection graph. Conversely, it is known that any graph G can be represented by molecular space M(G) in E" for some n. Suppose that S, and S, are topologically equivalent surfaces in E" and molecular spaces M, and M, are the two families of unit cubes intersecting S, and S,, respectively. It was revealed that M, and M, could be transferred from one to the other with four kinds of contractible transformations if a division was small enough.

In this paper, we will introduce the generating polynomial E,(x) and the Euler characteristic e(G) of a graph G. We will study several various operations performing on two graphs (surfaces). The generating polynomial of the new graph, which is obtained by performing various operations on well-studied graphs, can be expressed in terms of those of the old graphs. An immediate consequence is that the four contractible transformations do not change the Euler characteristic of a graph. Furthermore, we prove that all chordal graphs are contractible.