0
$\begingroup$

It's rather straightforward, I guess, to define conjugate subgraphs of a graph via its conjugate nodes. (Two nodes $x,y$ are conjugate when there is an automorphism $g$ such that $x = g(y)$.)

Definition: Two subgraphs $G,G'$ of a graph $H$ are conjugate when there is a bijection $f: V(G) \rightarrow V(G')$ such that $x,f(x)$ are conjugate for all $x \in V(G)$.

Note that being conjugate is more than being isomorphic.

Questions: Is there another name for conjugate subgraphs? And where do they play a role?

Is there, for example, something like a generalized Burnside's lemma which connects the number of "subgraph orbits" - with subgraphs of fixed order, eventually - with something else?

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ Wouldn’t it be more natural to say that $G$ and $G'$ are conjugate if there is an automorphism $g$ of $H$ such that $g(V(G))=V(G')$? $\endgroup$
    – Emil Jeřábek
    Commented Aug 21, 2012 at 12:35
  • 1
    $\begingroup$ In the same orbit (of the natural action of AUT$(H)$ on subgraphs? But if conjugate is good enough for vertices then it should be good enough for subgraphs. $\endgroup$
    – Aaron Meyerowitz
    Commented Aug 21, 2012 at 12:42
  • 2
    $\begingroup$ I think Polya Enumeration can fit the bill for a generalization of Burnside's lemma. $\endgroup$
    – Aaron Meyerowitz
    Commented Aug 21, 2012 at 12:49
  • 2
    $\begingroup$ As I understand it, your definition implies that any two subgraphs of the circular graph $C_n$ having the same number of vertices are "conjugate", since any two vertices of $C_n$ are conjugate. So conjugate subgraphs in your sense may not be isomorphic. Is this really your intention? $\endgroup$
    – Frieder Ladisch
    Commented Aug 21, 2012 at 13:16
  • 3
    $\begingroup$ @Hans: My definition is not equivalent to yours, the condition is stronger (it requires all the vertex pairs to be conjugate via the same automorphism). What I am saying is that the concept you defined looks quite weird to me, whereas my proposal is close to the definition of conjugate subgroups (the only difference being that for groups, only inner automorphisms are taken into account), which I assumed was your original motivation. Also, note that what I wrote is equivalent to Aaron’s description (being in the same orbit of the natural action of Aut($H$) on subgraphs). $\endgroup$
    – Emil Jeřábek
    Commented Aug 21, 2012 at 13:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .