Reconfiguration of graph minors

DOI10.4230/LIPICS.MFCS.2018.75arXiv1804.09240MaRDI QIDQ6300765FDOQ6300765

Authors: Benjamin Moore, N. Nishimura, Vijay Subramanya 

Publication date: 24 April 2018

Abstract: Under the reconfiguration framework, we consider the various ways that a target graph $H$ is a {em minor} of a host graph $G$, where a subgraph of $G$ can be transformed into $H$ by means of {em edge contraction} (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint). Equivalently, an {em $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 {em 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.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph minors (05C83)

This page was built for publication: Reconfiguration of graph minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300765)