19 papers
On the order-diameter ratio of girth-diameter cages
Stijn Cambie, Jan Goedgebeur, Jorik Jooken +1
For integers , a -cage (or simply girth-diameter cage) is a smallest -regular graph of girth and diameter (if it exists). The order of a -cage i…
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…
The Gray graph is pseudo 2-factor isomorphic
Marien Abreu, Jan Goedgebeur, Jorik Jooken +2
A graph is pseudo 2-factor isomorphic if all of its 2-factors have the same parity of number of cycles. Abreu et al. [J. Comb. Theory, Ser. B. 98 (2008) 432--442] conjectured that…
Generation of Cycle Permutation Graphs and Permutation Snarks
Jan Goedgebeur, Jarne Renders, Steven Van Overberghe
We present an algorithm for the efficient generation of all pairwise non-isomorphic cycle permutation graphs, i.e. cubic graphs with a -factor consisting of two chordless cycles…
Knowledge management in House of Graphs
Gauvain Devillez, Sven D'hondt, Jan Goedgebeur
The House of Graphs is an online database of graphs which can be accessed at https://houseofgraphs.org/. It serves as a central repository for complete lists of graphs for various…
Minimal obstructions to -coloring in hereditary graph classes
Jan Goedgebeur, Jorik Jooken, Karolina Okrasa +2
For graphs and , an -coloring of is an edge-preserving mapping from to . Note that if is the triangle, then -colorings are equivalent to -color…