All Questions
Tagged with finite-groups graph-theory
19 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
4
votes
0
answers
95
views
Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?
What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?
- 197
3
votes
0
answers
51
views
Asymptotic dimension of graph families representing each finite group
Frucht's theorem says every finite group is isomorphic to the automorphism group of a simple graph $G$ (with no loops, multiple edges or directed edges).
There has been interest in finding classes of ...
- 1,926
3
votes
0
answers
70
views
Hamilton cycles in Cayley graphs: between Rapaport-Strasser and Fleischner
A well-known question of Rapaport-Strasser asks whether every finite connected Cayley graph has a Hamilton cycle. Fleischner's Theorem implies that if $S$ is the generating set of such a Cayley graph $...
- 1,926
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
85
views
G graph connections for finite groups G
In my research, I have seen G graph connections usually when G is a Lie group and the graph is the fatgraph of a (punctured) surface. This is usually in a physics context. However, I am curious to ...
- 495
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
112
views
What is $H^*(\mathbb{CP}^{2^N-1}/\Sigma_n;\mathbb{Z})$ when $N=\binom{n}{2}$?
$H^*((S^3)^N/\Sigma_n;\mathbb{Q})$ is computed here.
It makes a little more sense to compute $H^*((S^2)^N/\Sigma_n;\mathbb{Q})$ given that global phase is irrelevant. The proof is exactly the same.
...
- 571
1
vote
0
answers
80
views
Are these maps, associated to finite simple graphs, interesting?
Given a finite simple graph on $n$ vertices, say $G = (V,\, E)$, where
$$ V = \{ v_1, \ldots , \, v_n \} $$
and
$$ E \subseteq \{ (v_a, \, v_b) \, | \, 1 \leq a < b \leq n \},$$
does there exist a ...
- 5,215
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
0
votes
0
answers
101
views
Eigenvalues of the Cayley-like graph
Let $ F_q $ be a finite field of characteristic 2.
Let $ x^2 + Sx +P \in F_q[x] $ be an irreducible polynomial over $ F_q $,
and let $ g $ be one of its roots in $ F_{q^2} $.
Define a map $ M: F_{q^2}...
- 503
-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