All Questions
Tagged with finite-groups graph-theory
47 questions
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 12.7k
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
4
votes
1
answer
421
views
Visualizing the elements of a finite group and does the Gram matrix determine the finite group?
Let $G$ be a finite group with $n = |G|$ elements. By Cayley's theorem for finite groups, we have an injective homomorphism of groups:
$$
\pi : G \rightarrow S_n, \quad g \mapsto \pi(g)
$$
where ...
- 5,409
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
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
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
7
votes
1
answer
337
views
Lovasz's conjecture for dihedral Cayley graphs
Background:
A tantalizing conjecture of Lovasz is the following:
Let $G$ be a (finite) connected vertex-transitive graph. Then $G$ contains a Hamiltonian cycle or is one of $5$ counter-examples.
(...
- 673
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
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
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,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
4
votes
2
answers
485
views
Transposition Cayley graphs are planar
Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13)...
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
32
votes
9
answers
5k
views
How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?
Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...
- 14k
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
1
vote
1
answer
286
views
Automorphism group of a graph
Suppose $\Gamma$ is a simple graph and $G=\mathrm{Aut}(\Gamma)$ is the automorphism group of $\Gamma$. If $G$ stabilizes a subgraph $\Gamma_1$,, and $G_0$ is the point-wise stabiliser of the set $V(\...
- 6,051
0
votes
1
answer
95
views
DCI-properties of Cayley graphs
A Cayley graph (resp. digraph) $Cay(G,S)$ is called a $CI$-graph (resp. $DCI$-graph) of $G$ if, for any Cayley graph (resp. digraph) $Cay(G, T)$, whenever $Cay(G,S) \cong Cay(G, T)$ we have $S = T^\...
- 3,911
20
votes
4
answers
2k
views
What algebraic structures are related to the McGee graph?
Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes.
The ...
- 2,902
26
votes
3
answers
3k
views
What is this subgroup of $\mathfrak S_{12}$?
On some occasion I was gifted a calendar. It displays a math quizz every day of the year. Not really exciting in general, but at least one of them let me raise a group-theoretic question.
The quizz: ...
- 52.3k
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
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
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
3
votes
3
answers
333
views
Mclaughlin Graph
how can i construct a strongly regular graph with parameter $(275,112,30,56)$(Mclaughlin Graph), (105,32,4,12)?
I need adjacency matrix of them?
I know they are unique.
- 1,197
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
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
1
vote
1
answer
155
views
Max order for which connected Cayley Graphs are known to be Hamiltonian
There is a well-known conjecture that all connected Cayley graphs are Hamiltonian.
For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?
- 3,291
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
12
votes
3
answers
1k
views
"Antipodal" maps on regular graphs?
This question is related to Realizing the diameter of a finite regular graph
Let $X=(V,E)$ be a finite, connected, regular graph of diameter $D$. Assume that, for every vertex $x\in V$, there exists ...
CommunityBot
- 1