Contraction Obstructions for Connected Graph Searching

Abstract : We consider the connected variant of the classic mixed search game where, in each search step, cleaned edges form a connected subgraph. We consider graph classes with bounded connected monotone mixed search number and we deal with the the question weather the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as graphs are not well quasi ordered under the contraction partial ordering relation. In this paper we provide the obstruction set for k = 2. This set is finite, it consists of 174 graphs and completely characterizes the graphs with connected monotone mixed search number at most 2. Our proof reveals that the "sense of direction" of an optimal search searching is important for connected search which is in contrast to the unconnected original case.
Type de document :
Communication dans un congrès
ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. 2014
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083704
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 17:14:41
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 14 avril 2017 - 15:38:45

Fichier

cmms - ICGT 2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01083704, version 1
  • ARXIV : 1410.8756

Collections

Citation

Best Micah J, Arvind Gupta, Dimitrios M. Thilikos, Dimitris Zoros. Contraction Obstructions for Connected Graph Searching. ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. 2014. 〈lirmm-01083704〉

Partager

Métriques

Consultations de la notice

143

Téléchargements de fichiers

70