# Tagged Questions

67 views

### Textbooks on graph theory

I've read the textbook Groups and Their Graphs by Grossman, and I'm interested in learning more about graphs. I know about O. Ore's book in the same series (Graphs and Their Uses), but I'm interested ...
36 views

### Variations of M,n,k-games

I just read about M,n,k-games and wondered if the following variation (with fixed $k$) has been studied as well and if there exists a name for it: Two players consecutively mark elements of ${\bf Z}$ ...
89 views

### Category theory for graph theory research

I am doing research in algebraic graph theory, focusing on the relation between graphs and groups (especially the representing groups as graphs) for my Ph.D. In particular, one of the ideas is to ...
60 views

### Example of non-Abelianness of symmetric group for graphs

I know that for $n \ge 3$, $S_n$ is non-Abelian. I would like to work out an example in terms of graphs so to make it sure that I understand it right. A symmetric group of graphs of four vertices, ...
70 views

### A mathematical game: moving tiles

There is a mathematical game called moving tiles. There are $8$ different movable tiles on a $3 \times 3$ board, At the beginning the tiles' location is given as following: ...
70 views

### Asymmetry of random graphs

By a well known result of Pólya we know that the number $g_n$ of isomorphism classes of simple graphs on $n$ vertices is asymptotically equivalent to $\frac{2^{\binom{n}{2}}}{n!}$. In this paper the ...
35 views

### Eulerian path for Rubik's Cube states

There are a number of discussions online confirming that there exists a Hamiltonian cycle through the states of a Rubik's Cube. Or more precisely, the "quarter-turn metric Cayley graph for the Rubik's ...
56 views

### number of symmetries of an arbitrary graph

Given an (undirected) graph G, is there way to (approximately) estimate the order of Aut(G)-- i.e., the number of permutations ...
46 views

Consider the 6-node ring with only one bit active (000001). This is shown in the following figure as a hexagon with one circle filled. If the active bit is traveling in the counter clockwise ...
105 views

### Applications of Cayley Graphs in Physics

I have been recently reading about Cayley graphs and character theory. It is evident that Cayley graphs are very useful tool in theoretical computer science. In physics, Cayley graphs seem do appear ...
26 views

### prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
81 views

### Is there a cayley graph for the Klein bottle?

When studying algebraic topology we learned about the fundamental group of the $2$-torus $T^2$ which is isomorphic to $$\langle a, b \mid aba^{-1}b^{-1} \rangle$$ (the free abelian group on two ...
54 views

### Largest order of automorphism group on a rooted tree?

MacArthur, Sanchez-Garcia, and Anderson have used the ratio of the order of $|Aut(G)|$ and $n!$ (i.e., order of $S_n$) as a normalized measure of the symmetries present in a graph. I am working on ...
77 views

### On the graph of induction-restriction for group-subgroup representations

Let $G$ be a finite group, and $H$ a subgroup. Let $(V_i)_{i \in I}$ and $(W_j)_{j \in J}$ be the irreducible complex representations of $G$ and $H$ (up to isom.). Consider the graph ...
78 views

### Text on Group Theory and Graphs

A student and I are going to investigate the use of group theoretic techniques in graph theory. What are good texts in this area (introductory and otherwise)? We are particularly interested in ...
26 views

### Determining Commutativity from a Digraph?

I'm trying to sort out when a group is commutative, given its digraph. We have vertices of the digraph for each element in the group and different arcs connecting the vertices for each generator of ...
33 views

### A Question about Cayley Graph [duplicate]

Petersen graph is http://en.wikipedia.org/wiki/Petersen_graph. It is not Cayley graph. How to prove. Can someone give a general method to judge a graph is or not a Cayley graph?
52 views

### Subgroup lattice

I've been searching around for a while now and can't seem to find a clear explanation of what a subgroup lattice of a group actually is. I see the vertex set is given by the subgroups of the group, ...
77 views

### Groups with presentation $\langle x_1,x_2,\dotsc, x_n\mid x_1^3, x_2^3,\dotsc, x_n^3\rangle$

I'm computer engineer but I'm working in some topics related with group theory. I found (accidentally) a group with presentation $\langle x_1,x_2,\dotsc, x_n\mid x_1^3, x_2^3,\dotsc, x_n^3\rangle$ ...
96 views

### Number of 2n-1 equal size partitions up to symmetry

Consider the $K_{2n}$ (or just the set $\{1,\dots,2n\}$) with $S_{2n}$ acting on the vertices. Moreover consider a collection of 2n-1 partitions of the vertices into two equal sized sets (repeated ...
84 views

### Klein four-group as automorphism group of a graph.

Every finite abstract group is the automorphism group of some graph. Can someone show an example of a graph whose automorphism group is isomorphic to the Klein four-group?
93 views

### Example of a simple graph isomorphic to a permutation group.

I'm taking a first course in graph theory this semester and I'm working trough Graph Theory with Applications by J.A. Bonday and U.S.R. Murty. I can't find an answer to question 1.2.12(f): (a) ...
63 views

### Trying to understanding the proof of the fact that Kazhdan property (T) implies expanders.

I am trying to trying to understanding the proof of the fact that Kazhdan property (T) implies expanders. This is a result of Grigory Margulis. It is stated in Proposition 3.3.1 on Page 30 of the book ...
37 views

### Graph with sharply 1-transitive automorphism group

What finite Graphs $G$ have the property that for all $v,w\in G$, there is exactly one automorphism $\phi$ of $G$ with $\phi(v)=w$? Of course, each of the three graphs with one or two vertices have ...
38 views

### Does every graph arise as the commutativity graph of some group?

By graph let us mean a set $G$ together with a relation $\bot$ that is reflexive and symmetric. Now every group gives rise to a commutativity graph by defining $x \,\bot\, y \iff xy=yx.$ Does every ...
108 views

### Software for generating Cayley graphs of $\mathbb Z_n$?

Does it exist any program (for linux) which can generate a nice Cayley graph of any $\mathbb Z_n$? (If it's possible to create such a graph at all, that is.) (where perhaps $n ≤ 100$ or something ...
51 views

### Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
93 views

### A connection between nonplanar complete graphs and the alternating group?

I went to an undergrad's senior honors thesis presentation a few days ago. She was discussing crossing numbers and mentioned that complete graphs $K_n$ are nonplanar iff $n \geq 5$. ?Coincidentally? ...
54 views

### Caley graphs of gruops and symmetric generating sets

There are several examples (of which Wikipedia show at least one) when the Caley graph (G,U) of a group G (where U generates the group) depend on the choice of generating set. Is requiring that the ...
46 views

### The automprphism group of the complete binary rooted tree height 3

Can someone give me some help with this problem: How do I find the automorphism gruop of the complete binary rooted tree height 3 (15 vertices)? when an automorphism F on a graph G=(V,E) is defined ...
721 views

### Painting a cube with 3 colors (each used for 2 faces).

A cube is about to get fully painted using $3$ different colors. Each color is being used for $2$ faces of a cube. How many different cubes can be created this way? I saw this in a fifth ...
131 views

### When is round-robin scheduling possible and with in minimal time?

Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five ...
66 views

### References request: which semigroups give Cayley graphs which are different from the Cayley graphs given by groups?

I would like to know which semigroups give Cayley graphs which are different from the Cayley graphs given by groups. Are there some references? For example, do the Cayley graphs of complete simple ...
95 views