Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F22%3A43964092" target="_blank" >RIV/49777513:23520/22:43964092 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://www.sciencedirect.com/science/article/pii/S0095895622000077" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0095895622000077</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1016/j.jctb.2022.01.007" target="_blank" >10.1016/j.jctb.2022.01.007</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs

  • Popis výsledku v původním jazyce

    Edge-elimination is an operation of removing an edge of a cubic graph together with its endvertices and suppressing the resulting 2-valent vertices. We study the effect of this operation on the cyclic connectivity of a cubic graph. Disregarding a small number of cubic graphs with no more than six vertices, this operation cannot decrease cyclic connectivity by more than two. We show that apart from three exceptional graphs (the cube, the twisted cube, and the Petersen graph) every 2-connected cubic graph on at least eight vertices contains an edge whose elimination decreases cyclic connectivity by at most one. The proof reveals an unexpected behaviour of connectivity 6, which requires a detailed structural analysis featuring the Isaacs flower snarks and their natural generalisation, the twisted Isaacs graphs, as forced structures. A complete characterisation of this family, which includes the Heawood graph as a sporadic case, serves as the main tool for excluding the existence of exceptional graphs in connectivity 6. As an application we show that every cyclically 5-edge-connected cubic graph has a decycling set of vertices whose removal leaves a tree and the set itself has at most one edge between its vertices. This strengthens a classical result of Payan and Sakarovitch (1975) .

  • Název v anglickém jazyce

    Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs

  • Popis výsledku anglicky

    Edge-elimination is an operation of removing an edge of a cubic graph together with its endvertices and suppressing the resulting 2-valent vertices. We study the effect of this operation on the cyclic connectivity of a cubic graph. Disregarding a small number of cubic graphs with no more than six vertices, this operation cannot decrease cyclic connectivity by more than two. We show that apart from three exceptional graphs (the cube, the twisted cube, and the Petersen graph) every 2-connected cubic graph on at least eight vertices contains an edge whose elimination decreases cyclic connectivity by at most one. The proof reveals an unexpected behaviour of connectivity 6, which requires a detailed structural analysis featuring the Isaacs flower snarks and their natural generalisation, the twisted Isaacs graphs, as forced structures. A complete characterisation of this family, which includes the Heawood graph as a sporadic case, serves as the main tool for excluding the existence of exceptional graphs in connectivity 6. As an application we show that every cyclically 5-edge-connected cubic graph has a decycling set of vertices whose removal leaves a tree and the set itself has at most one edge between its vertices. This strengthens a classical result of Payan and Sakarovitch (1975) .

Klasifikace

  • Druh

    J<sub>SC</sub> - Článek v periodiku v databázi SCOPUS

  • CEP obor

  • OECD FORD obor

    10101 - Pure mathematics

Návaznosti výsledku

  • Projekt

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2022

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název periodika

    Journal of Combinatorial Theory, Series B

  • ISSN

    0095-8956

  • e-ISSN

  • Svazek periodika

    155

  • Číslo periodika v rámci svazku

    Leden

  • Stát vydavatele periodika

    NL - Nizozemsko

  • Počet stran výsledku

    28

  • Strana od-do

    17-44

  • Kód UT WoS článku

  • EID výsledku v databázi Scopus

    2-s2.0-85123885552