1
$\begingroup$

I define partially cycle graphs as follows.

If we add the same subgraph to $n-k$ vertices of an $n$-vertex cycle graph, where $1\le k < n$, we create a partially cycle graph.

Here are a few examples.

$C_6$:

enter image description here

Automorphism group: $D_6 = (2, 6)(3, 5) \times (1, 2, 3, 4, 5, 6)$

Order: 12

Generators: $\{(2, 6)(3, 5), (1, 2, 3, 4, 5, 6)\}$

Example: When $n = 6, k = 1$:

enter image description here

Automorphism group: $\{e, (1, 5)(2, 4) \}$

Order: 2

Generators: $\{(1, 5)(2, 4)\}$

Example: When $n = 6, k = 5$:

enter image description here

Automorphism group: $\{e, (1, 5)(2, 4) (7, 10) (8, 11) \}$

Order: 2

Generators: $\{(1, 5)(2, 4) (7, 10) (8, 11)\}$

Example: When $n = 6, k = 3$:

enter image description here

Automorphism group: $\{e, (1, 3)(4, 6) (7, 9) \}$

Order: 2

Generators: $\{(1, 3)(4, 6) (7, 9)\}$

Obviously, the rotational symmetry which we have in $D_6$ is no more in the partially cycle graphs. The automorphism group contains only the reflections i.e. transpositions.

My question:

  1. Is there a general expression for the automorphism group of partially cycle graphs when $k$ is not fixed?
  2. Is there a general expression for the automorphism group of partially cycle graphs when $k$ is fixed?
  3. Can I always assume that the generator will always be some kind of transposition group?
$\endgroup$
  • 1
    $\begingroup$ Do you want to add the subgraph to adjacent vertices of the cycle? Otherwise you could start with a $2k$-cycle and attach an edge and a single vertex to every second vertex of the cycle, obtaining a graph with automorphism group $D_k$. $\endgroup$ – Christian Sievers Jul 10 '16 at 19:00
  • $\begingroup$ @ChristianSievers, I would like to add the subgraph to adjacent vertices. $\endgroup$ – Omar Shehab Jul 10 '16 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.