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)\}$?


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$ – Puck Rombach Dec 31 '18 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$ – Ethan Dec 31 '18 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$ – Puck Rombach Dec 31 '18 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$ – Ethan Dec 31 '18 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$ – Puck Rombach Dec 31 '18 at 17:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.