12
$\begingroup$

Given graphs $G$ and $H$ and vertex $v$ of $H$, the graph $G\otimes_v H$ is the graph obtained by replacing the vertex $v$ in $G$ by a copy of $H$. The vertices in the copy of $H$ are connected to the other vertices of $G$ in the same way as $v$ was connected to these vertices. $G\otimes_v H$ is obtained by substitution of $H$ for $v$.

Call a class $\mathcal C$ of finite graphs closed if it is closed under isomorphism, induced subgraphs and substitution.
The following classes of finite graphs are closed:

Empty class, class of singletons, class of complete graphs, class of graphs without edges, class of graphs without induced paths of length 4 ($P_4$-free graphs), class of perfect graphs, class of all finite graphs.

The closed classes form a complete lattice with respect to set-theoretic inclusion. The empty class is the smallest, the smallest above that are the singletons, minimal above the singletons are empty and complete graphs, minimal above these two incomparable classes is the class of $P_4$-free graphs. On top is the class of all finite graphs. Also, this lattice has antichains of the maximal possible size $2^{\aleph_0}$. All chains are countable since we are effectively working with subsets of a fixed countable set, the set of all finite graphs whose vertices are natural numbers.

Has this lattice been studied systematically? Are there any structural results known apart from the easy ones mentioned above? What if we modify our notion of closed class to include closure under complementation? In the list of examples above, this would only get rid of the classes of complete and of empty graphs.

Improve this question
$\endgroup$
2
  • $\begingroup$ Interesting. If a class of finite graphs is closed under minors, then is the same true of its $\otimes$-closure? Under those circumstances, the $\otimes$-closure would have a forbidden minors characterization. $\endgroup$
    – Todd Trimble
    Commented Oct 8, 2011 at 15:58
  • $\begingroup$ This is not the case, however. The class of $P_4$-free graphs, generated by an edge and a non-edge, is generated by a class closed under taking minors (just add in the single vertex graph to the other two). This class contains all complete graphs and hence $P_4$ itself, the path of length $4$ is a minor (even subgraph) of some graph in the class. But it is obviously not itself a member of the class. $\endgroup$
    – Stefan Geschke
    Commented Oct 24, 2011 at 9:35

1 Answer 1

Reset to default
1
$\begingroup$

You might redefine substitution as a family of replacements, one for each vertex. I am not sure if you are interested in enumeration, but for connected graphs I think your classes can then be construed as multicategories with morphisms $G\otimes \eta\rightarrow \eta$ where $\eta$ is a suitably indexed family of graphs, or as categories with $G\rightarrow G\otimes \eta$. Either way, the associativity concept derives from the lattice and decomposition structure of connected partitions of connected graphs. If you are interested in this approach I can provide a preprint of my thesis.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have to think more about your answer, i.e., the category part, but I defined substitution for single vertices since that is the basic building block. Now you can replace more vertices simply by iterating the procedure. Another way of defining the closure property that I am interested in is to replace every vertex of the first graph by a copy of the second graph. This would give what some people have called a wreath product. $\endgroup$
    – Stefan Geschke
    Commented Oct 24, 2011 at 9:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .