3
votes
1answer
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 ...
1
vote
0answers
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}$ ...
4
votes
1answer
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 ...
0
votes
1answer
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, ...
2
votes
0answers
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: ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
0answers
46 views

About Network Dynamics

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 ...
6
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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?
0
votes
1answer
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, ...
3
votes
1answer
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$ ...
1
vote
1answer
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 ...
4
votes
4answers
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?
3
votes
2answers
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) ...
3
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
7
votes
0answers
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? ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
5answers
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 ...
2
votes
3answers
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 ...
4
votes
1answer
95 views

Determining the automorphism group of a disconnected graph

There is this know formula for determining the automorphism group of a graph $G$: let the connected components of $G$ consist of $n_1$ copies of $G_1$, $\dots$, $n_r$ copies of $G_r$, where $G_1, ...
2
votes
1answer
100 views

Meaning of Fundamental group of a graph

I am a computer science student working in graph algorithms. I am unable to understand what the fundamental group of a graph means. I have some intuition regarding the fundamental group of a ...
0
votes
1answer
64 views

graphs and groups

In many papers we see a group which is constructed a graph from it and captures some information about the group. There are several ways of doing this, non-commuting graph, power graph, cayley ...
0
votes
0answers
27 views

Isomorphism of complete DAG corresponding to group action on group ordering.

Label the complete directed acyclic graph nodes with elements of a group of size $|V|$ where $V$ is the set of vertices. This graph represents a total ordering $\lt$ of the group minus antisymmetry. ...
3
votes
1answer
132 views

Number of isomorphism classes of countable models of a theory

Whether there are countably or uncountably many isomorphism classes of countable models of a given theory depends on the theory: if the theory is strong enough, there will be only countably many ...
3
votes
1answer
89 views

Automorphism groups of self-complementary graphs

Does every self-complementary graph has a non-trivial automorphism group?
1
vote
1answer
133 views

Graph (or Group) in Astronomy

Is there an application of graph theory (or group theory) in astronomy. If there is, refer me some references.
3
votes
0answers
65 views

Automorphism group for a family of bigraphs

Extend the sides of a regular polygon on 2m vertices, m ≥ 2, to define the 2m(m - 1) finite points of intersection. Circumscribe a centrally symmetric circle large enough all of the points of ...
0
votes
2answers
81 views

non-Hamiltonian Cycles: How to Prove for Small Graphs

How do I prove that the following graph is a non-Hamiltonian cycle? $\hspace{5.3cm}$ I'm asked to create a graph which is both non-Eulerian and non-Hamiltonian, and this is what I produced in TiKz. ...
1
vote
0answers
102 views

Is the prime graph of a solvable group also the prime graph of some nonsolvable group?

Let $G$ be a solvable group. Does a nonsolvable group exist whose prime graph is isomorphic to the prime graph of $G$?
4
votes
2answers
98 views

How to understand the automorphism group of a very symmetric graph (related to sylow intersections)

For a group $G$ and subgroup $H$, consider the relation on $G$ defined $x \sim y$ if $H^x \cap H^y = 1$. This defines a graph on $G$. It is always fairly symmetric: $N_G(H)$ acts on the left and $G$ ...
4
votes
2answers
173 views

Can any finite group be realized as the automorphism group of a directed acyclic graph?

We are given a finite group $G$ and wish to find a DAG (directed acyclic graph) $(V,E)$ whose automorphism group is exactly G (a graph automorphism of a graph is a bijective function $f:V\to V$ such ...
5
votes
2answers
182 views

Using the orbit-stabilizer theorem to count graphs

Revising for a course in group and representation theory, I have come across the following interesting problem: Use the orbit-stabilizer theorem to compute the number of isomorphism classes of ...
1
vote
0answers
50 views

A family of $8$-regular Ramanujan Cayley Graphs

I'm looking for expander graphs with certain properties. Is there a family of $8$-regular Ramanujan Cayley graphs $\{\text{Cay}(G_n,S_n)\}_n$ such that each of them has no cycles of odd length? ...
1
vote
2answers
64 views

Can we get the line graph of the $3D$ cube as a Cayley graph?

Given a graph $G=(V,E)$, the line graph of $G$ is a graph $\Gamma$ whose vertices are $E$ (the edges of $G$) and in $\Gamma$, two vertices $e_1,e_2$ are connected if, as edges in $G$, they share an ...
2
votes
1answer
202 views

Number of edge colorings in a tetrahedron with three colors. Is my solution correct?

I've tried to count rotationally distinct edge colorings (both proper and improper) in a regular tetrahedron with three colors. Could you take a look if it's correct? First the improper colorings. ...
1
vote
1answer
89 views

Is this graph coloring problem solved correctly?

On this Wikipedia page about Burnside's lemma, it is calculated that there are 57 rotationally distinct colorings of the faces of a cube with three colors. I'm confused by the way it is done. They ...