RNDr. Radek Hušek, Ph.D.

Publications

Counting circuit double covers

Authors
Hušek, R.; Šámal, R.
Year
2025
Published
Journal of Graph Theory. 2025, 108(2), 374-395. ISSN 0364-9024.
Type
Article
DOI
10.1002/jgt.23187
Departments
Department of Theoretical Computer Science
Annotation
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 C_k for some k) 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 2^(n/2 - 1) circuit double covers and we show an infinite class of graphs for which this bound is tight.

Group connectivity: Z4 vs Z22

Authors
Hušek, R.; Mohelníková, L.; Šámal, R.
Year
2020
Published
Journal of Graph Theory. 2020, 93(3), ISSN 0364-9024.
Type
Article
DOI
10.1002/jgt.22488
Departments
Department of Theoretical Computer Science

Homomorphisms of Cayley Graphs and Cycle Double Covers

Authors
Hušek, R.; Šámal, R.
Year
2020
Published
Electronic Journal of Combinatorics (E-JC),. 2020, 27(2), ISSN 1077-8926.
Type
Article
DOI
10.37236/8456
Departments
Department of Theoretical Computer Science

Recognition of tractable DNFs representable by a constant number of intervals

Authors
Čepek, O.; Hušek, R.
Year
2017
Published
Discrete Optimization. 2017, 23 ISSN 1572-5286.
Type
Article
DOI
10.1016/j.disopt.2016.11.002
Departments
Department of Theoretical Computer Science