3
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 8:16

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 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, 2014 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, 2014 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, 2014 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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