General  Information
Important Dates
Conference Poster
Organizing Committee
Program and Schedule
Invited Talks
Contributed Talks
Software Exhibitions
Registered Participants
 Call  For
Research Papers
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Gastronomic Guide
Additional Information
Social Events
Previous ISSACs
Other Events



The characteristic ideal of a finite, connected, regular graph

J. M. Brunat, A. Montes


This paper is the second of a series of two about polynomial graphs. Let $\Phi(x,y)\in\mathbb{C}[x,y]$ be a symmetric polynomial of partial degree $d$ and let $I$ be the ideal generated by $\Phi(x,y)$. The graph $G(\Phi)$ is defined by taking $\mathbb{C}$ as set of vertices and the points of $\mathbb{V}(I)$ as edges. We study the following problem: given a finite, connected, $d$-regular graph $H$, find the polynomials $\Phi(x,y)$ such that $G(\Phi)$ has some connected component isomorphic to $H$ and, in this case, if $G(\Phi)$ 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 the first paper, and allows to reduce its scope. In the second part, we determine the characteristic ideal for cycles of lengths $\le 5$ and for complete graphs of order $\le 6$. This results provide new evidence for the conjecture.

  issac2004 @