Circuits in graphs through a prescribed set of ordered vertices

David Coudert 1 Frédéric Giroire 1 Ignasi Sau 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A circuit in a simple undirected graph G=(V,E) is a sequence of vertices {v_1,v_2,...,v_{k+1}} such that v_1=v_{k+1} and {v_i,v_{i+1}} in E for i=1,...,k. A circuit C is said to be edge-simple if no edge of G is used twice in C. In this article we study the following problem: which is the largest integer k such that, given any subset of k ordered vertices of a graph G, there exists an edge-simple circuit visiting the k vertices in the prescribed order? We first study the case when G has maximum degree at most 3, establishing the value of k for several subcases, such as when G is planar or 3-vertex-connected. Our main result is that k=10 in infinite square grids. To prove this, we introduce a methodology based on the notion of core graph, in order to reduce the number of possible vertex configurations, and then we test each one of the resulting configurations with an Integer Linear Program (ILP) solver.
Type de document :
Article dans une revue
Journal of Interconnection Networks, World Scientific Publishing, 2011, 11 (3-4), pp.121-141. <10.1142/S0219265910002763>
Liste complète des métadonnées


https://hal.inria.fr/inria-00585561
Contributeur : David Coudert <>
Soumis le : mercredi 13 avril 2011 - 12:06:08
Dernière modification le : vendredi 9 juin 2017 - 10:42:15
Document(s) archivé(s) le : samedi 3 décembre 2016 - 17:35:05

Fichier

join-final-noformat.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Frédéric Giroire, Ignasi Sau. Circuits in graphs through a prescribed set of ordered vertices. Journal of Interconnection Networks, World Scientific Publishing, 2011, 11 (3-4), pp.121-141. <10.1142/S0219265910002763>. <inria-00585561>

Partager

Métriques

Consultations de
la notice

230

Téléchargements du document

155