Journal or Publication Title:
Date of publication:
Number:
ISSN:
Additional Information:
Նիկողոսյան Ժորա Գ., Никогосян Жора Г.
Title:
A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung
Other title:
Ակնարկ գրաֆներում մեծ ցիկլերի մասին Բոնդիի և Յունգի վարկածների շուրջ ; Заметка о больших циклах в графах вокруг гипотез Бонди и Юнга
Creator:
Corporate Creators:
Institute for Informatics and Automation Problems of NAS RA
Subject:
Mathematical cybernetics ; Computer science
Uncontrolled Keywords:
Hamilton cycle ; Dominating cycle ; Large cycle ; Longest cycle
Coverage:
Abstract:
New sufficient conditions are derived for generalized cycles (including Hamilton and dominating cycles as special cases) in an arbitrary k-connected (k = 1, 2, ...) graph, which prove the truth of Bondy’s (1980) famous conjecture for some variants significantly improving the result expected by the given hypothesis. Similarly, new lower bounds for the circumference (the length of a longest cycle) are established for the reverse hypothesis proposed by Jung (2001) combined inspiring new improved versions of the original conjectures of Bondy and Jung.
Ստացվել են նոր բավարար պայմաններ գրաֆի ընդհանրացված ցիկլերի համար (ընդգրկելով Համիլթոնյան և դոմինանտ ցիկլերը որպես մասնավոր դեպքեր) կամայական k-կապակցված ( k = 1, 2,...) գրաֆում, որոնք ապացուցում են Բոնդիի (1980) հայտնի վարկածի ճշմարտացիությունը որոշ տարերակների դեպքում, ինչի շնորհիվ զգալիորեն լավացվում է տվյալ վարկածով ակնկալվող արդյունքը: Համանմանորեն, ամենաերկար ցիկլի երկարության համար ստացվել են նոր ստորին գնահատականներ հակադարձ վարկածի համար, որն առաջ է քաշել Յունգը 2001-ին: Ստացված արդյունքները ավարար հիմքեր են տալիս առաջ քաշելու նոր լավացված տարերակներ Բոնդիի և Յունգի նախնական վարկածների փոխարեն:
Получены новые достаточные условия для обобщенных циклов (включая гамильтоновые и доминантные циклы как частные случаи) в произвольном k-связном графе ( k = 1, 2,...) , доказывающие справедливость известной гипотезы Бонди (1980) для некоторых вариантов, значительно улучшив ожидаемый по данной гипотезе результат. Аналогично, получены новые нижние оценки для длины длиннейшего цикла графа для обратной гипотезы, предложенной Юнгом (2001). Полученные результаты в сочетании дают основания выдвижения новых улучшенных вариантов для исходных гипотез Бонди и Юнга.