Journal or Publication Title:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Date of publication:

2023

Number:

59

ISSN:

2579-2784 ; e-2538-2788

Additional Information:

Նիկողոսյան Ժորա Գ., Никогосян Жора Г.

Other title:

Ակնարկ գրաֆներում մեծ ցիկլերի մասին Բոնդիի և Յունգի վարկածների շուրջ ; Заметка о больших циклах в графах вокруг гипотез Бонди и Юнга

Corporate Creators:

Institute for Informatics and Automation Problems of NAS RA

Coverage:

7-15

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). Полученные результаты в сочетании дают основания выдвижения новых улучшенных вариантов для исходных гипотез Бонди и Юнга.

Publisher:

Изд-во НАН РА

Format:

pdf

Identifier:

oai:arar.sci.am:366982

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան