All Questions
12 questions with no upvoted or accepted answers
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
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
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 ...
- 13.9k
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 ...
- 1,164
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 ...
- 13.6k
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 ...
- 340
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, ...
- 1,755
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 ...
- 21
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)....
- 267
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,197
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
-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$. ...
- 2,089