Jorik Jooken

Inspired by Sheehan’s conjecture that no <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4"> <mml:semantics> <mml:mn>4</mml:mn> <mml:annotation encoding="application/x-tex">4</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles … Inspired by Sheehan’s conjecture that no <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4"> <mml:semantics> <mml:mn>4</mml:mn> <mml:annotation encoding="application/x-tex">4</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. 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 and complement Haythorpe’s computational enumerative results from [Exp. Math. <bold>27</bold> (2018), no. 4, 426–430]. Thereafter, we use the Lovász Local Lemma to extend Thomassen’s independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k element-of StartSet 5 comma 6 EndSet"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>∈</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>5</mml:mn> <mml:mo>,</mml:mo> <mml:mn>6</mml:mn> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">k \in \{5, 6\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> there exist infinitely many <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="kappa element-of StartSet 2 comma 3 EndSet"> <mml:semantics> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>∈</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>3</mml:mn> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\kappa \in \{ 2, 3 \}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and any positive integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, there are infinitely many non-regular graphs of connectivity <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="kappa"> <mml:semantics> <mml:mi>κ</mml:mi> <mml:annotation encoding="application/x-tex">\kappa</mml:annotation> </mml:semantics> </mml:math> </inline-formula> containing exactly one hamiltonian cycle and in which every vertex has degree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="3"> <mml:semantics> <mml:mn>3</mml:mn> <mml:annotation encoding="application/x-tex">3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> or <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 k"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">2k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.

View PDF Chat

The Maximum Number of Connected Sets in Regular Graphs

2025-02-14

Stijn Cambie , Jorik Jooken , Jan Goedgebeur

We make some fundamental observations and conjectures on the number of connected sets $N(G)$ in $d$-regular graphs $G$. We improve the best known lower bounds on the exponential behavior of … We make some fundamental observations and conjectures on the number of connected sets $N(G)$ in $d$-regular graphs $G$. We improve the best known lower bounds on the exponential behavior of the maximum of $N(G)$ for regular graphs by considering a different construction of a family of graphs (depending on smaller base graphs) and improve the upper bounds conditional on one of our conjectures. The lower bounds are estimated using combinatorial reductions and linear algebra. We also determine the exact maxima of $N(G)$ for cubic and quartic graphs with small order.

Some Results on Critical ($$P_5,H$$)-Free Graphs

2025-01-01

Xia Wen , Jorik Jooken , Jan Goedgebeur +1 more

A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs

2019-04-24

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

This paper proposes a local search algorithm for a specific combinatorial optimisation problem in graph theory: the Hamiltonian Completion Problem (HCP) on undirected graphs. In this problem, the objective is … This paper proposes a local search algorithm for a specific combinatorial optimisation problem in graph theory: the Hamiltonian Completion Problem (HCP) on undirected graphs. In this problem, the objective is to add as few edges as possible to a given undirected graph in order to obtain a Hamiltonian graph. This problem has mainly been studied in the context of various specific kinds of undirected graphs (e.g. trees, unicyclic graphs and series-parallel graphs). The proposed algorithm, however, concentrates on solving HCP for general undirected graphs. It can be considered to belong to the category of matheuristics, because it integrates an exact linear time solution for trees into a local search algorithm for general graphs. This integration makes use of the close relation between HCP and the minimum path partition problem, which makes the algorithm equally useful for solving the latter problem. Furthermore, a benchmark set of problem instances is constructed for demonstrating the quality of the proposed algorithm. A comparison with state-of-the-art solvers indicates that the proposed algorithm is able to achieve high-quality results.

Exploring search space trees using an adapted version of Monte Carlo tree search for a combinatorial optimization problem.

2020-10-22

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker +1 more

In this article, a novel approach to solve combinatorial optimization problems is proposed. This approach makes use of a heuristic algorithm to explore the search space tree of a problem … In this article, a novel approach to solve combinatorial optimization problems is proposed. This approach makes use of a heuristic algorithm to explore the search space tree of a problem instance. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees. By leveraging the combinatorial structure of a problem, several enhancements to the algorithm are proposed. These enhancements aim to efficiently explore the search space tree by pruning subtrees, using a heuristic simulation policy, reducing the domains of variables by eliminating dominated value assignments and using a beam width. They are demonstrated for two specific combinatorial optimization problems: the quay crane scheduling problem with non-crossing constraints and the 0-1 knapsack problem. Computational results show that the algorithm achieves promising results for both problems and eight new best solutions for a benchmark set of instances are found for the former problem. These results indicate that the algorithm is competitive with the state-of-the-art. Apart from this, the results also show evidence that the algorithm is able to learn to correct the incorrect choices made by constructive heuristics.

A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs

2019-01-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

View PDF Chat

Evolving test instances of the Hamiltonian completion problem

2020-01-01

Thibault Lechien , Jorik Jooken , Patrick De Causmaecker

Predicting and comparing algorithm performance on graph instances is challenging for multiple reasons. First, there is usually no standard set of instances to benchmark performance. Second, using existing graph generators … Predicting and comparing algorithm performance on graph instances is challenging for multiple reasons. First, there is usually no standard set of instances to benchmark performance. Second, using existing graph generators results in a restricted spectrum of difficulty and the resulting graphs are usually not diverse enough to draw sound conclusions. That is why recent work proposes a new methodology to generate a diverse set of instances by using an evolutionary algorithm. We can then analyze the resulting graphs and get key insights into which attributes are most related to algorithm performance. We can also fill observed gaps in the instance space in order to generate graphs with previously unseen combinations of features. This methodology is applied to the instance space of the Hamiltonian completion problem using two different solvers, namely the Concorde TSP Solver and a multi-start local search algorithm.

View PDF Chat

Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems

2020-01-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker +1 more

In this article we propose a heuristic algorithm to explore search space trees associated with instances of combinatorial optimization problems. The algorithm is based on Monte Carlo tree search, a … In this article we propose a heuristic algorithm to explore search space trees associated with instances of combinatorial optimization problems. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees and represents the state-of-the-art algorithm for a number of games. Several enhancements to Monte Carlo tree search are proposed that make the algorithm more suitable in a combinatorial optimization context. These enhancements exploit the combinatorial structure of the problem and aim to efficiently explore the search space tree by pruning subtrees, using a heuristic simulation policy, reducing the domains of variables by eliminating dominated value assignments and using a beam width. The algorithm was implemented with its components specifically tailored to two combinatorial optimization problems: the quay crane scheduling problem with non-crossing constraints and the 0-1 knapsack problem. For the first problem our algorithm surpasses the state-of-the-art results and several new best solutions are found for a benchmark set of instances. For the second problem our algorithm typically produces near-optimal solutions that are slightly worse than the state-of-the-art results, but it needs only a small fraction of the time to do so. These results indicate that the algorithm is competitive with the state-of-the-art for two entirely different combinatorial optimization problems.

View PDF Chat

Few hamiltonian cycles in graphs with one or two vertex degrees

2022-01-01

Jan Goedgebeur , Jorik Jooken , On‐Hei Solomon Lo +2 more

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 and complement … 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 and complement Haythorpe's computational enumerative results from [Experim. Math. 27 (2018) 426-430]. Thereafter, we use the Lov\'asz Local Lemma to extend Thomassen's independent dominating set method. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen. Motivated by an observation of Aldred and Thomassen, we prove that for every $\kappa \in \{ 2, 3 \}$ and any positive integer $k$, there are infinitely many non-regular graphs of connectivity $\kappa$ containing exactly one hamiltonian cycle and in which every vertex has degree $3$ or $2k$.

View PDF Chat

Features for the 0-1 knapsack problem based on inclusionwise maximal solutions

2022-01-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

Decades of research on the 0-1 knapsack problem led to very efficient algorithms that are able to quickly solve large problem instances to optimality. This prompted researchers to also investigate … Decades of research on the 0-1 knapsack problem led to very efficient algorithms that are able to quickly solve large problem instances to optimality. This prompted researchers to also investigate whether relatively small problem instances exist that are hard for existing solvers and investigate which features characterize their hardness. Previously the authors proposed a new class of hard 0-1 knapsack problem instances and demonstrated that the properties of so-called inclusionwise maximal solutions (IMSs) can be important hardness indicators for this class. In the current paper, we formulate several new computationally challenging problems related to the IMSs of arbitrary 0-1 knapsack problem instances. Based on generalizations of previous work and new structural results about IMSs, we formulate polynomial and pseudopolynomial time algorithms for solving these problems. From this we derive a set of 14 computationally expensive features, which we calculate for two large datasets on a supercomputer in approximately 540 CPU-hours. We show that the proposed features contain important information related to the empirical hardness of a problem instance that was missing in earlier features from the literature by training machine learning models that can accurately predict the empirical hardness of a wide variety of 0-1 knapsack problem instances. Using the instance space analysis methodology, we also show that hard 0-1 knapsack problem instances are clustered together around a relatively dense region of the instance space and several features behave differently in the easy and hard parts of the instance space.

View PDF Chat

A heuristic algorithm using tree decompositions for the maximum happy vertices problem

2022-01-01

Louis Carpentier , Jorik Jooken , Jan Goedgebeur

We propose a new methodology to develop heuristic algorithms using tree decompositions. Traditionally, such algorithms construct an optimal solution of the given problem instance through a dynamic programming approach. We … We propose a new methodology to develop heuristic algorithms using tree decompositions. Traditionally, such algorithms construct an optimal solution of the given problem instance through a dynamic programming approach. We modify this procedure by introducing a parameter $W$ that dictates the number of dynamic programming states to consider. We drop the exactness guarantee in favour of a shorter running time. However, if $W$ is large enough such that all valid states are considered, our heuristic algorithm proves optimality of the constructed solution. In particular, we implement a heuristic algorithm for the Maximum Happy Vertices problem using this approach. Our algorithm more efficiently constructs optimal solutions compared to the exact algorithm for graphs of bounded treewidth. Furthermore, our algorithm constructs higher quality solutions than state-of-the-art heuristic algorithms Greedy-MHV and Growth-MHV for instances of which at least 40\% of the vertices are initially coloured, at the cost of a larger running time.

Improved asymptotic upper bounds for the minimum number of pairwise distinct longest cycles in regular graphs

2023-01-01

Jorik Jooken

We study how few pairwise distinct longest cycles a regular graph can have under additional constraints. For each integer $r \geq 5$, we give exponential improvements for the best asymptotic … We study how few pairwise distinct longest cycles a regular graph can have under additional constraints. For each integer $r \geq 5$, we give exponential improvements for the best asymptotic upper bounds for this invariant under the additional constraint that the graphs are $r$-regular hamiltonian graphs. Earlier work showed that a conjecture by Haythorpe on a lower bound for this invariant is false because of an incorrect constant factor, whereas our results imply that the conjecture is even asymptotically incorrect. Motivated by a question of Zamfirescu and work of Chia and Thomassen, we also study this invariant for non-hamiltonian 2-connected $r$-regular graphs and show that in this case the invariant can be bounded from above by a constant for all large enough graphs, even for graphs with arbitrarily large girth.

The maximum number of connected sets in regular graphs

2023-01-01

Stijn Cambie , Jan Goedgebeur , Jorik Jooken

View PDF Chat

Counterexamples to conjectures on the occupancy fraction of graphs

2023-01-01

Stijn Cambie , Jorik Jooken

The occupancy fraction of a graph is a (normalized) measure on the size of independent sets under the hard-core model, depending on a variable (fugacity) $\lambda.$ We present a criterion … The occupancy fraction of a graph is a (normalized) measure on the size of independent sets under the hard-core model, depending on a variable (fugacity) $\lambda.$ We present a criterion for finding the graph with minimum occupancy fraction among graphs with a fixed order, and disprove five conjectures on the extremes of the occupancy fraction and (normalized) independence polynomial for certain graph classes of regular graphs with a given girth.

View PDF Chat

A note on $\bar{X}$-coloring and $\hat{A}$-coloring 4-regular graphs

2024-01-01

Jorik Jooken

Let $\partial_H(u)$ be the set of edges incident with a vertex $u$ in the graph $H$. We say that a graph $G$ is $H$-colorable if there exist total functions $f … Let $\partial_H(u)$ be the set of edges incident with a vertex $u$ in the graph $H$. We say that a graph $G$ is $H$-colorable if there exist total functions $f : E(G) \rightarrow E(H)$ and $g : V(G) \rightarrow V(H)$ such that $f$ is a proper edge-coloring of $G$ and for each vertex $u \in V(G)$ we have $f(\partial_G(u))=\partial_H(g(u))$. Let $\bar{X}$ be the graph obtained by adding three parallel edges between two degree one vertices of the graph $K_{1,4}$. Let $\hat{A}$ be the graph obtained by adding two pendant edges to two different vertices of a triangle and then adding two edges between the degree two vertex and the two adjacent degree three vertices. Malnegro and Ozeki [Discrete Math. 347(3):113844 (2024)] asked whether every 4-regular graph with an even number of vertices and an even cycle decomposition of size 3 admits an $\bar{X}$-coloring or an $\hat{A}$-coloring and whether every 2-connected planar 4-regular graph with an even number of vertices admits such a coloring. Additionally, they conjectured that for every 2-edge-connected simple cubic graph $G$ with an even number of edges, the line graph $L(G)$ is $\bar{X}$-colorable. In this short note, we discuss two algorithms for deciding whether a graph $G$ is $H$-colorable. We give a negative answer to the two questions and disprove the conjecture by finding suitable graphs, as verified by two independent algorithms.

View PDF Chat

Exhaustive generation of edge-girth-regular graphs

2024-01-01

Jan Goedgebeur , Jorik Jooken

Edge-girth-regular graphs (abbreviated as $egr$ graphs) are a class of highly symmetrical graphs. More specifically, for integers $v$, $k$, $g$ and $\lambda$ an $egr(v,k,g,\lambda)$ graph is a $k$-regular graph with … Edge-girth-regular graphs (abbreviated as $egr$ graphs) are a class of highly symmetrical graphs. More specifically, for integers $v$, $k$, $g$ and $\lambda$ an $egr(v,k,g,\lambda)$ graph is a $k$-regular graph with girth $g$ on $v$ vertices such that every edge is contained in exactly $\lambda$ cycles of length $g$. The central problem in this paper is determining $n(k,g,\lambda)$, which is defined as the smallest integer $v$ such that an $egr(v,k,g,\lambda)$ graph exists (or $\infty$ if no such graph exists) as well as determining the corresponding extremal graphs. We propose a linear time algorithm for computing how often an edge is contained in a cycle of length $g$, given a graph with girth $g$. We use this as one of the building blocks to propose another algorithm that can exhaustively generate all $egr(v,k,g,\lambda)$ graphs for fixed parameters $v, k, g$ and $\lambda$. We implement this algorithm and use it in a large-scale computation to obtain several new extremal graphs and improvements for lower and upper bounds from the literature for $n(k,g,\lambda)$. Among others, we show that $n(3,6,2)=24, n(3,8,8)=40, n(3,9,6)=60, n(3,9,8)=60, n(4,5,1)=30, n(4,6,9)=35, n(6,5,20)=42$ and we disprove a conjecture made by Araujo-Pardo and Leemans [Discrete Math. 345(10):112991 (2022)] for the cubic girth 8 and girth 12 cases. Based on our computations, we conjecture that $n(3,7,6)=n(3,8,10)=n(3,8,12)=n(3,8,14)=\infty.$

View PDF Chat

Some Results on Critical ($P_5,H$)-free Graphs

2024-03-08

Xia Wen , Jorik Jooken , Jan Goedgebeur +1 more

Given two graphs $H_1$ and $H_2$, a graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ nor $H_2$. A graph $G$ is $k$-vertex-critical if every proper induced … Given two graphs $H_1$ and $H_2$, a graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ nor $H_2$. A graph $G$ is $k$-vertex-critical if every proper induced subgraph of $G$ has chromatic number less than $k$, but $G$ has chromatic number $k$. The study of $k$-vertex-critical graphs for specific graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there exists a polynomial-time certifying algorithm to decide the $k$-colorability of a graph in the class. In this paper, we show that: (1) for $k \ge 1$, there are finitely many $k$-vertex-critical $(P_5,K_{1,4}+P_1)$-free graphs; (2) for $s \ge 1$, there are finitely many 5-vertex-critical $(P_5,K_{1,s}+P_1)$-free graphs; (3) for $k \ge 1$, there are finitely many $k$-vertex-critical $(P_5,\overline{K_3+2P_1})$-free graphs. Moreover, we characterize all $5$-vertex-critical $(P_5,H)$-free graphs where $H \in \{K_{1,3}+P_1,K_{1,4}+P_1,\overline{K_3+2P_1}\}$ using an exhaustive graph generation algorithm.

View PDF Chat

Minimal obstructions to $C_5$-coloring in hereditary graph classes

2024-04-17

Jan Goedgebeur , Jorik Jooken , Karolina Okrasa +2 more

For graphs $G$ and $H$, an $H$-coloring of $G$ is an edge-preserving mapping from $V(G)$ to $V(H)$. Note that if $H$ is the triangle, then $H$-colorings are equivalent to $3$-colorings. … For graphs $G$ and $H$, an $H$-coloring of $G$ is an edge-preserving mapping from $V(G)$ to $V(H)$. Note that if $H$ is the triangle, then $H$-colorings are equivalent to $3$-colorings. In this paper we are interested in the case that $H$ is the five-vertex cycle $C_5$. A minimal obstruction to $C_5$-coloring is a graph that does not have a $C_5$-coloring, but every proper induced subgraph thereof has a $C_5$-coloring. In this paper we are interested in minimal obstructions to $C_5$-coloring in $F$-free graphs, i.e., graphs that exclude some fixed graph $F$ as an induced subgraph. Let $P_t$ denote the path on $t$ vertices, and let $S_{a,b,c}$ denote the graph obtained from paths $P_{a+1},P_{b+1},P_{c+1}$ by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to $C_5$-coloring among $F$-free graphs, where $F \in \{ P_8, S_{2,2,1}, S_{3,1,1}\}$ and explicitly determine all such obstructions. This extends the results of Kami\'nski and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of $P_7$-free minimal obstructions to $C_5$-coloring, and of D\k{e}bski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique $S_{2,1,1}$-free minimal obstruction to $C_5$-coloring. We complement our results with a construction of an infinite family of minimal obstructions to $C_5$-coloring, which are simultaneously $P_{13}$-free and $S_{2,2,2}$-free. We also discuss infinite families of $F$-free minimal obstructions to $H$-coloring for other graphs $H$.

View PDF Chat

Improved asymptotic upper bounds for the minimum number of longest cycles in regular graphs

2024-06-05

Jorik Jooken

On Graphs Isomorphic with Their Conduction Graph

2024-01-01

Aidan Birkinshaw , Patrick W. Fowler , Jan Goedgebeur +1 more

Conduction graphs are defined here in order to elucidate at a glance the often complicated conduction behaviour of molecular graphs as ballistic molecular conductors. The graph $G^{\mathrm C}$ describes all … Conduction graphs are defined here in order to elucidate at a glance the often complicated conduction behaviour of molecular graphs as ballistic molecular conductors. The graph $G^{\mathrm C}$ describes all possible conducting devices associated with a given base graph $G$ within the context of the Source-and-Sink-Potential model of ballistic conduction. The graphs $G^{\mathrm C}$ and $G$ have the same vertex set, and each edge $xy$ in $G^{\mathrm C}$ represents a conducting device with graph $G$ and connections $x$ and $y$ that conducts at the Fermi level. If $G^{\mathrm C}$ is isomorphic with the simple graph $G$ (in which case we call $G$ conduction-isomorphic), then $G$ has nullity $\eta(G)=0$ and is an ipso omni-insulator. Motivated by this, examples are provided of ipso omni-insulators of odd order, thereby answering a recent question. For $\eta(G)=0$, $G^{\mathrm C}$ is obtained by 'booleanising' the inverse adjacency matrix $A^{-1}(G)$, to form $A(G^{\mathrm C})$, i.e. by replacing all non-zero entries $(A(G)^{-1})_{xy}$ in the inverse by $1+\delta_{xy}$ where $\delta_{xy}$ is the Kronecker delta function. Constructions of conduction-isomorphic graphs are given for the cases of $G$ with minimum degree equal to two or any odd integer. Moreover, it is shown that given any connected non-bipartite conduction-isomorphic graph $G$, a larger conduction-isomorphic graph $G'$ with twice as many vertices and edges can be constructed. It is also shown that there are no 3-regular conduction-isomorphic graphs. A census of small (order $\leq 11$) connected conduction-isomorphic graphs and small (order $\leq 22$) connected conduction-isomorphic graphs with maximum degree at most three is given. For $\eta(G)=1$, it is shown that $G^{\mathrm C}$ is connected if and only if $G$ is a nut graph (a singular graph of nullity one that has a full kernel vector).

View PDF Chat

On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration

2024-08-26

Robert Jajcay , Jorik Jooken , István Porupsánszki

A vertex-girth-regular $vgr(v,k,g,\lambda)$-graph is a $k$-regular graph of girth $g$ and order $v$ in which every vertex belongs to exactly $\lambda$ cycles of length $g$. While all vertex-transitive graphs are … A vertex-girth-regular $vgr(v,k,g,\lambda)$-graph is a $k$-regular graph of girth $g$ and order $v$ in which every vertex belongs to exactly $\lambda$ cycles of length $g$. While all vertex-transitive graphs are necessarily vertex-girth-regular, the majority of vertex-girth-regular graphs are not vertex-transitive. Similarly, while many of the smallest $k$-regular graphs of girth $g$, the so-called $(k,g)$-cages, are vertex-girth-regular, infinitely many vertex-girth-regular graphs of degree $k$ and girth $g$ exist for many pairs $k,g$. Due to these connections, the study of vertex-girth-regular graphs promises insights into the relations between the classes of extremal, highly symmetric, and locally regular graphs of given degree and girth. This paper lays the foundation to such study by investigating the fundamental properties of $vgr(v,k,g,\lambda)$-graphs, specifically the relations necessarily satisfied by the parameters $v,k,g$ and $\lambda$ to admit the existence of a corresponding vertex-girth-regular graph, by presenting constructions of infinite families of $vgr(v,k,g,\lambda)$-graphs, and by establishing lower bounds on the number $v$ of vertices in a $vgr(v,k,g,\lambda)$-graph. It also includes computational results determining the orders of smallest cubic and quartic graphs of small girths.

View PDF Chat

Cubic graphs of given girth and connectivity with a unique longest cycle

2024-09-25

Jorik Jooken , Carol T. Zamfirescu

We show that there exists an infinite family of cubic $2$-connected non-hamiltonian graphs with girth at least $5$ containing a unique longest cycle. We show that there exists an infinite family of cubic $2$-connected non-hamiltonian graphs with girth at least $5$ containing a unique longest cycle.

View PDF Chat

Computational methods for finding bi-regular cages

2024-11-26

Jan Goedgebeur , Jorik Jooken , Tibo Van den Eede

An $(\{r,m\};g)$-graph is a (simple, undirected) graph of girth $g\geq3$ with vertices of degrees $r$ and $m$ where $2 \leq r < m$ . Given $r,m,g$, we seek the $(\{r,m\};g)$-graphs … An $(\{r,m\};g)$-graph is a (simple, undirected) graph of girth $g\geq3$ with vertices of degrees $r$ and $m$ where $2 \leq r < m$ . Given $r,m,g$, we seek the $(\{r,m\};g)$-graphs of minimum order, called $(\{r,m\};g)$-cages or bi-regular cages, whose order is denoted by $n(\{r,m\};g)$. In this paper, we use computational methods for finding $(\{r,m\};g)$-graphs of small order. Firstly, we present an exhaustive generation algorithm, which leads to $\unicode{x2013}$ previously unknown $\unicode{x2013}$ exhaustive lists of $(\{r,m\};g)$-cages for 24 different triples $(r,m,g)$. This also leads to the improvement of the lower bound of $n(\{4,5\};7)$ from 66 to 69. Secondly, we improve 49 upper bounds of $n(\{r,m\};g)$ based on constructions that start from $r$-regular graphs. Lastly, we generalize a theorem by Aguilar, Araujo-Pardo and Berman [arXiv:2305.03290, 2023], leading to 73 additional improved upper bounds.

View PDF Chat

On $(k,g)$-Graphs without $(g+1)$-Cycles

2024-11-28

Leonard Chidiebere Eze , Robert Jajcay , Jorik Jooken

A $(k,g,\underline{g+1})$-graph is a $k$-regular graph of girth $g$ which does not contain cycles of length $g+1$. Such graphs are known to exist for all parameter pairs $k \geq 3, … A $(k,g,\underline{g+1})$-graph is a $k$-regular graph of girth $g$ which does not contain cycles of length $g+1$. Such graphs are known to exist for all parameter pairs $k \geq 3, g \geq 3 $, and we focus on determining the orders $n(k,g,\underline{g+1})$ of the smallest $(k,g,\underline{g+1})$-graphs. This problem can be viewed as a special case of the previously studied Girth-Pair Problem, the problem of finding the order of a smallest $k$-regular graph in which the length of a smallest even length cycle and the length of a smallest odd length cycle are prescribed. When considering the case of an odd girth $g$, this problem also yields results towards the Cage Problem, the problem of finding the order of a smallest $k$-regular graph of girth $g$. We establish the monotonicity of the function $n(k,g,\underline{g+1})$ with respect to increasing $g$, and present universal lower bounds for the values $n(k,g,\underline{g+1})$. We propose an algorithm for generating all $(k,g,\underline{g+1})$-graphs on $n$ vertices, use this algorithm to determine several of the smaller values $n(k,g,\underline{g+1})$, and discuss various approaches to finding smallest $(k,g,\underline{g+1})$-graphs within several classes of highly symmetrical graphs.

View PDF Chat

Critical $(P_5,W_4)$-Free Graphs

2025-01-08

Xia Wen , Jorik Jooken , Jan Goedgebeur +3 more

A graph $G$ is $k$-vertex-critical if $\chi(G) = k$ but $\chi(G-v)<k$ for all $v \in V(G)$. A graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ nor … A graph $G$ is $k$-vertex-critical if $\chi(G) = k$ but $\chi(G-v)<k$ for all $v \in V(G)$. A graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ nor $H_2$. A $W_4$ is the graph consisting of a $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. We show that there are finitely many $k$-vertex-critical $(P_5,W_4)$-free graphs for all $k \ge 1$ and we characterize all $5$-vertex-critical $(P_5,W_4)$-free graphs. Our results imply the existence of a polynomial-time certifying algorithm to decide the $k$-colorability of $(P_5,W_4)$-free graphs for each $k \ge 1$ where the certificate is either a $k$-coloring or a $(k+1)$-vertex-critical induced subgraph.

View PDF Chat

Sharp results for the Erd\H{o}s, Pach, Pollack and Tuza problem

2025-02-12

Stijn Cambie , Jorik Jooken

We consider the Erd\H{o}s, Pach, Pollack and Tuza problem, asking for the maximum diameter of a graph with given order $n$, minimum degree $\delta$ and clique number at most $\omega$. … We consider the Erd\H{o}s, Pach, Pollack and Tuza problem, asking for the maximum diameter of a graph with given order $n$, minimum degree $\delta$ and clique number at most $\omega$. We solve their problem asymptotically for the first hard case, $\omega \leq 3$, for the smallest values of $\delta$ by determining the smallest rational number $f(\delta)$ such that $diam(G) \leq f(\delta)n+O(1)$ for all graphs $G$ with order $n$, minimum degree $\delta$ and clique number $\omega \leq 3$. We also consider the weaker version where the clique number $\omega \leq 3$ is replaced by having chromatic number $\chi \leq 3$ and solve this version for small $\delta$, thereby yielding a counterexample to a conjecture of Erd\H{o}s et al. in a regime where this conjecture was still open. When restricting the conjecture to graphs with chromatic number $\chi \leq 3$, we show that this counterexample appears for the smallest possible $\delta$, namely $\delta=16.$

View PDF Chat

Exhaustive Generation of Edge-Girth-Regular Graphs

2025-05-06

Jan Goedgebeur , Jorik Jooken

View PDF Chat

Exhaustive Generation of Edge-Girth-Regular Graphs

2025-05-06

Jan Goedgebeur , Jorik Jooken

View PDF Chat

The Maximum Number of Connected Sets in Regular Graphs

2025-02-14

Stijn Cambie , Jorik Jooken , Jan Goedgebeur

Sharp results for the Erd\H{o}s, Pach, Pollack and Tuza problem

2025-02-12

Stijn Cambie , Jorik Jooken

View PDF Chat

Critical $(P_5,W_4)$-Free Graphs

2025-01-08

Xia Wen , Jorik Jooken , Jan Goedgebeur +3 more

View PDF Chat

Some Results on Critical ($$P_5,H$$)-Free Graphs

2025-01-01

Xia Wen , Jorik Jooken , Jan Goedgebeur +1 more

On $(k,g)$-Graphs without $(g+1)$-Cycles

2024-11-28

Leonard Chidiebere Eze , Robert Jajcay , Jorik Jooken

View PDF Chat

Computational methods for finding bi-regular cages

2024-11-26

Jan Goedgebeur , Jorik Jooken , Tibo Van den Eede

View PDF Chat

Cubic graphs of given girth and connectivity with a unique longest cycle

2024-09-25

Jorik Jooken , Carol T. Zamfirescu

View PDF Chat

On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration

2024-08-26

Robert Jajcay , Jorik Jooken , István Porupsánszki

View PDF Chat

Improved asymptotic upper bounds for the minimum number of longest cycles in regular graphs

2024-06-05

Jorik Jooken

Minimal obstructions to $C_5$-coloring in hereditary graph classes

2024-04-17

Jan Goedgebeur , Jorik Jooken , Karolina Okrasa +2 more

View PDF Chat

Some Results on Critical ($P_5,H$)-free Graphs

2024-03-08

Xia Wen , Jorik Jooken , Jan Goedgebeur +1 more

View PDF Chat

Few hamiltonian cycles in graphs with one or two vertex degrees

2024-01-17

Jan Goedgebeur , Jorik Jooken , On‐Hei Solomon Lo +2 more

View PDF Chat

A note on $\bar{X}$-coloring and $\hat{A}$-coloring 4-regular graphs

2024-01-01

Jorik Jooken

View PDF Chat

Exhaustive generation of edge-girth-regular graphs

2024-01-01

Jan Goedgebeur , Jorik Jooken

View PDF Chat

On Graphs Isomorphic with Their Conduction Graph

2024-01-01

Aidan Birkinshaw , Patrick W. Fowler , Jan Goedgebeur +1 more

View PDF Chat

Critical $$(P_5,dart)$$-Free Graphs

2023-12-08

Xia Wen , Jorik Jooken , Jan Goedgebeur +1 more

Features for the 0-1 knapsack problem based on inclusionwise maximal solutions

2023-04-18

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

View PDF Chat

Improved asymptotic upper bounds for the minimum number of pairwise distinct longest cycles in regular graphs

2023-01-01

Jorik Jooken

The maximum number of connected sets in regular graphs

2023-01-01

Stijn Cambie , Jan Goedgebeur , Jorik Jooken

View PDF Chat

Counterexamples to conjectures on the occupancy fraction of graphs

2023-01-01

Stijn Cambie , Jorik Jooken

View PDF Chat

Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems

2022-11-05

Jorik Jooken , Pieter Leyman , Tony Wauters +1 more

View PDF Chat

Evolving test instances of the Hamiltonian completion problem

2022-09-17

Thibault Lechien , Jorik Jooken , Patrick De Causmaecker

View PDF Chat

Few hamiltonian cycles in graphs with one or two vertex degrees

2022-01-01

Jan Goedgebeur , Jorik Jooken , On‐Hei Solomon Lo +2 more

View PDF Chat

Features for the 0-1 knapsack problem based on inclusionwise maximal solutions

2022-01-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

View PDF Chat

A heuristic algorithm using tree decompositions for the maximum happy vertices problem

2022-01-01

Louis Carpentier , Jorik Jooken , Jan Goedgebeur

Exploring search space trees using an adapted version of Monte Carlo tree search for a combinatorial optimization problem.

2020-10-22

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker +1 more

A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs

2020-07-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

View PDF Chat

Evolving test instances of the Hamiltonian completion problem

2020-01-01

Thibault Lechien , Jorik Jooken , Patrick De Causmaecker

View PDF Chat

Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems

2020-01-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker +1 more

View PDF Chat

A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs

2019-04-24

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs

2019-01-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

View PDF Chat

Coauthor	Papers Together
Jan Goedgebeur	14
Patrick De Causmaecker	10
Pieter Leyman	8
Xia Wen	4
Stijn Cambie	4
Shenwei Huang	4
Tony Wauters	3
Carol T. Zamfirescu	3
Ben Seamone	2
Robert Jajcay	2
On‐Hei Solomon Lo	2
Thibault Lechien	2
Paweł Rzążewski	1
Patrick W. Fowler	1
Oliver Schaudt	1
Louis Carpentier	1
Iain Beaton	1
Karolina Okrasa	1
István Porupsánszki	1
Ben Cameron	1
Aidan Birkinshaw	1
Leonard Chidiebere Eze	1
Tibo Van den Eede	1

House of Graphs 2.0: A database of interesting graphs and more

2022-11-07

Kris Coolsaet , Sven D’hondt , Jan Goedgebeur

View PDF Chat

A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs

2020-07-01

Jorik Jooken , Pieter Leyman , Patrick De Causmaecker

View PDF Chat

Discrete-Variable Extremum Problems

1957-04-01

George B. Dantzig

This paper reviews some recent successes in the use of linear programming methods for the solution of discrete-variable extremum problems. One example of the use of the multistage approach of … This paper reviews some recent successes in the use of linear programming methods for the solution of discrete-variable extremum problems. One example of the use of the multistage approach of dynamic programming for this purpose is also discussed.

Practical graph isomorphism, II

2013-09-27

Brendan D. McKay , Adolfo Piperno

View PDF Chat

Constructions of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si11.gif" display="inline" overflow="scroll"><mml:mi>k</mml:mi></mml:math>-critical<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si12.gif" display="inline" overflow="scroll"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>-free graphs

2014-06-27

Chı́nh T. Hoàng , Brian Moore , Daniel Recoskie +2 more

k-Critical graphs in P5-free graphs

2021-02-24

Kathie Cameron , Jan Goedgebeur , Shenwei Huang +1 more

View PDF Chat

A Certifying Algorithm for 3-Colorability of P 5-Free Graphs

2009-01-01

Daniel Bruce , Chı́nh T. Hoàng , Joe Sawada

View PDF Chat

On $3$-Colorable $P_5$-Free Graphs

2012-01-01

Frédéric Maffray , Grégory Morel

A graph is $P_5$-free when it does not contain a $P_5$ (that is, a path with five vertices) as an induced subgraph. The class of $P_5$-free graphs is of particular … A graph is $P_5$-free when it does not contain a $P_5$ (that is, a path with five vertices) as an induced subgraph. The class of $P_5$-free graphs is of particular interest, especially with respect to the still unknown complexity status of the maximum stable set problem in that class. We investigate the class of $3$-colorable $P_5$-free graphs. We give a complete description of the structure of those graphs and derive a linear-time algorithm that tests membership in this class. Moreover, the algorithm is able to find a maximum weight stable set of a $3$-colorable $P_5$-free graph in linear time.

The strong perfect graph theorem

2006-07-01

Maria Chudnovsky , Neil Robertson , Paul Seymour +1 more

A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge … A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one.The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge.A stronger conjecture was made recently by Conforti, Cornuéjols and Vušković -that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge's conjecture cannot have either of these properties).In this paper we prove both of these conjectures.

View PDF Chat

Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs

1998-01-01

Carsten Thomassen

Emergence of Scaling in Random Networks

1999-10-15

Albert‐László Barabási , Réka Albert

Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex … Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

View PDF Chat

Hamiltonian circuits in random graphs

1976-01-01

L. Pósa

Regular Graphs with Given Girth and Restricted Circuits

1963-01-01

H. Sachs

Hamiltonian completions of sparse random graphs

2005-07-15

David Gamarnik , Maxim Sviridenko

The total interval number of a tree and the Hamiltonian completion number of its line graph

1995-12-01

Arundhati Raychaudhuri

Zum Hilbertschen Aufbau der reellen Zahlen

1928-12-01

Wilhelm Ackermann

Spanning cycles of nearly cubic graphs

1980-12-01

R. C. Entringer , Henda C. Swart

Advances on the Hamiltonian Completion Problem

1975-07-01

S. E. Goodman , Stephen T. Hedetniemi , Peter J. B. Slater

article Free Access Share on Advances on the Hamiltonian Completion Problem Authors: S. E. Goodman Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied … article Free Access Share on Advances on the Hamiltonian Completion Problem Authors: S. E. Goodman Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , S. T. Hedetniemi Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , P. J. Slater National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, Iowa National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, IowaView Profile Authors Info & Claims Journal of the ACMVolume 22Issue 3July 1975 pp 352–360https://doi.org/10.1145/321892.321897Published:01 July 1975Publication History 18citation522DownloadsMetricsTotal Citations18Total Downloads522Last 12 Months18Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

On color-critical (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si4.gif" display="inline" overflow="scroll"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>,co-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si4.gif" display="inline" overflow="scroll"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>)-free graphs

2016-06-15

Harjinder S. Dhaliwal , Angèle M. Hamel , Chı́nh T. Hoàng +3 more

On the Minimum Number of Hamiltonian Cycles in Regular Graphs

2017-04-03

Michael Haythorpe

A graph construction that produces a k-regular graph on n vertices for any choice of k ⩾ 3 and n = m(k + 1) for integer m ⩾ 2 is … A graph construction that produces a k-regular graph on n vertices for any choice of k ⩾ 3 and n = m(k + 1) for integer m ⩾ 2 is described. The number of Hamiltonians cycles in such graphs can be explicitly determined as a function of n and k, and empirical evidence is provided that suggests that this function gives a tight upper bound on the minimum number of Hamiltonian cycles in k-regular graphs on n vertices for k ⩾ 5 and n ⩾ k + 3. An additional graph construction for 4-regular graphs is described for which the number of Hamiltonian cycles is superior to the above function in the case when k = 4 and n ⩾ 11.

View PDF Chat

Exhaustive generation of <i>k</i>‐critical ‐free graphs

2017-04-28

Jan Goedgebeur , Oliver Schaudt

Abstract We describe an algorithm for generating all k ‐critical ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H … Abstract We describe an algorithm for generating all k ‐critical ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H ‐free, k ‐chromatic, and every H ‐free proper subgraph of G is ‐colorable). Using this algorithm, we prove that there are only finitely many 4‐critical ‐free graphs, for both and . We also show that there are only finitely many 4‐critical ‐free graphs. For each of these cases we also give the complete lists of critical graphs and vertex‐critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3‐colorability problem in the respective classes. In addition, we prove a number of characterizations for 4‐critical H ‐free graphs when H is disconnected. Moreover, we prove that for every t , the class of 4‐critical planar ‐free graphs is finite. We also determine all 52 4‐critical planar P 7 ‐free graphs. We also prove that every P 11 ‐free graph of girth at least five is 3‐colorable, and show that this is best possible by determining the smallest 4‐chromatic P 12 ‐free graph of girth at least five. Moreover, we show that every P 14 ‐free graph of girth at least six and every P 17 ‐free graph of girth at least seven is 3‐colorable. This strengthens results of Golovach et al.

View PDF Chat

Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

2017-01-01

David Silver , Thomas Hubert , Julian Schrittwieser +7 more

The game of chess is the most widely-studied domain in the history of artificial intelligence. The strongest programs are based on a combination of sophisticated search techniques, domain-specific adaptations, and … The game of chess is the most widely-studied domain in the history of artificial intelligence. The strongest programs are based on a combination of sophisticated search techniques, domain-specific adaptations, and handcrafted evaluation functions that have been refined by human experts over several decades. In contrast, the AlphaGo Zero program recently achieved superhuman performance in the game of Go, by tabula rasa reinforcement learning from games of self-play. In this paper, we generalise this approach into a single AlphaZero algorithm that can achieve, tabula rasa, superhuman performance in many challenging domains. Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved within 24 hours a superhuman level of play in the games of chess and shogi (Japanese chess) as well as Go, and convincingly defeated a world-champion program in each case.

Graphs with few hamiltonian cycles

2019-06-12

Jan Goedgebeur , Barbara Meersman , Carol T. Zamfirescu

We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number $k \ge 0$ of hamiltonian cycles, which is especially efficient for small $k$. Our main … We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number $k \ge 0$ of hamiltonian cycles, which is especially efficient for small $k$. Our main findings, combining applications of this algorithm and existing algorithms with new theoretical results, revolve around graphs containing exactly one hamiltonian cycle (1H) or exactly three hamiltonian cycles (3H). Motivated by a classic result of Smith and recent work of Royle, we show that there exist nearly cubic 1H graphs of order $n$ iff $n \ge 18$ is even. This gives the strongest form of a theorem of Entringer and Swart, and sheds light on a question of Fleischner originally settled by Seamone. We prove equivalent formulations of the conjecture of Bondy and Jackson that every planar 1H graph contains two vertices of degree 2, verify it up to order 16, and show that its toric analogue does not hold. We treat Thomassen's conjecture that every hamiltonian graph of minimum degree at least $3$ contains an edge such that both its removal and its contraction yield hamiltonian graphs. We also verify up to order 21 the conjecture of Sheehan that there is no 4-regular 1H graph. Extending work of Schwenk, we describe all orders for which cubic 3H triangle-free graphs exist. We verify up to order $48$ Cantoni's conjecture that every planar cubic 3H graph contains a triangle, and show that there exist infinitely many planar cyclically 4-edge-connected cubic graphs with exactly four hamiltonian cycles, thereby answering a question of Chia and Thomassen. Finally, complementing work of Sheehan on 1H graphs of maximum size, we determine the maximum size of graphs containing exactly one hamiltonian path and give, for every order $n$, the exact number of such graphs on $n$ vertices and of maximum size.

View PDF Chat

Long cycles in Hamiltonian graphs

2018-10-23

António Girão , Teeradej Kittipassorn , Bhargav Narayanan

View PDF Chat

Certifying coloring algorithms for graphs without long induced paths

2018-11-02

Marcin Kamiński , Anna Pstrucha

View PDF Chat

Regular Graphs with Few Longest Cycles

2022-03-01

Carol T. Zamfirescu

Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant $c$ such that there is an infinite family of 4-regular 4-connected graphs, each containing … Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant $c$ such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly $c$ Hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput [European J. Combin., 97 (2021), 103395], and that it holds for 4-regular graphs of connectivity 2 with the constant $144 < c$, which we believe to be minimal among all Hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every nonnegative integer $k$ there is a 5-regular graph on $26 + 6k$ vertices with $2^{k+10} \cdot 3^{k+3}$ Hamiltonian cycles. We prove that for every $d \ge 3$ there is an infinite family of Hamiltonian 3-connected graphs with minimum degree $d$, with a bounded number of Hamiltonian cycles. It is shown that if a 3-regular graph $G$ has a unique longest cycle $C$, at least two components of $G - E(C)$ have an odd number of vertices on $C$, and that there exist 3-regular graphs with exactly two such components.

View PDF Chat

Uniquely Hamiltonian Graphs of Minimum Degree 4

2013-01-31

Herbert Fleischner

Abstract We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree. Abstract We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree.

Independent dominating sets and hamiltonian cycles

2006-11-16

Penny Haxell , Ben Seamone , Jacques Verstraëte

Abstract A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r ‐regular uniquely hamiltonian graphs when r > … Abstract A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r ‐regular uniquely hamiltonian graphs when r > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 2007

On random graphs. I.

2022-07-01

P. Erdős , A. Rényi

Critical (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e178" altimg="si9.svg"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>, bull)-free graphs

2023-03-14

Shenwei Huang , Jiawei Li , Xia Wen

View PDF Chat

Some results on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e421" altimg="si20.svg"><mml:mi>k</mml:mi></mml:math>-critical <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e426" altimg="si280.svg"><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>-free graphs

2023-03-21

Qingqiong Cai , Jan Goedgebeur , Shenwei Huang

View PDF Chat

Vertex-critical <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e42" altimg="si19.svg"><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mi>c</mml:mi><mml:mi>h</mml:mi><mml:mi>a</mml:mi><mml:mi>i</mml:mi><mml:mi>r</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>-free graphs

2023-08-08

Shenwei Huang , Zeyu Li

View PDF Chat

Critical $$(P_5,dart)$$-Free Graphs

2023-12-08

Xia Wen , Jorik Jooken , Jan Goedgebeur +1 more

Planar graphs, regular graphs, bipartite graphs and Hamiltonicity.

1999-01-01

Derek Holton , R. E. L. Aldred

An Efficient Dynamic Sampling Policy for Monte Carlo Tree Search

2022-12-11

Gongbo Zhang , Yijie Peng , Yilong Xu

We consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of finite-horizon Markov decision process. We propose a … We consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of finite-horizon Markov decision process. We propose a dynamic sampling tree policy that efficiently allocates limited computational budget to maximize the probability of correct selection of the best action at the root node of the tree. Experimental results on Tic-Tac-Toe and Gomoku show that the proposed tree policy is more efficient than other competing methods.

View PDF Chat

Edge-girth-regular graphs

2018-05-08

Robert Jajcay , György Kiss , Štefko Miklavič

Automated Algorithm Selection: Survey and Perspectives

2018-11-26

Pascal Kerschke , Holger H. Hoos , Frank Neumann +1 more

It has long been observed that for practically any computational problem that has been intensely studied, different instances are best solved using different algorithms. This is particularly pronounced for computationally … It has long been observed that for practically any computational problem that has been intensely studied, different instances are best solved using different algorithms. This is particularly pronounced for computationally hard problems, where in most cases, no single algorithm defines the state of the art; instead, there is a set of algorithms with complementary strengths. This performance complementarity can be exploited in various ways, one of which is based on the idea of selecting, from a set of given algorithms, for each problem instance to be solved the one expected to perform best. The task of automatically selecting an algorithm from a given set is known as the per-instance algorithm selection problem and has been intensely studied over the past 15 years, leading to major improvements in the state of the art in solving a growing number of discrete combinatorial problems, including propositional satisfiability and AI planning. Per-instance algorithm selection also shows much promise for boosting performance in solving continuous and mixed discrete/continuous optimisation problems. This survey provides an overview of research in automated algorithm selection, ranging from early and seminal works to recent and promising application areas. Different from earlier work, it covers applications to discrete and continuous problems, and discusses algorithm selection in context with conceptually related approaches, such as algorithm configuration, scheduling, or portfolio selection. Since informative and cheaply computable problem instance features provide the basis for effective per-instance algorithm selection systems, we also provide an overview of such features for discrete and continuous problems. Finally, we provide perspectives on future work in the area and discuss a number of open research challenges.

View PDF Chat

The Maximum Number of Connected Sets in Regular Graphs

2025-02-14

Stijn Cambie , Jorik Jooken , Jan Goedgebeur

Critical <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" id="d1e38" altimg="si20.gif"><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>6</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:mi>b</mml:mi><mml:mi>a</mml:mi><mml:mi>n</mml:mi><mml:mi>n</mml:mi><mml:mi>e</mml:mi><mml:mi>r</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>-free graphs

2018-12-21

Shenwei Huang , Tao Li , Yongtang Shi

Vertex-Critical ($$P_5$$, banner)-Free Graphs

2019-01-01

Qingqiong Cai , Shenwei Huang , Tao Li +1 more

A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem

2012-01-01

Olaf Mersmann , Bernd Bischl , Heike Trautmann +2 more

Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the … Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesman problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.

SNAP: A General Purpose Network Analysis and Graph Mining Library

2016-01-01

Jure Leskovec , Rok Sosič

Large networks are becoming a widely used abstraction for studying complex systems in a broad set of disciplines, ranging from social network analysis to molecular biology and neuroscience. Despite an … Large networks are becoming a widely used abstraction for studying complex systems in a broad set of disciplines, ranging from social network analysis to molecular biology and neuroscience. Despite an increasing need to analyze and manipulate large networks, only a limited number of tools are available for this task. Here, we describe Stanford Network Analysis Platform (SNAP), a general-purpose, high-performance system that provides easy to use, high-level operations for analysis and manipulation of large networks. We present SNAP functionality, describe its implementational details, and give performance benchmarks. SNAP has been developed for single big-memory machines and it balances the trade-off between maximum performance, compact in-memory graph representation, and the ability to handle dynamic graphs where nodes and edges are being added or removed over time. SNAP can process massive networks with hundreds of millions of nodes and billions of edges. SNAP offers over 140 different graph algorithms that can efficiently manipulate large graphs, calculate structural properties, generate regular and random graphs, and handle attributes and meta-data on nodes and edges. Besides being able to handle large graphs, an additional strength of SNAP is that networks and their attributes are fully dynamic, they can be modified during the computation at low cost. SNAP is provided as an open source library in C++ as well as a module in Python. We also describe the Stanford Large Network Dataset, a set of social and information real-world networks and datasets, which we make publicly available. The collection is a complementary resource to our SNAP software and is widely used for development and benchmarking of graph analytics algorithms.

Discrepancy-based evolutionary diversity optimization

2018-07-02

Aneta Neumann , Wanru Gao , Carola Doerr +2 more

Diversity plays a crucial role in evolutionary computation. While diversity has been mainly used to prevent the population of an evolutionary algorithm from premature convergence, the use of evolutionary algorithms … Diversity plays a crucial role in evolutionary computation. While diversity has been mainly used to prevent the population of an evolutionary algorithm from premature convergence, the use of evolutionary algorithms to obtain a diverse set of solutions has gained increasing attention in recent years. Diversity optimization in terms of features on the underlying problem allows to obtain a better understanding of possible solutions to the problem at hand and can be used for algorithm selection when dealing with combinatorial optimization problems such as the Traveling Salesperson Problem.

View PDF Chat

A census of small transitive groups and vertex-transitive graphs

2019-06-27

Derek F. Holt , Gordon Royle

View PDF Chat

Cubic vertex-transitive graphs on up to 1280 vertices

2012-09-27

Primož Potočnik , Pablo Spiga , Gabriel Verret

View PDF Chat

Few hamiltonian cycles in graphs with one or two vertex degrees

2024-01-17

Jan Goedgebeur , Jorik Jooken , On‐Hei Solomon Lo +2 more

View PDF Chat

Evolutionary diversity optimization using multi-objective indicators

2019-07-03

Aneta Neumann , Wanru Gao , Markus Wagner +1 more

Evolutionary diversity optimization aims to compute a set of solutions that are diverse in the search space or instance feature space, and where all solutions meet a given quality criterion. … Evolutionary diversity optimization aims to compute a set of solutions that are diverse in the search space or instance feature space, and where all solutions meet a given quality criterion. With this paper, we bridge the areas of evolutionary diversity optimization and evolutionary multi-objective optimization. We show how popular indicators frequently used in the area of multi-objective optimization can be used for evolutionary diversity optimization. Our experimental investigations for evolving diverse sets of TSP instances and images according to various features show that two of the most prominent multi-objective indicators, namely the hypervolume indicator and the inverted generational distance, provide excellent results in terms of visualization and various diversity indicators.

View PDF Chat

Uniquely hamiltonian graphs for many sets of degrees

2023-01-01

Gunnar Brinkmann

We give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case added for … We give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case added for completeness), all sets with minimum 3 that contain an even number (for sets without an even number it is known that no uniquely hamiltonian graphs exist), and all sets with minimum 4 and at least two elements, where all degrees different from 4 are at least 10. For minimum degree 3 and 4, the constructions also give 3-connected graphs. We also introduce the concept of seeds, which makes the above results possible and might be useful in the study of Sheehan's conjecture. Furthermore we prove that 3-connected uniquely hamiltonian 4-regular graphs exist if and only if 2-connected uniquely hamiltonian 4-regular graphs exist.

View PDF Chat

Feature-Based Diversity Optimization for Problem Instance Classification

2020-06-17

Wanru Gao , Samadhi Nallaperuma , Frank Neumann

Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Travelling Salesperson Problem (TSP). In this article, … Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Travelling Salesperson Problem (TSP). In this article, we present a general framework that is able to construct a diverse set of instances which are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances which are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.

View PDF Chat

The energy of a graph

2004-06-08

B. Ramachandran