1
$\begingroup$

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

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
7
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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