Abstract | ||
---|---|---|
We define a locally grid graph as a graph in which the structure around each vertex is a 3 × 3 grid, the canonical examples being the toroidal grids Cp × Cq. The paper contains two main results. First, we give a complete classification of locally grid graphs, showing that each of them has a natural embedding in the torus or in the Klein bottle. Secondly, as a continuation of the research initiated in (On graphs determined by their Tutte polynomials, Graphs Combin., to appear), we prove that Cp × Cq is uniquely determined by its Tutte polynomial, for p, q ≥ 6. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0012-365X(02)00818-X | Discrete Mathematics |
Keywords | Field | DocType |
main result,complete classification,klein bottle,tutte uniqueness,locally grid graph,toroidal grid,graphs combin,natural embedding,tutte polynomial,grid graph,canonical example,toroidal grids cp | Tutte 12-cage,Discrete mathematics,Combinatorics,Tutte polynomial,Tutte theorem,Polyhedral graph,Nowhere-zero flow,Chromatic polynomial,Mathematics,Tutte matrix,Graph coloring | Journal |
Volume | Issue | ISSN |
266 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
11 | 1.08 | 10 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alberto Márquez | 1 | 124 | 20.06 |
anna de mier | 2 | 22 | 2.48 |
M. Noy | 3 | 369 | 33.94 |
M. P. Revuelta | 4 | 24 | 7.72 |