Neighbourhood attachments indexed by induced embeddings

Let $J,A,L$ be finite simple graphs and let $I\subseteq V(J)$ be independent, meaning that no two distinct vertices of $I$ are adjacent. Put $F=J[V(J)\setminus I]$, the subgraph induced by the vertices outside $I$. Let $\mathrm{\Phi }$ be the set of induced embeddings $\phi :F\to A$: these are injections on vertices preserving both adjacency and nonadjacency. Put $T=\mathrm{\Phi }\times I$.

The labelled neighbourhood-attachment graph has a tagged core $C=\{0\}\times V(A)$ and, for every $(\phi ,u)\in T$, a tagged part $P_{\phi ,u}=\{1\}\times \{(\phi ,u)\}\times V(L)$, with ordered products associated to the right. Its vertices are the union of the core and these parts. Inside the core retain exactly the edges of $A$, and inside each part retain exactly the edges of $L$. A vertex $(0,a)$ of the core is adjacent to a vertex $(1,((\phi ,u),x))$ of $P_{\phi ,u}$ exactly when there is $v\in V(F)$ with $a=\phi (v)$ and $\{u,v\}\in E(J)$. There are no edges between distinct parts. These rules specify the entire edge set. Thus different embeddings with the same image still receive distinct parts.

For comparison with indexing by induced images, let $\mathcal{S}=\{\phi (V(F)):\phi \in \mathrm{\Phi }\}$. For each $S\in \mathcal{S}$, choose one ${\phi }_S\in \mathrm{\Phi }$ with image $S$; it is an isomorphism from $F$ onto $A[S]$. The induced subgraph on the core and the parts $P_{{\phi }_S,u}$ for $S\in \mathcal{S}$ and $u\in I$ is the corresponding one-embedding-per-image attachment. Other embeddings with the same image and their parts remain present in the full labelled construction.

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Induced embeddings and induced copies of a graph

Subgraphs, induced subgraphs and spanning subgraphs

Cliques, independent sets, clique number and independence number

Tagged graph families with anticomplete parts

The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) }

The difference a ∖ b, the symmetric difference a △ b, and the complement X ∖ a relative to a set X

The vertex set of $F$ is finite as a subset of $V(J)$. Enumerating that finite domain identifies the set of all maps from $V(F)$ to $V(A)$ with a finite product of copies of $V(A)$, including the singleton empty product when $V(F)$ is empty. The product rule makes that set finite, and the induced embeddings form a subset; hence $\mathrm{\Phi }$ and then $T=\mathrm{\Phi }\times I$ are finite. The tagged-family construction applied to one copy of $A$ and the copies of $L$ indexed by $T$ gives a finite vertex set with disjoint core and parts.

Every specified internal edge has distinct endpoints, and every specified attachment edge joins the disjoint core and a part. Consequently the specified edge set consists of two-element subsets of the finite vertex set and determines a finite simple graph. The edge rules exhaust the possibilities, so they introduce no other core-to-part edges or edges between parts. Each $\phi \in \mathrm{\Phi }$ is an isomorphism onto its induced image; the finite set of images permits one such embedding to be chosen for each image. If $I$ or $\mathrm{\Phi }$ is empty, there are no attachment parts; if $V(F)$ is empty, the unique empty embedding is included and its parts have no core neighbours.

The product rule: | A × B| = | A| | B|, and |∏_i<m Aᵢ| = ∏_i<m| Aᵢ|

A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A

Tagged graph families with anticomplete parts