License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.75
URN: urn:nbn:de:0030-drops-96573
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9657/
Go to the corresponding LIPIcs Volume Portal

Moore, Benjamin ; Nishimura, Naomi ; Subramanya, Vijay

Reconfiguration of Graph Minors

pdf-format:
LIPIcs-MFCS-2018-75.pdf (0.4 MB)

Abstract

Under the reconfiguration framework, we consider the various ways that a target graph H is a minor of a host graph G, where a subgraph of G can be transformed into H by means of edge contraction (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint). Equivalently, an H-model of G is a labeling of the vertices of G with the vertices of H, where the contraction of all edges between identically-labeled vertices results in a graph containing representations of all edges in H.
We explore the properties of G and H that result in a connected reconfiguration graph, in which nodes represent H-models and two nodes are adjacent if their corresponding H-models differ by the label of a single vertex of G. Various operations on G or H are shown to preserve connectivity. In addition, we demonstrate properties of graphs G that result in connectivity for the target graphs K_2, K_3, and K_4, including a full characterization of graphs G that result in connectivity for K_2-models, as well as the relationship between connectivity of G and other H-models.

BibTeX - Entry

@InProceedings{moore_et_al:LIPIcs:2018:9657,
  author =	{Benjamin Moore and Naomi Nishimura and Vijay Subramanya},
  title =	{{Reconfiguration of Graph Minors}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{75:1--75:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9657},
  URN =		{urn:nbn:de:0030-drops-96573},
  doi =		{10.4230/LIPIcs.MFCS.2018.75},
  annote =	{Keywords: reconfiguration, graph minors, graph algorithms}
}

Keywords: reconfiguration, graph minors, graph algorithms
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI