CZCarol T. Zamfirescu
Carol T. Zamfirescu
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Carol T. Zamfirescu has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
- Jan Goedgebeur
KU Leuven Kulak
16 shared publications - Gábor Wiener
Budapest Univ Technol & Econ, Dept Comp Sci & Informat Theory, Budapest, Hungary
6 shared publications - Jarne Renders
KU Leuven Kulak
6 shared publications - Nico Van Cleemput
Department of Applied Mathematics Computer Science and Statistics Ghent University Ghent Belgium
5 shared publications - On-Hei Solomon Lo
Faculty of Environment and Information Sciences Yokohama National University Yokohama Japan
5 shared publications - Jorik Jooken
KU Leuven
4 shared publications
Latest Publications
- 11 September 2026
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 42 (5) , 70
Edge-Kempe Classes in Planar Regular Graphs
- 11 September 2026
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 42 (5) , 70
Edge-Kempe Classes in Planar Regular Graphs
- 31 March 2026
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 525
Network fault costs based on minimum leaf spanning trees
- 31 March 2026
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 525
Network fault costs based on minimum leaf spanning trees
- 4 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 377, 87-94
On platypus graphs and the Steiner–Deogun property
- 4 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 377, 87-94
On platypus graphs and the Steiner–Deogun property
- Open Access
Counting Small Cycle Double Covers
A theorem due to Seyffarth states that every planar $4$-connected $n$-vertex graph has a cycle double cover (CDC) containing at most $n-1$ cycles (a "small" CDC). We extend this theorem by proving that, in fact, such a graph must contain linearly many small CDCs (in terms of $n$), and provide stronger results in the case of planar $4$-connected triangulations. We complement this result with constructions of planar $4$-connected graphs which contain at most polynomially many small CDCs. Thereafter we treat cubic graphs, strengthening a lemma of Hušek and Šámal on the enumeration of CDCs, and, motivated by a conjecture of Bondy, give an alternative proof of the result that every planar 2-connected cubic graph on $n > 4$ vertices has a CDC of size at most $n/2$. Our proof is much shorter and obtained by combining a decomposition based argument, which might be of independent interest, with further combinatorial insights. Some of our results are accompanied by a version thereof for CDCs containing no cycle twice.Open AccessCounting Small Cycle Double Covers
A theorem due to Seyffarth states that every planar $4$-connected $n$-vertex graph has a cycle double cover (CDC) containing at most $n-1$ cycles (a "small" CDC). We extend this theorem by proving that, in fact, such a graph must contain linearly many small CDCs (in terms of $n$), and provide stronger results in the case of planar $4$-connected triangulations. We complement this result with constructions of planar $4$-connected graphs which contain at most polynomially many small CDCs. Thereafter we treat cubic graphs, strengthening a lemma of Hušek and Šámal on the enumeration of CDCs, and, motivated by a conjecture of Bondy, give an alternative proof of the result that every planar 2-connected cubic graph on $n > 4$ vertices has a CDC of size at most $n/2$. Our proof is much shorter and obtained by combining a decomposition based argument, which might be of independent interest, with further combinatorial insights. Some of our results are accompanied by a version thereof for CDCs containing no cycle twice. - Open Access
On a conjecture of Faudree and Schelp
In 1976 Faudree and Schelp conjectured that in a hamiltonian-connected graph on $n$ vertices, any two distinct vertices are connected by a path of length $k$ for every $k \ge n/2$. In 1978 Thomassen constructed a (non-cubic and non-planar) family of counterexamples, showing that there exist hamiltonian-connected $n$-vertex graphs containing two vertices with no path of length $n-2$ between them. We complement this result by describing cubic planar counterexamples on $6p+16$ vertices, each containing vertices between which there is no path of any odd length greater than $1$ and at most $4p+9$. Motivated by a remark of Thomassen about a gap in the cycle spectrum of hamiltonian-connected graphs, we also describe an infinite family of hamiltonian-connected graphs with many gaps in the first half of their cycle spectra.Open AccessOn a conjecture of Faudree and Schelp
In 1976 Faudree and Schelp conjectured that in a hamiltonian-connected graph on $n$ vertices, any two distinct vertices are connected by a path of length $k$ for every $k \ge n/2$. In 1978 Thomassen constructed a (non-cubic and non-planar) family of counterexamples, showing that there exist hamiltonian-connected $n$-vertex graphs containing two vertices with no path of length $n-2$ between them. We complement this result by describing cubic planar counterexamples on $6p+16$ vertices, each containing vertices between which there is no path of any odd length greater than $1$ and at most $4p+9$. Motivated by a remark of Thomassen about a gap in the cycle spectrum of hamiltonian-connected graphs, we also describe an infinite family of hamiltonian-connected graphs with many gaps in the first half of their cycle spectra. - 11 April 2025
- Published by Elsevier in Discrete Mathematics
- Vol. 348 (8)
Shortness parameters of polyhedral graphs with few distinct vertex degrees
- 11 April 2025
- Published by Elsevier in Discrete Mathematics
- Vol. 348 (8)
Shortness parameters of polyhedral graphs with few distinct vertex degrees
- Open Access
Network fault costs based on minimum leaf spanning trees
We study the fault-tolerance of networks from both the structural and computational point of view using the minimum leaf number of the corresponding graph $G$, i.e. the minimum number of leaves of the spanning trees of $G$, and its vertex-deleted subgraphs. We investigate networks that are leaf-guaranteed, i.e. which satisfy a certain stability condition with respect to minimum leaf numbers and vertex-deletion. Next to this, our main notion is the so-called fault cost, which is based on the number of vertices that have different degrees in minimum leaf spanning trees of the network and its vertex-deleted subgraphs. We characterise networks with vanishing fault cost via leaf-guaranteed graphs and describe, for any given network $N$, leaf-guaranteed networks containing $N$. We determine for all non-negative integers $k \le 8$ except $1$ the smallest network with fault cost $k$. We also give a detailed treatment of the fault cost $1$ case, prove that there are infinitely many $3$-regular networks with fault cost $3$, and show that for any non-negative integer $k$ there exists a network with fault cost exactly $k$.Open AccessNetwork fault costs based on minimum leaf spanning trees
We study the fault-tolerance of networks from both the structural and computational point of view using the minimum leaf number of the corresponding graph $G$, i.e. the minimum number of leaves of the spanning trees of $G$, and its vertex-deleted subgraphs. We investigate networks that are leaf-guaranteed, i.e. which satisfy a certain stability condition with respect to minimum leaf numbers and vertex-deletion. Next to this, our main notion is the so-called fault cost, which is based on the number of vertices that have different degrees in minimum leaf spanning trees of the network and its vertex-deleted subgraphs. We characterise networks with vanishing fault cost via leaf-guaranteed graphs and describe, for any given network $N$, leaf-guaranteed networks containing $N$. We determine for all non-negative integers $k \le 8$ except $1$ the smallest network with fault cost $k$. We also give a detailed treatment of the fault cost $1$ case, prove that there are infinitely many $3$-regular networks with fault cost $3$, and show that for any non-negative integer $k$ there exists a network with fault cost exactly $k$. - 5 November 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 170, 335-351
Counting cycles in planar triangulations
- 5 November 2024
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 170, 335-351
Counting cycles in planar triangulations
- 30 September 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 108 (2) , 368-373
Non‐Hamiltonian Cartesian products of two even dicycles
In this note it is proven that there exist infinitely many positive integers and such that the Cartesian product of a directed cycle of length and a directed cycle of length is non-Hamiltonian. In particular, the Cartesian product of an 880-dicycle and a 4368-dicycle is non-Hamiltonian. We also prove that there is no such graph on fewer than vertices, which is rather astonishing.- 30 September 2024
- Published by Wiley in Journal of Graph Theory
- Vol. 108 (2) , 368-373
Non‐Hamiltonian Cartesian products of two even dicycles
In this note it is proven that there exist infinitely many positive integers and such that the Cartesian product of a directed cycle of length and a directed cycle of length is non-Hamiltonian. In particular, the Cartesian product of an 880-dicycle and a 4368-dicycle is non-Hamiltonian. We also prove that there is no such graph on fewer than vertices, which is rather astonishing.- 22 March 2024
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (7)
Generation and new infinite families of K2-hypohamiltonian graphs
- 22 March 2024
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (7)
Generation and new infinite families of K2-hypohamiltonian graphs