Repositorio de producción científica de la Universidad de Sevilla

Locally grid graphs: classification and Tutte uniqueness


Advanced Search
Opened Access Locally grid graphs: classification and Tutte uniqueness

Show item statistics
Export to
Author: Márquez Pérez, Alberto
Mier, Anna de
Noy, Marc
Revuelta Marchena, María Pastora
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2003
Published in: Discrete Mathematics, 266 (1-3), 327-352.
Document type: Article
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.
Size: 310.8Kb
Format: PDF



This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)