Counting circuit double covers

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10513662" target="_blank" >RIV/00216208:11320/25:10513662 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/25:00379064

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=u2rR13N8Ej" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=u2rR13N8Ej</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Counting circuit double covers

Popis výsledku v původním jazyce

We study a counting version of Cycle Double Cover Conjecture. We discuss why it is more interesting to count circuits (i.e., graphs isomorphic to (Formula presented.) for some (Formula presented.)) instead of cycles (graphs with all degrees even). We give an almost-exponential lower bound for graphs with a surface embedding of representativity at least 4. We also prove an exponential lower bound for planar graphs. We conjecture that any bridgeless cubic graph has at least (Formula presented.) circuit double covers and we show an infinite class of graphs for which this bound is tight.

Název v anglickém jazyce

Counting circuit double covers

Popis výsledku anglicky

We study a counting version of Cycle Double Cover Conjecture. We discuss why it is more interesting to count circuits (i.e., graphs isomorphic to (Formula presented.) for some (Formula presented.)) instead of cycles (graphs with all degrees even). We give an almost-exponential lower bound for graphs with a surface embedding of representativity at least 4. We also prove an exponential lower bound for planar graphs. We conjecture that any bridgeless cubic graph has at least (Formula presented.) circuit double covers and we show an infinite class of graphs for which this bound is tight.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-17398S" target="_blank" >GA22-17398S: Toky a cykly v grafech na plochách</a><br>

Návaznosti

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

Rok uplatnění

2025

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

108

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

374-395

Kód UT WoS článku

001324395000001

EID výsledku v databázi Scopus

2-s2.0-85205355982