10
$\begingroup$

Denote by $\delta^+(G)$ the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.

In a related question, I've mentioned the Ghouila-Houri extension of Dirac's theorem on Hamiltonian cycles, which suggests that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian.

In his comment, Saeed have commented on a different extension that seems stronger, except it requires the graph to be strongly connected.

The strong connectivity was proven redundant for the Ghouila-Houri theorem about 30 years after it was first published, and I was wondering if the same holds for the extension Saeed presented.

So the question is:

  1. Who proved (can anyone find the reference) that $\delta^+(G)+\delta^-(G) \geq n$ implies $G$ is Hamiltonian, given that $G$ is strongly connected?

  2. Is the strong connectivity redundant here as well, i.e. Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?


(Note that while the graph obviously has to be strongly connected for it to be Hamiltonian, I'm asking whether this condition is implied by the degree conditions).

$\endgroup$
8
$\begingroup$

The variation that I suggested was actually slightly different variation of Woodal theorem. Perhaps I saw it in the Bang-Jensen and Gutin's book. At the time that I wrote a comment I didn't check the book for correctness. So to be sure I wrote the graph should be strongly connected. BTW, that statement holds because can be interpreted as a special case of Woodal theorem. In addition does not need strongly connectivity requirement.

This is the theorem 6.4.6 from Bang-Jensen and Gutin's book:

Let $D$ be a digraph of order $n\ge 2$. If $\delta^+(x)+\delta^-(y) \ge n$ for all pairs of vertices $x$ and $y$ such that there is no arc from $x$ to $y$, then $D$ is hamiltonian.

That means the answer to the second part of your question is also Yes.

There was a doubt about that whether $n$ is a tight bound or not. Here I try to answer it. We cannot reduce the requirement of at least $n$ to $k<n$, consider the following graph. $a,b,c$ are making bidirected triangle, and $e,d$ are making a bidirected $k_2$. If hamiltonian cycle starts at $e$, it cannot go to $d$ in the next move because the only way for $d$ is using $b$ but, $b$ is the only way to back to $e$. On the other hand the Hamiltonian cycle after $e$ cannot go to $c$, because then the only back way to $e,d$ is going directly to $d$ to use $b$ in next moves, but again we are in the previous position. Also from the picture it's clear that every vertex has in and out degree at least $2$. So sum of every two arbitrary in-out is at least $4=5-1 = n-1$. We can extend these sort of graphs to arbitrary $n$.

enter image description here

P.S1: Sure the aforementioned theorem holds for simple digraphs. i.e digraphs without loop or parallel edges.

P.S2: I don't have a good Tex tool right now. So image is not good.

$\endgroup$
  • 3
    $\begingroup$ When there are only two authors, it is better to refer to them as "First and Second", rather than "First et al.", so they receive the credit they deserve. Et al. ("and others") should only be used when the full author list is long enough that reproducing it would be awkward. $\endgroup$ – David Richerby Apr 24 '14 at 15:39
7
$\begingroup$

The answer to your second question is affirmative:

If $\delta^+(G)+\delta^-(G) \ge n$ then $G$ is strongly connected

Proof: Let $G$ be a graph which is not strongly connected. We will prove that $\delta^+(G)+\delta^-(G) < n$. Write the decomposition of $G$ into strongly connected components. Let $S$ be a strongly connected component which is a sink (i.e. no edges go outside of $S$) and $T$ be a source (i.e. no edges go into $T$). Since no edges go $S$ to outside of $S$, then $\delta^+(G) \le \delta^+(S) \le |S|-1$. Similarly we get $\delta^-(G) \le |T|-1$, and taking these two things together we get $$\delta^+(G)+\delta^-(G) \le |S|+|T|-2 \le n-2 \ .$$ QED.

$\endgroup$
  • 1
    $\begingroup$ From this it seems like $\ge n-1$ is sufficient. $\endgroup$ – Geoffrey Irving Apr 24 '14 at 17:17
  • $\begingroup$ @GeoffreyIrving Yes, it seems so. $\endgroup$ – mobius dumpling Apr 25 '14 at 0:47
  • $\begingroup$ This makes me wonder if n-1 is enough for Hamiltonicity. $\endgroup$ – R B Apr 25 '14 at 14:37
  • $\begingroup$ @RB, No it's not enough. $\endgroup$ – Saeed Apr 26 '14 at 9:15
  • 1
    $\begingroup$ @RB, But I'm wonder what is the minimum number of edges for a non-hamiltonian digraph D if $\delta^-+\delta^+ = n-1$. $\endgroup$ – Saeed Apr 26 '14 at 21:51
4
$\begingroup$

This is an extension of @Mobius answer to show a stronger claim:

If $\delta^+ + \delta^- \geq n-1$, then $\forall u,v\in V, d(u,v)\leq 2$.

Proof:

If $(u,v)\in E$ we're done.

Denote $A=\{x\in V: (u,x)\in E\}, B=\{y\in V: (y,v)\in E\}$.

Notice that since $(u,v)\not \in E$, $A \cup B \subseteq V\setminus \{u,v\}$, hence $|A\cup B|\leq n-2$.

But then $$n-1 \leq \delta^+ + \delta^- \leq |A|+|B| = |A\cup B| + |A\cap B| \leq n-2 + |A\cap B|$$

And therefore $|A\cap B| \geq 1$, i.e. $\exists w\in V:(u,w),(w,v)\in E$ and $d(u,v)=2$.

$ \blacksquare$.

$\endgroup$

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.