Decycling cubic graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F24%3A43972124" target="_blank" >RIV/49777513:23520/24:43972124 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S0012365X24001705?pes=vor" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0012365X24001705?pes=vor</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Decycling cubic graphs

Popis výsledku v původním jazyce

A set of vertices of a graph G is said to be decycling if its removal leaves an acyclic subgraph. The size of a smallest decycling set is the decycling number of G. Generally, at least ⌈(n+2)/4⌉ vertices have to be removed in order to decycle a cubic graph on n vertices. In 1979, Payan and Sakarovitch proved that the decycling number of a cyclically 4-edge-connected cubic graph of order n equals ⌈(n+2)/4⌉. In addition, they characterised the structure of minimum decycling sets and their complements. If n≡2(mod4), then G has a decycling set which is independent and its complement induces a tree. If n≡0(mod4), then one of two possibilities occurs: either G has an independent decycling set whose complement induces a forest of two trees, or the decycling set is near-independent (which means that it induces a single edge) and its complement induces a tree. In this paper we strengthen the result of Payan and Sakarovitch by proving that the latter possibility (a near-independent set and a tree) can always be guaranteed. Moreover, we relax the assumption of cyclic 4-edge-connectivity to a significantly weaker condition expressed through the canonical decomposition of 3-connected cubic graphs into cyclically 4-edge-connected ones. Our methods substantially use a surprising and seemingly distant relationship between the decycling number and the maximum genus of a cubic graph.

Název v anglickém jazyce

Decycling cubic graphs

Popis výsledku anglicky

A set of vertices of a graph G is said to be decycling if its removal leaves an acyclic subgraph. The size of a smallest decycling set is the decycling number of G. Generally, at least ⌈(n+2)/4⌉ vertices have to be removed in order to decycle a cubic graph on n vertices. In 1979, Payan and Sakarovitch proved that the decycling number of a cyclically 4-edge-connected cubic graph of order n equals ⌈(n+2)/4⌉. In addition, they characterised the structure of minimum decycling sets and their complements. If n≡2(mod4), then G has a decycling set which is independent and its complement induces a tree. If n≡0(mod4), then one of two possibilities occurs: either G has an independent decycling set whose complement induces a forest of two trees, or the decycling set is near-independent (which means that it induces a single edge) and its complement induces a tree. In this paper we strengthen the result of Payan and Sakarovitch by proving that the latter possibility (a near-independent set and a tree) can always be guaranteed. Moreover, we relax the assumption of cyclic 4-edge-connectivity to a significantly weaker condition expressed through the canonical decomposition of 3-connected cubic graphs into cyclically 4-edge-connected ones. Our methods substantially use a surprising and seemingly distant relationship between the decycling number and the maximum genus of a cubic graph.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

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ů

Název periodika

Discrete Mathematics

ISSN

0012-365X

e-ISSN

1872-681X

Svazek periodika

347

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

20

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85191298820