All Questions
54 questions
3
votes
0
answers
126
views
Finite approximability of graphs with finitely many automorphisms
In this question, all graphs are understood to be simple and undirected, and have countably many vertices and edges, but not necessarily finite.
Let $G = (V, E)$ be a graph. It is clear that any ...
- 2,830
1
vote
0
answers
55
views
Possible variant of Lovász: Graphs without 3 vertex-disjoint cycles
Is there a classification, or perhaps some exhaustive description, of graphs without 3 vertex-disjoint cycles,
and/or do you maybe know about some reference for such?
The case of graphs without 2 ...
- 11
-2
votes
2
answers
217
views
Must an isomorphism preserving graph transformation preserve the order of the automorphism group?
Let $F$ be some function graph to graph which preserve graph isomorphism.
Example of such $F$ are the line graph, the $k$-subdivision of $G$
and many others.
$F$ need not preserve the order, the ...
- 25.4k
2
votes
2
answers
234
views
Decompose complete directed graph with n vertices into n edge-disjoint cycles with length n−1
I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in Bermond and Faber - Decomposition of the ...
- 21
4
votes
1
answer
465
views
Turán's theorem for cosets of groups
Let $G$ be a finite group, $G',H$ be its subgroups and $H'=G'\cap H$. For each $g\in G$, we create a map $f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$. It's easy to see that the map is well defined ...
- 1,462
7
votes
0
answers
325
views
Groups of non-orientable genus 1 and 2
The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...
- 185
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
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
7
votes
1
answer
216
views
Automorphism group of a putative strongly regular graph
The smallest feasible parameters for which no strongly regular graph is known to exist are $(69,48,32,36)$, as per Brouwer's table. What is known on the automorphism group of such a graph?
- 221
4
votes
2
answers
292
views
Can every involution of a symmetric directed graph be written as a power of another symmetry?
Let $D=(V,A)$ be a finite directed graph, and suppose that
$D$ is vertex-transitive,
$D$ is edge-transitive, and
between any two vertices there is at most one edge, in particular, if $(v,w)\in A$ ...
- 13.6k
2
votes
1
answer
181
views
Generators of sandpile groups of wheel graphs
In the paper "On the Sandpile Group of a Graph" by Cori and Rossin one can find a result related to the structure of the sandpile group of $W_n$. Is there a way to provide a set of ...
- 298
-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
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
3
votes
0
answers
325
views
Intuitive, elementary intros to Hopf algebras/monoids
Motivation:
I'm interested in understanding the role that noncrossing partitions play in Hopf algebras/monoids (HAs) as the components of the power series of the compositional inverse of formal ...
- 10.5k
1
vote
0
answers
93
views
Generating graphs of groups
Suppose $G$ is a group and $S \subset G$ is its finite subset. Let’s define the generating graph of $G$ in respect to $S$ as $Gen(G, S)$ - a graph $\Gamma(V, E)$, where $V = S$ and $E = \{(a, b) \in S ...
- 2,618
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$ ...
- 237
1
vote
1
answer
82
views
The complexity on calculation of the Graev metric on the free Boolean group of a metric space
For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be ...
- 41.8k
7
votes
2
answers
415
views
Graph which do not satisfy a pseudo-Poincaré inequality
Say that an infinite (connected) graph (with vertices of bounded degree) satisfies a $\ell_1$-pseudo-Poincaré inequality if there is a constant $C>0$ so that for any $n \in \mathbb{N}$ for any ...
- 4,432
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
0
votes
2
answers
152
views
coloring infinite vertex transitive graph without large cliques
Let $G$ be an infinite vertex-transitive graph (this means that for every $u,w \in V(G)$ there exists an automorphism $\tau$ of $G$ such that $\tau(u) = v$).
We assume that $G$ is undirected, and does ...
- 11.3k
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 ...
- 909
9
votes
2
answers
454
views
How to characterize "matching-transitive" regular graphs?
I am interested in regular graphs $G$ such that for each pair of 1-factors (=perfect matchings) $F$ and $F'$ there is an automorphism of $G$ that takes $F$ to $F'$. Let's call this property matching ...
- 13.4k
10
votes
1
answer
269
views
Edge-transitive Cayley graphs of $S_n$
I came across the following question which I haven't seen before:
Question. Fix $k\ge 3$. For infinitely many $n$, does there exists a generating set $\langle R_n \rangle = S_n$, $|R_n|=k$, such ...
- 17k
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
13
votes
1
answer
409
views
When is the union of a graph and a random permutation thereof connected?
First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and ...
- 20.2k
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
9
votes
1
answer
339
views
Finite and infinite 4-regular vertex-transitive graphs with identical $R$-balls
Consider the set of all 4-regular connected vertex-transitive graphs.
By compactness, for every integer $R \ge 0$, there is an integer $N_R$, so that for every 4-regular vertex-transitive graph of ...
- 91
5
votes
0
answers
163
views
Graphs quasi-isometric to a plane
Suppose that a planar graph $\Gamma$ is quasi-isometric to the Euclidean plane. Is it true that the growth function $g(r)$ of $\Gamma$ with respect to any vertex $o$ (that is $g(r)$ is the number of ...
user6976
4
votes
1
answer
207
views
A spectral graph theory problem
Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, ...
- 51
2
votes
1
answer
172
views
Number of eigenvalues of a Cayley graph
Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...
- 21
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
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 ...
- 197
0
votes
0
answers
106
views
When is edge colored circulant isomorphism polynomial?
Don't understand enough group theory, but two papers
appear to give partial results about an open problem.
Edge colored graph isomorphism is isomorphism which
preserves the edge coloring (the ...
- 25.4k
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
1
vote
2
answers
268
views
Cubic Cayley (undirected) graphs
The generators of a cubic Cayley graph always include at least one involution, since 3 is odd. There are then two possibilties for the other two generators: either (A) they are also (distinct) ...
- 3,612
5
votes
1
answer
282
views
Duration and critical groups order in sandpile models and chip firing games
The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least $d_{v}...
- 6,962
2
votes
0
answers
120
views
When polynomial GI implies polynomial (edge) colored GI?
(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...
- 25.4k
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 ...
- 17.6k
2
votes
1
answer
87
views
Commensurability of 2-colorings of finite 4-valent graphs
It is quite easy to show that given two finite 4-valent graphs $X,X'$ (I will take the convention that there is at most one edge between two vertices, but allow loops) there is a third such graph $X''$...
- 3,399
8
votes
2
answers
478
views
Embedding of a "quotient graph"
Consider the simple undirected graph $G$ with natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff they are similar, i.e. iff there exists $\phi\in Aut(G)$ with $\phi(u)=v$.
Define a "...
- 747
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
4
votes
0
answers
209
views
Rough structure of the double coset space/Graph bijections up to automorphisms
I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...
- 679
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
14
votes
2
answers
738
views
Finite vertex-transitive graphs that look like infinite vertex-transitive graphs
For a vertex-transitive graph $G$ and a positive integer $d$, and let $G(d)$ be the subgraph induced by all vertices of $G$ within distance $d$ of some given vertex $v$ (since $G$ is vertex-transitive,...
- 143
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 ...
- 1,306
9
votes
1
answer
397
views
When does a `distinguished matching' exist?
Suppose I have a bipartite graph on a pair of vertex sets $X$ and $Y$.
Definition: A distinguished matching is a subset $DX\subseteq X$ and a subset $DY\subseteq Y$ such that:
For all $y\in Y$, ...
- 11.2k
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 ...
- 171
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
6
votes
3
answers
494
views
Tutte polynomials of appropriate Cayley graphs
I was quite intrigued by Tutte polynomials in a recent talk I had been to. It was introduced as a polynomial associated to a undirected finite graph. For a graph $G=(V,E)$ we form the polynomial
$T_G(...
- 3,423
2
votes
4
answers
1k
views
Automorphism Group of Paley Graph
Hello all,
I would like an explanation as to the structure description of the automorphism group of a Paley graph.
Paley graphs are a specific case of Cayley graphs where the group is $Z_q$ (q is a ...
- 163