Про блоки у графах iз парними та непарними вiдстанями мiж не точками з’єднання
Loading...
Date
2024
Authors
Антошина, Катерина
Козеренко, Сергій
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Вершина графа називається точкою з’єднання, якщо її видалення збiльшує кiлькiсть компонент зв’язностi. Наприклад, для зв’язного графа 𝐺 вершина 𝑢 ∈ 𝑉 (𝐺) є точкою з’єднання, якщо граф 𝐺 − 𝑢 незв’язний. Дерево – це зв’язний ациклiчний граф. Легко бачити, що не точками з’єднання дерева є в точностi вершини степеня 1, якi називаються висячими. У роботi [3] дослiджувався спецiальний клас графiв пiд назвою сильно унiкально незалежнi графи. Це такi графи 𝐺, в яких iснує єдина максимальна незалежна множина вершин 𝐴 ⊂ 𝑉 (𝐺), що її доповнення 𝑉 (𝐺)∖𝐴 теж незалежна в 𝐺. Зокрема, було показано, що сильно унiкально незалежнi дерева (надалi просто SUIT) характеризуються як дерева iз парними вiдстанями мiж їхнiми висячими вершинами. Узагальнюючи цей клас дерев, у роботi було розглянуто зв’язнi графи iз парними вiд-
станями мiж їхнiми не точками з’єднання (NCE-графи) та графи з цими непарними вiдстанями (NCO-графи).
Description
Keywords
NCE-граф, NCO-граф, двозв’язний пiдграф, тези конференції
Citation
Антошина К. О. Про блоки у графах із парними та непарними відстанями між не точками з'єднання / К. О. Антошина, С. О. Козеренко // XII Всеукраїнська наукова конференцiя молодих математикiв, Київ, 9-11 травня 2024 р. : [збірник тез /оргком.: Глибовець А. М. та ін.] ; Нацiональний унiверситет Києво-Могилянська академiя" [та ін.]. - [Київ : б. в.], 2024. - С. 95-96.