Building Graphs from Colored Trees
Rachel Esselstein, Peter M. Winkler · The Electronic Journal of Combinatorics · 2010
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2010
Abstract
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.
Open the resolved locator · 10.37236/433
Metadata licence: OpenAlex metadata (CC0)