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.
- Janusz Adamus
- 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
- Received: 2008-09-07.
- Revised: 2009-07-20.
- Accepted: 2009-08-02.
