Abstract:

Most known fundamental theorems in hamiltonian graph theory (due to Dirac, Ore, Nash-Williams, Bondy, Jung and so on) are related to the length of a longest cycle C in a graph G in terms of connectivity · and the length p of a longest path in G ¡ C, for the special cases when · · 3 and p · 1 (if p = ¡1 then V (G ¡ C) = ; and C is called hamiltonian; and if p = 0 then V (G ¡ C) is an independent set of vertices and C is called dominating). Bondy (1980) and Jung (2001) conjectured a common generalization of these results in terms of degree sums including p and · as parameters. These conjectures still are open in the original form. In 2009, the minimum degree c¡versions (c - the length of a longest cycle in V (G ¡ C)) of Conjectures of Bondy and Jung are shown to be true by the author (Discrete Math, v.309, 2009, 1925- 1930). In this paper, using another result of the author (Graphs and Combinatorics, v.29, 2013, 1531-1541), a number of analogous sharp results are presented including both p and c¡minimum degree versions of Conjectures of Bondy and Jung without connectivity conditions, inspiring a number of new strengthened and extended versions of conjectures of Bondy and Jung.
; Наиболее известные фундаментальные теоремы в теории гамильтоновости графов (авторы: Дирак, Оре, Неш-Вильямс, Бонди, Юнг и т.д.) представляют различные оценки длины длиннейшего цикла C графа G в терминах минимальной степени вершин или сумм степеней, связности • и длины p длиннейшей цепи в G — C для частных случаев когда • < 3 и p < 1 (в случае p = —1 имеет место V(G — C) = и C называется гамильтоновым циклом; если p = 0 то V (G — C) является независимым множеством вершин и C называется доминантным циклом). Обобщенные гипотезы Бонди (1980) и Юнга (2001) основаны на суммах степеней, где p и • являются параметрами, включающие вышеупамянутые результаты как частные случаи. Эти гипотезы остаются нерешенными. В 2009 г автор решил С-версии гипотез Бонди и Юнга на основе минимальной степени, где С обозначает длину длиннейшего цикла в V(G—C) (Discrete Math, v.309, 2009, 1925-1930). На основе другого результата автора (Graphs and Combinatorics, v.29, 2013, 1531-1541), в работе доказывается справедливость некеторых версий гипотез Бонди и Юнга, включающие p и С-версии без условия связности, которые в свою очередь порождают новые усиленные и расширенные версии этих гипотез. Все полученные результаты неулучшаемы.

Publisher:

Mathematical Problems of Computer Science

Identifier:

oai:noad.sci.am:136032

ISSN:

0131-4645

Language:

English

Volume:

45

URL:

click here to follow the link

Additional Information:

zhora@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2016

Indexing:

ASCI