Paper Info
Title
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.
Year
DOI
Venue
2004
10.1145/1005285.1005295
ISSAC
Keywords
Field
DocType
complete graph,connected component isomorphic,following problem,d-regular graph h,new perspective,partial degree,characteristic ideal,graph g,previous paper,new evidence,pairing,regular graph,symmetric polynomial,connected component
Discrete mathematics,Combinatorics,Strongly regular graph,Vertex-transitive graph,Graph power,Integral graph,Regular graph,Distance-regular graph,Graph minor,Mathematics,Complement graph
Conference
ISSN
ISBN
Citations 
Proc. ISSAC-2004, ACM, 50-57
1-58113-827-X
1
PageRank 
References 
Authors
0.43
2
2
Name
Order
Citations
PageRank
Josep M. Brunat1425.52
Antonio Montes220519.68