All Questions
28 questions
12
votes
1
answer
1k
views
Necessary and sufficient conditions for the Cayley graph to be bipartite
Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=\operatorname{Cay}(G, S)$ is a ...
- 12.9k
-1
votes
1
answer
215
views
Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques
Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
CommunityBot
- 1
1
vote
0
answers
221
views
A connection between nonplanar complete graphs and the alternating groups?
I didn't get any response on MSE so I though I'd give this a try here (my question on MSE).
I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...
- 1,093
2
votes
0
answers
53
views
Can a polytope with vertex-transitive edge graph or face lattice be made vertex-transitive?
Let $P\subset\Bbb R^d$ be a convex, full-dimensional polytope (convex hull of finitely many points, affine hull is the whole space), $G_P$ its edge graph and $\mathcal F_P$ its face lattice. Any of ...
CommunityBot
- 1
2
votes
1
answer
172
views
Examples of 3-transitive expander family of Schreier graphs
What are examples of expander family of 3-transitive Schreier graphs?
Meaning for an action that is 3-transitive.
It is better to have an option for randomization. We know that choosing 2 elements ...
- 340
5
votes
2
answers
567
views
Orbits of independent sets of the hypercube
How does one enumerate the distinct orbit classes of independent sets of the hypercube modulo symmetries of the hypercubes?
The counting of the number of independent sets in an $n$-dimensional ...
- 63.9k
5
votes
1
answer
385
views
$C_4\times C_2 : C_2$: what does this mean?
I am reading this paper where the object $C_4\times C_2 : C_2$ is used as a group structure. I know that $C_n$ is a cyclic group but don't know what kind of operation between groups is identified by ...
- 6,367
7
votes
1
answer
276
views
Groups and graphs
Let $A=(V, E)$ be a finite simple (no loops or multiple edges) graph. Let $G(A)$ be the following nilpotent group of class 2 and exponent $p$ (an odd prime). $G(A)$ as a set is $span(V)+span(E)$ ...
- 37.4k
5
votes
1
answer
275
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
- 63.9k
2
votes
0
answers
202
views
Expander graphs with many 4-cycles
The question is not strictly well-defined. But it goes like this:
Could you find an infinite family of graphs $G_i$, that are all $\epsilon$-expanders, but have many 4-cycles?
$\epsilon$ should ...
- 63.9k
3
votes
0
answers
56
views
Groups that can occur as graph automorphisms of a fixed size graph
From theorem $4$ and corollary $1$ in this book we have that graph isomorphism has to do with automorphism group of a graph. We also know every group is the automorphism group of a graph by Frucht's ...
CommunityBot
- 1
0
votes
0
answers
72
views
Isomorphism of finite groups and cycle graphs
Let $G$ and $H$ be finite groups and suppose they do have the same cycle graph. Is it possible to argue that this implies $G$ and $H$ are isomorphic? If yes, why? If not, is there an explicit ...
- 489
11
votes
4
answers
1k
views
Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley graph of any abelian group?
It's the first question I post here :) I'm sorry if the question is too specific or if it's somehow repeating others.
In other words, my question is the following. Consider a Cayley graph $\Gamma$ of ...
- 4,713
12
votes
2
answers
1k
views
Graph automorphism group
Let $A_w$ denote such set of positive integer $n$ that: for any two permutations $\pi_0,\pi_1\in S_n$, if $\pi_1$ is not a power of $\pi_0$, then there exists a (labeled non oriented) graph $G$ of ...
- 6,051
2
votes
0
answers
54
views
Is it possible to characterize all finite groups $G$ whose coprime graph contains precisely three or precisely four leaves?
Is it possible to characterize all finite groups $G$ whose
coprime graph contains precisely three or precisely four leaves?
In section 3 of X. Ma, H. Wei, and L. Yang, The coprime graph of a group, ...
- 6,051
2
votes
0
answers
140
views
About the eigenvectors of a matrix related to a Cayley graph
In some papers about the cayley graphs of finite groups the behaviour of the eigenvalues and eigenvectors of $\phi$ were discussed when $\phi=\sum_{g\in G} \lambda_G(g)$ and $\lambda_G(g)$ is defined ...
- 33.8k
4
votes
0
answers
215
views
Words Growth in Finite Groups
Let $G$ be a finite group with a set of generators and let $\Gamma$ be its Cayley Graph. Let $b_k$ be the number of elements in the ball of radius $k$. I am interested in what is known about the ...
- 5,450
3
votes
0
answers
164
views
Generating sets of the symmetric group that yield isomorphic Cayley graphs
Let $S$ and $S'$ be subsets of size $k$ of $\mathfrak{S}_n$.
Are there any necessary or sufficient conditions to determine whether or not $S$ and $S'$ yield isomorphic Cayley graphs?
Assuming we ...
- 63.9k
17
votes
5
answers
709
views
Cayley graphs of $A_n.$
Consider the Cayley graphs of $A_n,$ with respect to the generating set of all $3$-cycles. Their properties must be quite well-known, but sadly not to me. For example: what is its diameter? Is it an ...
CommunityBot
- 1
8
votes
2
answers
1k
views
Are vertex and edge-transitive graphs determined by their spectrum?
A graph is called vertex and edge transitive if the automorphism group is transitive on both vertices and edges.
The spectrum of a graph is the collection (with multiplicities) of eigenvalues of the ...
- 2,446
2
votes
0
answers
187
views
Classification of Automorphism set of a Regular graph
Let $A$ be the adjacency matrix of an $r$-regular graph $G$ with $n$ vertices (Not complete or cycle graph) . Also, let $Aut(G)$ be the set of all its automorphisms (i.e. set of permutation matrices)....
CommunityBot
- 1
1
vote
1
answer
178
views
Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?
Feedback vertex set is a set of vertices whose removal leaves an acyclic graph.
It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...
- 56
10
votes
1
answer
906
views
Which finite groups are not the automorphism group of some rooted finite tree?
The question is as given in the title:
Which finite groups are not the automorphism group of some rooted finite tree?
A rephrasing could be: Is any finite group representable as the automorphism ...
- 6,210
9
votes
2
answers
432
views
Vertex-primitive graphs with two vertices having almost the same neighbourhood
Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$
Question: Is it true that $\Gamma$ must either be a complete graph or have ...
- 3,291
7
votes
1
answer
517
views
Paths in groups
Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...
- 23k
4
votes
2
answers
213
views
Are the following Cayley digraphs Hamiltonian?
Consider the Cayley graphs $A'G_n$ on the alternating group $A_n$ with generating set $S = \{(1i2) : 3 \leq i \leq n\}$, for $n \geq 4$.
See the following page on Alternating Group Graphs for ...
- 15.4k
4
votes
2
answers
1k
views
Automorphism group action leads to a "quotient graph"
Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.
Define a new ...
- 747
17
votes
0
answers
512
views
Maximum automorphism group for a 3-connected cubic graph
The following arose as a side issue in a project on graph reconstruction.
Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a ...
- 37.7k