17 citations · 56 across the 23 of their papers we have counts for
25 papers · 1 filter
On the number of perfect matchings in planar graphs
Jan Goedgebeur, Jorik Jooken, Tibo Van den Eede +1
We investigate the minimum non-zero number of perfect matchings in planar graphs. We prove that this is a constant for 2-connected planar graphs of minimum degree 3 and 3-connected…
Counting Hamiltonian paths between prescribed vertices in traceable graphs with a forbidden induced subgraph
Jorik Jooken, Carol T. Zamfirescu
For graphs and , we say that is -free if does not occur as an induced subgraph of . This paper is concerned with the following question: Given an -free grap…
Counting Small Cycle Double Covers
Jorik Jooken, Ben Seamone, Carol T. Zamfirescu
A theorem due to Seyffarth states that every planar -connected -vertex graph has a cycle double cover (CDC) containing at most cycles (a "small" CDC). We extend this th…
On a conjecture of Faudree and Schelp
Jan Goedgebeur, Jorik Jooken, Michiel Provoost +1
In 1976 Faudree and Schelp conjectured that in a hamiltonian-connected graph on vertices, any two distinct vertices are connected by a path of length for every .…
Network fault costs based on minimum leaf spanning trees
Jan Goedgebeur, Jarne Renders, Gábor Wiener +1
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 , i.e. the minimum num…
On the girth and connectivity of cubic graphs with a unique longest cycle
Jorik Jooken, Carol T. Zamfirescu
We show that there exists an infinite family of cubic -connected non-hamiltonian graphs with girth containing a unique longest cycle.
HIST-Critical Graphs and Malkevitch's Conjecture
Jan Goedgebeur, Kenta Noguchi, Jarne Renders +1
In a given graph, a HIST is a spanning tree without -valent vertices. Motivated by developing a better understanding of HIST-free graphs, i.e. graphs containing no HIST, in this…
Spanning trees for many different numbers of leaves
Kenta Noguchi, Carol T. Zamfirescu
Let be a connected graph and the set of all integers such that contains a spanning tree with exactly leaves. We show that for a connected graph , the set…
Generation and New Infinite Families of -hypohamiltonian Graphs
Jan Goedgebeur, Jarne Renders, Carol T. Zamfirescu
We present an algorithm which can generate all pairwise non-isomorphic -hypohamiltonian graphs, i.e. non-hamiltonian graphs in which the removal of any pair of adjacent vertic…
-Hamiltonian Graphs: II
Jan Goedgebeur, Jarne Renders, Gábor Wiener +1
In this paper we use theoretical and computational tools to continue our investigation of -hamiltonian graphs, that is, graphs in which the removal of any pair of adjacent ver…
Few hamiltonian cycles in graphs with one or two vertex degrees
Jan Goedgebeur, Jorik Jooken, On-Hei Solomon Lo +2
We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct…
Counting cycles in planar triangulations
On-Hei Solomon Lo, Carol T. Zamfirescu
We investigate the minimum number of cycles of specified lengths in planar -vertex triangulations . It is proven that this number is for any cycle length at most $3 +…
4-regular 4-connected Hamiltonian graphs with few Hamiltonian cycles
Carsten Thomassen, Carol T. Zamfirescu
We prove that there exists an infinite family of 4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles. We do not know if there exists such a family…
Regular graphs with few longest cycles
Carol T. Zamfirescu
Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant such that there is an infinite family of 4-regular 4-connected graphs, eac…
Counterexamples to a conjecture of Merker on 3-connected cubic planar graphs with a large cycle spectrum gap
Carol T. Zamfirescu
Merker conjectured that if is an integer and a 3-connected cubic planar graph of circumference at least , then the set of cycle lengths of must contain at leas…
Hamiltonian cycles and 1-factors in 5-regular graphs
Nico Van Cleemput, Carol T. Zamfirescu
It is proven that for any integer and , there exist infinitely many 5-regular graphs of genus containing a 1-factorisation with exactly …
Long Cycles and Spanning Subgraphs of Locally Maximal 1-planar Graphs
Igor Fabrici, Jochen Harant, Tomáš Madaras +3
A graph is -planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for e…
The Connectivity of the Dual
Drago Bokal, Gunnar Brinkmannb, Carol T. Zamfirescu
The dual of a polyhedron is a polyhedron -- or in graph theoretical terms: the dual of a 3-connected plane graph is a 3-connected plane graph. Astonishingly, except for sufficientl…
Graphs with few Hamiltonian Cycles
Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu
We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number of hamiltonian cycles, which is especially efficient for small . Ou…
Structural and computational results on platypus graphs
Jan Goedgebeur, Addie Neyt, Carol T. Zamfirescu
A platypus graph is a non-hamiltonian graph for which every vertex-deleted subgraph is traceable. They are closely related to families of graphs satisfying interesting conditions r…
On Hypohamiltonian Snarks and a Theorem of Fiorini
Jan Goedgebeur, Carol T. Zamfirescu
We discuss an omission in the statement and proof of Fiorini's 1983 theorem on hypohamiltonian snarks and present a version of this theorem which is more general in several ways. U…
On almost hypohamiltonian graphs
Jan Goedgebeur, Carol T. Zamfirescu
A graph is almost hypohamiltonian (a.h.) if is non-hamiltonian, there exists a vertex in such that is non-hamiltonian, and is hamiltonian for every…
Polyhedra with few 3-cuts are hamiltonian
Gunnar Brinkmann, Carol T. Zamfirescu
In 1956, Tutte showed that every planar 4-connected graph is hamiltonian. In this article, we will generalize this result and prove that polyhedra with at most three 3-cuts are ham…
Improved bounds for hypohamiltonian graphs
Jan Goedgebeur, Carol T. Zamfirescu
A graph is hypohamiltonian if is non-hamiltonian and is hamiltonian for every . In the following, every graph is assumed to be hypohamiltonian. Aldred,…