Decycling cubic graphs

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Decycling cubic graphs

Original language description

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.

Czech name

—

Czech description

—

Type

J_SC - Article in a specialist periodical, which is included in the SCOPUS database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Name of the periodical

Discrete Mathematics

ISSN

0012-365X

e-ISSN

1872-681X

Volume of the periodical

347

Issue of the periodical within the volume

8

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

20

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

2-s2.0-85191298820