The Characteristic Ideal of a Finite, Connected, Regular Graph

摘要

Let Φ(x,y) ∈ C[x,y] be a symmetric polynomial of partial degree d. The graph G(Φ) is defined by taking C as set of vertices and the points of V(Φ(x, y)) as edges. We study the following problem: given a finite, connected, d-regular graph H, find the polynomials Φ(x, y) such that G(Φ) has some connected component isomorphic to H and, in this case, if G(Φ) has (almost) all components isomorphic to H. The problem is solved by associating to H a characteristic ideal which offers a new perspective to the conjecture formulated in a previous paper, and allows to reduce its scope. In the second part, we determine the characteristic ideal for cycles of lengths ≤ 5 and for complete graphs of order ≤ 6. This results provide new evidence for the conjecture.