In the well studied problem of Hamiltonicity, several papers/theorems gave sufficient "degree conditions" for the existence of Hamiltonian path in a graph.

These include:

  1. Dirac's theorem , 1952, which states that "A simple (undirected) graph with $n$ vertices ($n \geq 3$) is Hamiltonian if every vertex has degree $\frac{n}{2}$ or greater".

  2. Ghouila-Houiri 's theorem, ("Une condition suffisante d’existence d'un circuit hamiltonien",1960), which generalized Dirac's result to directed graphs, showing that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian, where $\delta^+(G)$ is the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.

  3. A theorem from Bang-Jensen and Gutin's book gave a stronger result, which imply that if $\forall v\in V: d_{in}(v)+d_{out}(v)\geq n$ then the graph is Hamiltonian.

The $k$-path problem is a simple generalization of Hamiltonicity asking whether a simple path on $k$ nodes exist in a graph.

What would be the weakest sufficient "degree conditions" from a graph such that it is bound to contain a $k$-path?

  • 1
    $\begingroup$ Are you looking for conditions independent to $n$? e.g $\delta^++\delta^- > f(k)$. (I think something like Ramsey theorem works here, sure I don't know any references right now). $\endgroup$ – Saeed Aug 5 '14 at 21:00
  • $\begingroup$ @Saeed - this is exactly what I'm looking for (although $f(n,k)$ would work too), thanks. $\endgroup$ – R B Aug 5 '14 at 21:36
  • $\begingroup$ It doesn't work to lower-bound only the sum of the indegree and outdegree. Consider a complete bipartite graph $K_{n,n}$ oriented from one side of the bipartition to the other. The sum of indegree and outdegree is $n$ but the longest directed path has only two nodes. $\endgroup$ – David Eppstein Aug 5 '14 at 23:02
  • $\begingroup$ @DavidEppstein - thanks for the example. It doesn't have to be the sum of degrees, as in theorems 1,2 in the question if we can get a bound which means $d_{in},d_{out}\geq f(n,k)$ it would be interesting too. Also, it seems to me that $d_{in} + d_{out}\geq \frac{n}{2} + g(k)$ might work. $\endgroup$ – R B Aug 6 '14 at 6:35
  • $\begingroup$ Maybe $\delta^+ + \delta^-$ together with strongly connectivity condition works. e.g right now David Eppstein's counterexample works because the graph is actually weakly connected. $\endgroup$ – Saeed Aug 6 '14 at 8:16

I don't know about the weakest possible conditions, but if a graph has a subgraph with minimum degree $k-1$ (that is, if its degeneracy is at least $k-1$) then a greedy algorithm can easily find a path of $k$ nodes starting at any node. The example of $K_{k-1}$, which has no $k$-path and has minimum degree $k-2$, shows that this is tight.

  • 1
    $\begingroup$ OP's examples are more toward directed graphs, I don't know if OP also interested in undirected case (well seems we can relax your condition to get result for a directed graph but directed case is not trivial, at least for me). $\endgroup$ – Saeed Aug 5 '14 at 21:09
  • $\begingroup$ If the minimum outdegree is at least $k-1$ then the same idea works. (Or, by working backwards, indegree instead of outdegree works too.) As in the undirected case you can find a subgraph maximizing the minimum outdegree by peeling away minimum-outdegree vertices greedily. $\endgroup$ – David Eppstein Aug 5 '14 at 23:00
  • $\begingroup$ Right, then by your example the best bound till now (that we have in this answer) is $(\delta^-)\delta^+ > k-2$ and seems it's not possible to obtain something like $\delta^+ + \delta^-$ for directed case, except adding additional dependency (as R B mentioned n/2 + g(k) may works). $\endgroup$ – Saeed Aug 6 '14 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.