Building graphs from colored trees

Rachel M. Esselstein ; Peter Winkler

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

We will explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely, fix a radius $\rho$ and let $N(G)$ be the set of isomorphism classes of $\rho$-neighborhoods of vertices of $G$ where $G$ is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. The root of the neighborhood will be the unique vertex at the "center" of the graph. Given a set $\mathcal{S}$ of colored graphs with a unique root, when is there a graph $G$ with $N(G)=\mathcal{S}$? Or $N(G) \subset \mathcal{S}$? What if $G$ is forced to be infinite, or connected, or both? If the neighborhoods are unrestricted, all these problems are recursively unsolvable; this follows from the work of Bulitko [Graphs with prescribed environments of the vertices. Trudy Mat. Inst. Steklov., 133:78–94, 274, 1973]. In contrast, when the neighborhoods are cycle free, all the problems are in the class $\mathtt{P}$. Surprisingly, if $G$ is required to be a regular (and thus infinite) tree, we show the realization problem is NP-complete (for degree 3 and higher); whereas, if $G$ is allowed to be any finite graph, the realization problem is in P.

Détail

DOI : 10.37236/433

Classification : 05C85, 05C05, 05C15