Perfect matchings in highly cyclically connected regular graphs

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.22764" target="_blank" >https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.22764</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/jgt.22764" target="_blank" >10.1002/jgt.22764</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Perfect matchings in highly cyclically connected regular graphs

Popis výsledku v původním jazyce

A leaf matching operation on a graph consists of removing a vertex of degree 1 together with its neighbour from the graph. Let G be a d‐regular cyclically (d k − 1+2 )‐ edge‐connected graph of even order, where k ≥ 0 and d ≥ 3. We prove that for any given set X of d k − 1 + edges, there is no 1‐factor of G avoiding X if and only if either an isolated vertex can be obtained by a series of leaf matching operations in G − X, or G − X has an independent set that contains more than half of the vertices of G. To demonstrate how to check the conditions of the theorem we prove several statements on 2‐factors of cubic graphs. For k ≥ 3, we prove that given a cyclically (4k − 5)‐edge‐connected cubic graphG and three paths of length k such that the distance between any two of them is at least 8k − 16, there is a 2‐factor of G that contains one of the paths. We provide a similar statement for two paths when k = 3 and k = 4. As a corollary we show that given a vertex v in a cyclically 7‐edge‐connected cubic graph, there is a 2‐factor such that v is in a circuit of length greater than 7.

Název v anglickém jazyce

Perfect matchings in highly cyclically connected regular graphs

Popis výsledku anglicky

A leaf matching operation on a graph consists of removing a vertex of degree 1 together with its neighbour from the graph. Let G be a d‐regular cyclically (d k − 1+2 )‐ edge‐connected graph of even order, where k ≥ 0 and d ≥ 3. We prove that for any given set X of d k − 1 + edges, there is no 1‐factor of G avoiding X if and only if either an isolated vertex can be obtained by a series of leaf matching operations in G − X, or G − X has an independent set that contains more than half of the vertices of G. To demonstrate how to check the conditions of the theorem we prove several statements on 2‐factors of cubic graphs. For k ≥ 3, we prove that given a cyclically (4k − 5)‐edge‐connected cubic graphG and three paths of length k such that the distance between any two of them is at least 8k − 16, there is a 2‐factor of G that contains one of the paths. We provide a similar statement for two paths when k = 3 and k = 4. As a corollary we show that given a vertex v in a cyclically 7‐edge‐connected cubic graph, there is a 2‐factor such that v is in a circuit of length greater than 7.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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ů

Název periodika

JOURNAL OF GRAPH THEORY

ISSN

0364-9024

e-ISSN

1097-0118

Svazek periodika

100

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

28-49

Kód UT WoS článku

000710868900001

EID výsledku v databázi Scopus

2-s2.0-85118139855