Mathematical Research Seminar - Archive

An undirected graph G d-degenerate if every subgraph of G has a vertex of degree at most d, and the degeneracy is the minimum d such that G is d-degenerate. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d+1. But can we decide in polynomial time whether a graph contains a cycle of length at least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete.  Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected.  In this case we prove that    deciding whether G contains a cycle of length at least d+k can be done in time 2^{O(k)}|V(G)|^{O(1)}.  Further, we briefly consider similar problem arising from the classical result of Dirac from 1952 that every 2-connected n-vertex graph has a cycle with at least min{2\delta(G),n} vertices. 

The talk is based on the joint work with Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi, Danil Sagunov, and Kirill Simonov.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

It is known that a Cayley digraph $\Cay(A,S)$ of an abelian group $A$ is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $B\le A$ such that $S\setminus B$ is a union of cosets of $B$ in $A$. We generalize this result to Cayley digraphs $\Cay(G,S)$ to nonabelian groups $G$ by showing that such a digraph is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $H\le G$ such that $S\setminus H$ is a union of double cosets of $H$ in $G$. This result is proven in the more general situation of a double coset digraph (also known as a Sabidussi coset digraph.) We then give applications of this result which include showing the problem of determining automorphism groups of vertex-transitive digraphs is equivalent to the problem of determining automorphism groups of Cayley digraphs, and extending the definition of generalized wreath product digraphs to double coset digraphs of all groups $G$.

Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.