For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ isomorphic to $H$ induced in $G$ by some set of complete representatives for the partition $P=\{Q_t:t\in V(H)\}$?
1 Answer
$\begingroup$
$\endgroup$
7
This is not true in general. Here is a non-trivial counter example: Let $H \sim K_{1,2}$ and $G\sim C_4$, with the vertices of $G$ labelled $a,b,c,d$ around the cycle. Then $\{a\},\{c\},\{b,d\}$ works as a partition, but the induced subgraph $G[a,b,d]$ is isomorphic to $H$.
-
$\begingroup$ And if you want to add non-trivial directedness, we can let $H$ be the graph $x \to y, z \to y$ and $G$ be $a \to b, a \to d, c\to b, c\to d$. $\endgroup$ Dec 31, 2018 at 17:08
-
$\begingroup$ How would you express $\{(a,b),(b,c),(c,d ),(d,a)\}$ in terms of the blocks $\{a\},\{c\},\{b,d\}$? I don't see how a cycle can be written in the form $\bigcup_{(u,v)\in E(H)}X_u\times X_v$ unless $|X_t|=1$ for all $t\in V(H)$. $\endgroup$ Dec 31, 2018 at 17:25
-
$\begingroup$ I would say that $\{ ab,bc,cd,da\}=(\{a\} \times \{b,d\})\cup (\{b,d\} \times \{c\})$. Is that what you had in mind? $\endgroup$ Dec 31, 2018 at 17:27
-
$\begingroup$ @ Puck Rombach But $\{a\}\times \{b,d\}\cup \{b,d\}\times \{c\}=\{(a,b),(a,d),(b,c),(d,c)\}$ which isnt a cycle $\endgroup$ Dec 31, 2018 at 17:29
-
$\begingroup$ I was ignoring the directions in that comment. Is that what you're worried about? In that case, we can say $\{ ab,ad,cb,cd\}= \{a\}\times \{b,d\} \cup \{c\}\times \{b,d\}$? $\endgroup$ Dec 31, 2018 at 17:31