Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Which full bipartite ($K_{r,s}$) and 3-partite ($K_{r,s,t}$) graphs are eulerian/hamiltonian graphs?

What I have found so far:

  1. bipartite/eulerian $\rightarrow 2|r \land 2|s$
  2. $3$-partite/eulerian $\rightarrow 2|r \land 2|s \land 2|t$
  3. bipartite/hamiltonian $\rightarrow r=s$
  4. $3$-partite/hamiltonian $\rightarrow s=r+t$ (and symmetric cases) or $ s=r+t + 1$

Shortly speaking:

$1.$ and $2. $ is a result of the fact that graph has eulerian cycle $\leftrightarrow$ $2|deg(v)$ $ v\in V(G)$

$3.$ and $4.$ we have $k$-partite graphs so when we go to one part, we must be able to return.

Do you agree with that?

share|improve this question
1  
Counterexample to your condition 2) $\forall v\in V(K_{3,3,3}), \,\, 2|\text{deg(v)} \quad \implies \quad K_{3,3,3} \, \text{ is eulerian}$ –  Stano Apr 20 '13 at 12:57
add comment

2 Answers 2

up vote 1 down vote accepted

A graph is eulerian iff all its vertex degrees are even. For a complete 3-partite graph $K_{r,s,t}$, this is true if $r + s$, $r+t$, and $s+t$ are all even, which happens iff $r$, $s$, and $t$ are all the same parity.

Ore's theorem implies that a complete 3-partite graph is always hamiltonian unless one part has more than half the vertices. The converse also holds in this case.

share|improve this answer
add comment

1) is OK
2) incorrect - $K_{3,3,3}$ is eulerian
3) is OK
4) incorrect - $K_{2,3,5}$ is hamiltonian but don't hold your conditions.
Use Dirac's theorem:
$$(V(G)\geq3) \wedge \left(\forall v\in G: deg(v)\geq\frac{V(G)}{2} \right) \implies G \text{ is hamiltonian}$$ and next try to show that it is also sufficient condition.

share|improve this answer
1  
$K_{2,3,5}$ does satisfy his conditions, since 5 = 2 + 3. But $K_{2,2,2}$ is hamiltonian, and does not. –  Kundor Apr 20 '13 at 18:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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