Hamiltonian cycle containg selected sets of edges of a graph

• Authors: Grzegorz Gancarzewicz
• Languages of publication: EN

Abstracts

EN

The aim of this paper is to characterize for every k ≥ 1 all (l + 3)-connected graphs G on n ≥ 3 vertices satisfying P(n + k): for each pair of vertices x and y in G, such that there is a path system S of length k with l internal vertices which components are paths of length at most 2 satisfying: such that S is not contained in any hamiltonian cycle of G.

Keywords

EN

Cycle; hamiltonian cycle; matching; path

Discipline

• INFORMATICS: INFORMATICS

• Publisher: Scientific Publishing House „DARWIN”
• Journal: World Scientific News
• Year: 2016
• Volume: 57
• Pages: 276-287

Contributors

author

Grzegorz Gancarzewicz

• Institute of Mathematics,Tadeusz Kościuszko Cracow University of Technology, 24 Warszawska Str., 31-155 Cracow, Poland

References

• [1] J. A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-135.
• [2] J. A. Bondy and U.S.R. Murty, Graph theory with applications, MacMillan Press LTD, 1976.
• [3] G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221-227.
• [4] G. Gancarzewicz and A. P. Wojda, Graphs with every k-matching in a hamiltonian cycle, Discrete Math. 213(1-3) (2000) 141-151.
• [5] H. V. Kronk, Variations of a theorem of pósa, in The Many Facets of Graph Theory, ed. G. Chartrand and S.F. Kapoor, Lect. Notes Math. 110 (1969) 193-197.
• [6] O. Ore, Note on hamiltonian circuits, Amer. Math. Monthly 67 (1960) 55.
• [7] Z. Skupień and A. P. Wojda, On highly hamiltonian graphs, Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 22 (1974) 463-471.
• [8] M. Las Vargnas, Sur une propriété des arbres maximaux dans un graphe, C. R. Axad. Sci. Paris, Sér. A 272 (1971) 1297-1300.
• [9] A. P. Wojda, Hamiltonian cycles through matchings, Demonstratio Mathematica XXI(2) (1983) 547-553

• Document Type: article