Tagged Questions

1
vote
1answer
39 views

Determine no. elements in $ \operatorname{Aut}(H)$ where $H$ is the 6 point/5line graph in the shape of H

Determine the amount of automorphisms in the group $\operatorname{Aut}(H)$ where $H$ is the graph with 6 points and five lines in the shape of a capital 'H'. Here is what it should look like, I ...
2
votes
2answers
93 views

Can $C_{10}$ be isomorphic to $C_5\times C_2$?

$C_{10}$ is algebraically described by $a^{10}=1$. That's all. $C_{10}$ is $\{1,a,a^2,a^3,a^4,a^5,a^6,a^7,a^8,a^9\}.$ $C_5\times C_2$ is algebraically described by $r^5=1$, $f^2=1$, and $rf=fr$. ...
3
votes
0answers
126 views

Petersen graph is not a Cayley graph

How can I show that the Petersen graph is not a Cayley graph? I don't know very much about Cayley graphs, I know that they are vertex-transitive, but so is the Petersen graph. It probably has to do ...
9
votes
2answers
115 views

Representation theorems for groups

There are two baffling representation theorems for groups: Every group is isomorphic to the automorphism group of some graph. (see Frucht's theorem) Every group is isomorphic to the fundamental ...
0
votes
2answers
32 views

how do I calculate the ismorphism group of a six-nodes-tree?

How do I calculate the ismorphism group of a connected six-nodes-tree? The tree has a node centred and the other 5 nodes are leaves of the graph. I already know the answer is 6, which is the quotient ...
7
votes
1answer
108 views

Computing shortest paths in Cayley graphs

I am interested in shortest paths in the Cayley graph of the alternating group $A_{12}$ acting on the vertices of the icosahedron, where the generators are given by 5-cycles on the neighbors of any ...
0
votes
1answer
119 views

Prove that the group of automorphisms of a labelled Cayley graph of a group G is the group G itself (Just stumped on one direction)

I feel like for this question it is just a matter of showing the mapping in both directions, from the group to the graph and the graph to the group. So for the mapping from the group to the graph, I ...
4
votes
1answer
77 views

Action of a subgroup of finite index on a tree induced by an action of a group on a tree

Let $G$ be a group wich acts on a tree $\Gamma$. Then $U$ acts on $\Gamma$ for every $U\leq G$. Question: Why does the following hold? If $|G:U|<\infty$. Then the minimal $U$-invariant subtree ...
14
votes
1answer
304 views

What are all conditions on a finite sequence $x_1,x_2,…,x_m$ such that it is the sequence of orders of elements of a group?

My Definition: The finite sequence $x_1,x_2,...,x_m$ of nonnegative integers, is said to be generated by the finite group $G$ iff $n:=|G|=x_1+x_2+...+x_m$. $n$ has $m$ divisors. if ...
5
votes
2answers
121 views

How many ways can one paint the edges of a Petersen graph black or white?

How many ways can one paint the edges of a Petersen graph black or white? I know that the symmetrygroup of the Petersen graph is $ [S5][1]$. Furthermore this this seems like a case where I should ...
4
votes
1answer
91 views

Symmetries of a graph

Determine the number of symmetries in the following graph: What are the general things you should do when finding such symmetries? Usually I would label all of them from $1...n$ and note their ...
2
votes
1answer
75 views

Wreath Products of Symmetric Groups

I am currently in the process of reading an article by D.Bundy The connectivity of commuting graphs. In section 3 (in the Preliminary Results) Bundy gives the following result: $\mathbf{(3.1)}$ Let ...
1
vote
0answers
85 views

Questions on Trees and Automorphisms of Trees

Please give me some hints for the following problems. Many thanks in advance. Problem 1. Let $T_1,\cdots, T_n$ be a finite set of subtrees of a tree $X$ and let $T_i\cap T_j\ne\emptyset$ for all $i$ ...
4
votes
1answer
104 views

Cayley graphs on small Dihedral and Cyclic group

Consider the following problem Let $n \leq 5$ and let $\Gamma = \mathrm{Cay}(C_{2n},S)$ be the Cayley graph with Cayley set $S$. Show that $\Gamma$ is isomorphic to $\mathrm{Cay}(D_{2n},S')$ ...
0
votes
1answer
52 views

Arc transitivity of the complete graph

Recall that a graph $G$ is arc transitive if the natural action of $\mathrm{Aut}(G)$ on $A(G) = \{ (u,v) | \{u,v\} \in E(G)\}$ is transitive. In other words, given $(u,v),(u'.v') \in A(G)$ one finds ...
0
votes
1answer
73 views

Constructing a graph based on numbers of vertices, incident edges, and incident triangles

In my project to construct the outer automorphism group for $S_6$ I have come across a need (or desire) to visualize a graph that has 15 vertices, with each vertex having 6 incident edges and 3 ...
4
votes
1answer
183 views

Graphs with a unique $3$-path free acyclic orientation up to isomorphism.

Let $\Gamma$ be a simple, $3$-colorable graph such that, up to isomorphism, there exists exactly one acyclic orientation of $\Gamma$ that does not contain a directed 3-path. (To be clear, when I say ...
10
votes
0answers
228 views

Normalizers of automorphism groups

In abstract groups $\Gamma$ the normalizer $N_\Gamma(S)$ of a subset $S\subseteq\Gamma$ is the subgroup of all $x \in \Gamma$ that commute with $S$, i.e. $xS = Sx$, i.e. $x\ y\ x^{-1} \in S $ for all ...
3
votes
1answer
114 views

Ends of a Group

I have these two questions that I cannot get any intuition about. Perhaps someone can possibly offer a few hints on how to get started? 1) Show that the ends of ${\bf F_2} \oplus {\bf F_2}$ is equal ...
3
votes
1answer
82 views

Behaviour of the Cayley graph of a group when changing the generating set / Number of ends of a group

Introduction of terminology: Let $G$ be an infinite group and let $S$ be a finite generating subset of $G$ that is symmetric, i.e. $x\in S$ implies $x^{-1}\in S$. Then the relation $g\sim ...
18
votes
2answers
428 views

Groups and generating sets

This question feels completely trivial and I am somewhat embarrassed to be asking it, but I am having a brain dead moment and failing to prove what I'm sure is a completely trivial statement about ...
2
votes
0answers
45 views

Dehn Twist in the sense of graphs

Does anyone knows a good book or script about Dehn Twists in the sense of graphs. More precisely: I need to know how a Dehn Twist yields an automorphism of a group or subgroups. I want to know ...
4
votes
1answer
91 views

Why does every finite subgroup of $\mathrm{Aut}(F_n)$ acts on a graph of Euler characteristic $n-1$?

My question is the following: In a paper I read that: Any finite subgroup of $\mathrm{Aut}(F_n)$ can be realised as agroup of baspoint-preserving isometries of a graph of Euler characteristic $1-n$. ...
4
votes
1answer
120 views

Is $K_n\times K_n$ a Cayley graph?

Let $K_n\times K_n$ be the Cartesian product of two complete graphs. Is $K_n\times K_n$ is Cayley graph or not? I know that I have to use this lemma: A connected graph $G$ is Cayley if and only ...
2
votes
1answer
153 views

Automorphism of graph

Let $G$ be a connected vertex transitive graph and $G_v$ denote stabilizer of the vertex $v$. If $h$ is any automorphism of $G$ for which $d(v,h(v))=1$, and $G$ is symmetric,the $h$ and $G_v$ ...
4
votes
0answers
155 views

“Semidirect product” of graphs?

The first subquestion is "has a standard notion of semidirect product been defined in graph theory"? If yes, i'd like to know if the definition i'm gonna give is equivalent to the standard one. I'd ...
6
votes
0answers
114 views

Connecting cells by line and column permutations in a finite grid

I'd like to know whether the following simple problem has been studied before and if any solution is known. Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said ...
2
votes
2answers
91 views

Transitive graph such that the stabilizer of a point has three orbits

I am looking for an example of a finite graph such that its automorphism group is transitive on the set of vertices, but the stabilizer of a point has exactly three orbits on the set of vertices. I ...
2
votes
4answers
259 views

Connection Between Automorphism Groups of a Graph and its Line Graph

First, the specific case I'm trying to handle is this: I have the graph $\Gamma = K_{4,4}$. I understand that its automorphism group is the wreath product of $S_4 \wr S_2$ and thus it is a group of ...
3
votes
0answers
146 views

Automorphism Group of Paley Graph

I would like an explanation as to the structure description of the automorphism group of a Paley graph. Paley graphs are a specific case of Cayley graphs where the group is $Z_q$ (q is a prime power ...
3
votes
1answer
90 views

Fourier analysis on groups and paths in a Cayley graph

If one takes a cyclic group and a function on this group, and performs harmonic analysis on it (classical Fourier analysis), the result is a set of coefficients, each one of them corresponding to ...
4
votes
1answer
201 views

Getting generators of graphs automorphism group

Suppose I have a graph like this and a list of its automorphisms. How do I go about getting a set of generators for this group?
11
votes
3answers
462 views

Two seemingly unrelated puzzles have very similar solutions; what's the connection?

I think it's an interesting coincidence that the locker puzzle and this puzzle about duplicate array entries (see problem 6b) have such similar solutions. Spoiler alert! Don't read on if you want to ...