0
$\begingroup$

Let $G=(V,E)$ be a graph and $\mathrm{Ind}(G)$ be the collection of its independent sets.

We call a graph automorphism $f:V \to V$ of $G$ good if it is non-trivial and $f(\mathrm{Ind}(G))=\mathrm{Ind}(G)$, i.e. $f$ maps every independent set of $G$ into another independent set of $G$.

(i) Is there a (elegant/minimal) set of conditions under on the graph $G$ that guarantees the existence of a good automorphism?

(ii) Is there any paper in the mathematical literature studying this class of good automorphisms?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Some graphs have trivial automorphism groups only. $\endgroup$
    – Turbo
    Commented Jun 9, 2015 at 17:33
  • $\begingroup$ What do you mean by "automorphism"? $\endgroup$
    – Goldstern
    Commented Jun 9, 2015 at 18:54
  • 6
    $\begingroup$ I'm voting to close this question as off-topic because the question depends on a misunderstanding of a standard term. $\endgroup$
    – Chris Godsil
    Commented Jun 9, 2015 at 19:33

1 Answer 1

Reset to default
4
$\begingroup$

I thought that if $f$ is graph automorphism then it preserves both edges and non-edges. In that case, any automorphism would be good, and as @Turbo said, some graphs have trivial autormorphism groups only. See https://en.wikipedia.org/wiki/Graph_automorphism

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .