Problems

Problems

1. Mathematics Stack Exchange 

2. Open Problems in Graph Theory

3. Egres Open problem forum

4. Open Problems by Mohar

5. Problems by Trotter

6. Open problems in Combinatorial Group Theory

7. Bestvina's Geometric Group Theory Problem List

I'm interested in the following problems:

1. [Miraftab-Stavropoulos] Characterize all groups admitting 4-regular Cayley graphs of connectivity at most three in terms of splitting over subgroups, see here.

2. [Miraftab-Stavropoulos] Characterize all cubic quasi-transitive graphs of connectivity two in terms of tree-amalgamations, see here.

3. [Hamann-Lenher-Miraftab-Rühmann] Let G be an accessible connected quasi-transitive locally finite graph. Every process of splittings must end after finitely many steps, see here.

4. [Miraftab-Stavropoulos] Can every 4-regular Cayley graph of two-ended generalized quasidihedral group be decomposed into two disjoint hamiltonian double-rays(Hamiltonian circles)?see here. The question for hamiltonian circles has been answered  here.

5. [Georgakopoulos] 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 Cay(G,S), then by adding at most 2|S|^2 further generators (of the form \{st \mid s,t\in S\}), we can obtain a hamiltonian supergraph Cay(G,S'). What is the smallest k(n) for which you can prove that for every finite connected Cayley graph Cay(G,S) with |S|=n, there is a set T of at most k(n) elements of G, such that Cay(G,S \cup T) is hamiltonian? Conjecturally, k(n)=0, but any improvement over Fleischner's k(n)\leq 2n^2 would be nice, see here.

6. [Georgakopoulos-Miraftab] Let S be the standard generating set of the free group F_n. What is the smallest size of a generating set T containing S such that Cay(F_n,T) has a hamiltonian circle? Our guess is cn generators,  where c is a small universal constant. This has been answered  here.

7. [Miraftab-Moghadamzadeh] Algebraic flow theory of finite graphs could be extended to infinite graphs with ends for abelian Hausdorff topological groups with compact subsets. Is there any way to drop the condition "compact subsets"?

8. [Darijani-Miraftab-Witte Morris] If C_1, C_2, . . . , C_r are directed cycles (of length ≥ 2), and r ≥ 2, then the Cartesian product C_1xC_2 x· · · xC_r has two arc-disjoint hamiltonian paths, see here.

9. [Darijani-Miraftab-Witte Morris] Does there exist a function f(r) → ∞, such that every Cartesian product of r directed cycles has at least f(r) pairwise arc-disjoint hamiltonian paths? see here.

10. [Darijani-Miraftab-Witte Morris] If {a, b} is a 2-element generating set of a finite abelian group G, and a and b are nontrivial, then the directed Cay(G; a, b) has two arc-disjoint hamiltonian paths, see here.

11. [Smith] proved that every cubic graph G has an even number of Hamiltonian cycles containing a given edge e. Later Thomason suggested an algorithm for a given cubic graph G with hamiltonian cycle  that finds a second hamiltonian cycle which is an effective proof Smith's theorem. The time complexity of Thomason's algorithm is a chalenging problem. Poljak, Pudlak and Turzik constructed examples of graphs requiring \Omega(n^2) and later Chrobak and Szymacha found examples with \Omega(n^3).

12. [Miraftab]How can we find a  complete median-decomposition with a minimum tree-dimension? see here.

13. [Georgakopoulos]Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?

14. [Miraftab-Witte Morris]Which connected Cayley graphs of F_2 (or of a more general free group) admit a nowhere zero Z_4-flow? In particular, is there a connected Cayley graph of F_2 that does not admit a nowhere zero Z_4-flow, see Question 5.16 here.

15. [Miraftab-Witte Morris]Find all S, such that Cay(F2; S) is uniquely hamiltonian. (or outerplanar or hamiltonian), see here.

16. [Miraftab-Witte Morris]Is there a uniquely hamiltonian vertex-transtive graph that is not outerplanar? The answer is yes and an example provided by Florian Lehner.

17. [Miraftab-Witte Morris] Which vertex-transitive graphs with infinitely many ends have a unique hamiltonian cycle(circle)?see Question 1.19 here.

18. [Karpinsiki-Miraftab] Let X be a locally finite transitive hyperbolic graph with countable automorphism group, there is a group G of Aut(X) with transitive action on $X$ such that the action of G on the set of Gromov ends induces a hyperfinite equivalence relation.

19. [Miraftab-Petyt] is it true that every transitive hyperbolic locally finite graph is quasi-isometric to a transitive locally finite median graph?

20. [Miraftab-Rühmann] Let G be a finite group with the commutator subgroup of order p, where p is a prime number. Then Durnberger and Maru\u{s}i\u{c} proved that every  Cayley graph on G has a hamiltonian cycle. Rühmann and I conjectured that every finitely generated group with the commutator subgroup of order p has two-way hamiltonian path(hamiltonian circle), see here.

21. [Esperet, Giocanti, Legrand-Duchesne] Let G be a locally finite quasi-transitive graph. Is there an orientation of the edges of G such that the oriented graph G itself is quasi-transitive (where automorphisms have to preserve the orientation of the edges)?

22. [Maghsoudi-Miraftab-Sho] Are the following familes of graphs factorizable via Matrix Product?see here.

• Strongly regular graphs, Random graphs, Trees, Grid, Torus

23. [Miraftab] The basis number of genus 1 graphs is three.

 I can see that without being excited mathematics can look pointless and cold. The beauty of mathematics only shows itself to more patient followers.

— Maryam Mirzakhani 2008