Opuscula Math. 29, no. 4 (2009), 337-343
http://dx.doi.org/10.7494/OpMath.2009.29.4.337

Opuscula Mathematica

# Edge condition for hamiltonicity in balanced tripartite graphs

Abstract. A well-known theorem of Entringer and Schmeichel asserts that a balanced bipartite graph of order $$2n$$ obtained from the complete balanced bipartite $$K_{n,n}$$ by removing at most $$n-2$$ edges, is bipancyclic. We prove an analogous result for balanced tripartite graphs: If $$G$$ is a balanced tripartite graph of order $$3n$$ and size at least $$3n^2-2n+2$$, then $$G$$ contains cycles of all lengths.

Keywords: Hamilton cycle, pancyclicity, tripartite graph, edge condition.

Mathematics Subject Classification: 05C38, 05C35.

Full text (pdf)

• The University of Western Ontario, Department of Mathematics, London, Ontario N6A 5B7 Canada
• Jagiellonian University, Institute of Mathematics, ul. Łojasiewicza 6, 30-348 Kraków, Poland
• Revised: 2009-07-20.
• Accepted: 2009-08-02.