All Questions
10 questions
34
votes
9
answers
7k
views
Applications of infinite graph theory
Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the ...
- 349
20
votes
3
answers
991
views
Does the hypergraph of subgroups determine a group?
A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
- 48.9k
19
votes
4
answers
973
views
Are there Hamilton paths in Cayley graphs of Coxeter groups?
Hi everyone.
I want to optimize certain computation on finite Coxeter groups $(W,S)$. Basically I compute the matrices $\rho(T_w)$ for all $w\in W$ of a matrix representation $H\to K^{d\times d}$ of ...
- 9,650
8
votes
2
answers
950
views
Which 3-regular graphs are Schreier coset graphs?
Given a group $G$ and a subgroup $H$ the Schreier coset graph (w.r.t. some set $S$ of $G$) is the directed (and labelled) graph whose vertices are the cosets of $H$ (i.e. the set $G/H$) and $x \sim y$ ...
- 4,432
15
votes
1
answer
1k
views
Is there a group whose cardinality counts non-intersecting paths?
Introduction
Graphs are not only important combinatorial objects, but also related to many topological/algebraic structures. In this question I am going to talk about various group structures with ...
- 85.6k
11
votes
1
answer
302
views
Infinite vertex-transitive graph where every automorphism has a fixed vertex
This is a follow-up to the question Connected vertex-transitive graph with the fixed-point property. In particular, it is based on a comment by user bof.
Let $G = (V,E)$ be a graph with $V$ infinite. ...
- 24.2k
9
votes
1
answer
356
views
Diameter of the modified bubble-sort graph
The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...
- 406
7
votes
1
answer
285
views
When is a Schreier coset graph vertex transitive
When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive?
It is well known that when $H$ is normal, the Schreier coset graph ...
- 2,089
5
votes
0
answers
267
views
(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples
Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
- 3,612
2
votes
0
answers
41
views
Complexity of computing the automorphism group of the subdivision of clique with leaves
Related to graph isomorphism.
Consider the graph transformation $G$ to $G'$.
Make a clique of $V(G)$ and subdivide each edge once, i.e.
replace edge $(u,v)$ with path $(u,S_{uv},v)$.
For all edges $(...
- 25.4k