Edge condition for hamiltonicity in balanced tripartite graphs

• Autorzy: Adamus J.
• Języki publikacji: EN

Abstrakty

EN

A well-known theorem of Entringer and Schmeichel asserts that a balanced bipartite graph of order 2n obtained from the complete balanced bipartite Kn,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.

Słowa kluczowe

EN

Hamilton cycle; pancyclicity; tripartite graph; edge condition

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2009
• Tom: Vol. 29, no. 4
• Strony: 337--343
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Adamus J.

• The University of Western Ontario, Department of Mathematics, London, Ontario N6A 5B7 Canada,

Bibliografia

• [1] J.A. Bondy, Pancyclic graphs I, J. Combinatorial Theory B 11 (1971), 80–84.
• [2] G. Chen, R.J. Faudree, R.J. Gould, M.S. Jacobson, L. Lesniak, Hamiltonicity in balanced k-partite graphs, Graphs and Combinatorics 11 (1995), 221–231.
• [3] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 3 (1952) 2, 69–81.
• [4] R.C. Entringer, E. Schmeichel, Edge conditions and cycle structure in bipartite graphs, Ars Combinatoria 26 (1988), 229–232.
• [5] K. Yokomura, A degree sum condition on hamiltonian cycles in balanced 3-partite graphs, Discrete Math. 178 (1998), 293–297.