In 1976, Bondy and Chvátal [Discrete Math. 1976] introduced the notion of closure of a graph: let $\ell$ be an integer; the $(n+\ell)$-closure, $cl_{n+\ell}(G)$, of a graph $G$ with $n$ vertices is obtained from $G$ by recursively adding an edge between pairs of nonadjacent vertices whose degree sum is at least $n+\ell$ until no such pair remains.
A graph property $\Upsilon$ defined on all graphs of order $n$ is said to be $(n+\ell)$-stable if for any graph $G$ of order $n$ that does not satisfy $\Upsilon$, the fact that $uv$ is not an edge of $G$ and that $G+uv$ satisfies $\Upsilon$ implies $d(u)+d(v)< n+\ell$.
The degeneracy of a graph $G$ is the least $k$ such that every induced subgraph of $G$ contains a vertex with degree at most $k$.
In this talk, we present an algorithmic framework based on the notion of Bondy and Chvátal closures to deal with the degeneracy of the complement graph, called co-degeneracy, as a parameter. Using such a framework, we can show that Hamiltonian Path, Hamiltonian Cycle, and Minimum Path Cover can be solved efficiently on graphs with bounded co-degeneracy.
In addition, we show that Edge Dominating Set can also be solved efficiently on this class of graphs.
Finally, by determining the stability of the property of having a bounded cycle cover and combining our framework with some results of Jansen et al. [WG 2019], we show an efficient algorithm for Minimum Cycle Cover on graphs with bounded co-degeneracy.
These results show that co-degeneracy is a useful width parameter for handling dense instances of graph problems.
Everyone is welcome and encourage to attend.