5
$\begingroup$

Given a graph $G$, its ΔY-family is the smallest family of graphs that contains $G$ and is closed under ΔY- and YΔ-transformations.

Since YΔ-transformations can introduce multi-edges, the ΔY-family of $G$ might consist of multigraphs even if $G$ itself is simple. However, for many notable graph classes, this does not happen. For example, the Petersen family is generated from $K_6$ and contains only simple graphs. The same is true for $K_7$. But it fails for $K_5$.

Question: Is there a way to tell in advance whether $G$ generates a ΔY-family of only simple graphs?

$\endgroup$

0

You must log in to answer this question.