The characteristic ideal of a finite, connected, regular graph

ABSTRACT

Let Φ(x,y)∈ ℂ[x,y] be a symmetric polynomial of partial degree d. The graph G(Φ) is defined by taking ℂ as set of vertices and the points of 𝕍 (Φ(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.

REFERENCES

• 1: Josep M. Brunat , Joan-C. Lario, Galois Graphs: Walks, Trees and Automorphisms, Journal of Algebraic Combinatorics: An International Journal, v.10 n.2, p.135-148, Sept. 1999 [doi>10.1023/A:1018723511986]
• 2: J. M. Brunat and A. Montes. Digraphs defined by polynomials. Dep. Matemàatica Aplicada 2, Univ. Politèecnica de Catalunya, Preprint MAII-IR-04-00007, (2004) http://www.ma2.upc.es/montes/
• 3: Gary Chartrand , Linda Lesniak, Graphs & digraphs (2nd ed.), Wadsworth Publ. Co., Belmont, CA, 1986
• 4: D. Cox, J. Little, and D. O'Shea. Ideals, Varieties and Algorithms. Springer, New York, second edition, 1997.
• 5: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer, New York, 1998.
• 6: B. Korte and J. Vygen. Combinatorial Optimization. Springer, Berlin, 2000.
• 7: Antonio Montes, A new algorithm for discussing Gröbner bases with parameters, Journal of Symbolic Computation, v.33 n.2, p.183-208, February 2002 [doi>10.1006/jsco.2001.0504]
• 8: M. E. Watkins. Ends and automorphisms of infinite graphs. In G. Hahn and G. Sabidussi, editors, Graph Symmetry, Algebraic

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory

Keywords:
characteristic ideal, conjecture, connected component, galois graph, pairing, polynomial digraph, polynomial graph, strongly polynomial graph, variety of a pairing