Ամսագրի կամ հրապարակման վերնագիր:

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

Հրապարակման ամսաթիւ:

2023

Համար:

59

ISSN:

2579-2784 ; e-2538-2788

Լրացուցիչ տեղեկութիւն:

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

Այլ վերնագիր:

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

Համատեղ հեղինակները:

Institute for Informatics and Automation Problems of NAS RA

Ծածկոյթ:

7-15

Ամփոփում:

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

Հրատարակիչ:

Изд-во НАН РА

Ձեւաչափ:

pdf

Նոյնացուցիչ:

oai:arar.sci.am:366982

Բնօրինակին գտնուելու վայրը:

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