CYCLES CONTAINING SPECIFIED EDGES IN A GRAPH

Grzegorz  Gancarzewicz

CYCLES CONTAINING SPECIFIED EDGES IN A GRAPH

Publication date: 09.02.2015

Technical Transactions, 2014, Nauki Podstawowe Issue 2 NP (16) 2014, pp. 37-43

https://doi.org/10.4467/2353737XCT.14.298.3386

Authors

Download full text

PDF

Titles

CYCLES CONTAINING SPECIFIED EDGES IN A GRAPH

Abstract

The aim of this paper is to prove that if s > 1 and G is a graph of order n > 4s + 6 satisfying
2 > (4n - 4s - 3) / 3 ; then every matching of G lies on a cycle of length at least n-s and hence, in a path of length at least n - s + 1:

Keywords

cycle, graph, hamiltonian cycle, hamiltonian path, matching, path

References

Berman K.A., Proof of a conjecture of Haggkvist on cycles and independent edges, Discrete Mathematics 46, 1983, 9—13.

Bondy J.A. and Murty U.S.R., Graph theory with applications, The Macmillan Press LTD, London 1976.

Chvátal V., On Hamilton’s ideals, J. Combin. Theory B 12, 1972, 163—168.

Häggkvist R., On F-hamiltonian graphs in Graph Theory and Related Topics, ed. J.A. Bondy and U.S.R. Murty, Academic Press N.Y. 1979 219—231.

Ore O., Note on hamiltonian circuits, Amer. Math. Monthly 67, 1960, 55.

Wojda, A.P. , Hamiltonian cycles through matchings, Demonstratio Mathematica XXI 2, 1983, 547—553.

Information

Information: Technical Transactions, 2014, Nauki Podstawowe Issue 2 NP (16) 2014, pp. 37-43

DOI: https://doi.org/10.4467/2353737XCT.14.298.3386

Article type: Original article

Titles:

Polish:

CYCLES CONTAINING SPECIFIED EDGES IN A GRAPH

English:

CYCLES CONTAINING SPECIFIED EDGES IN A GRAPH

Authors

Grzegorz Gancarzewicz

Institute of Mathematics, Cracow University of Technology

Published at: 09.02.2015

Article status: Open

Licence: None

Percentage share of authors:

Grzegorz Gancarzewicz (Author) - 100%

Article corrections:

Publication languages:

English

View count: 1524

Number of downloads: 977

<p> CYCLES CONTAINING SPECIFIED EDGES IN A GRAPH</p>

Download xml