The stability number of a graph, defined as the cardinality of the largest set of pairwise non-adjacent vertices, is NP-hard to compute. The exact subgraph hierarchy (ESH) provides a sequence of increasingly tighter upper bounds on the stability number, starting with the Lovász theta function at the first level and including all exact subgraph constraints of subgraphs of order into the semidefinite program to compute the Lovász theta function at level . In this paper, we investigate the ESH for Paley graphs, a class of strongly regular, vertex-transitive graphs. We show that for Paley graphs, the bounds obtained from the ESH remain the Lovász theta function up to a certain threshold level, i.e., the bounds of the ESH do not improve up to a certain level. To overcome this limitation, we introduce the vertex-transitive ESH for the stable set problem for vertex-transitive graphs such as Paley graphs. We prove that this new hierarchy provides upper bounds on the stability number of vertex-transitive graphs that are at least as tight as those obtained from the ESH. Additionally, our computational experiments reveal that the vertex-transitive ESH produces superior bounds compared to the ESH for Paley graphs.

Let G be a graph with n vertices and m edges. One of several hierarchies towards the stability number of G is the exact subgraph hierarchy (ESH). On the first level it computes the Lovász theta function ϑ(G) as semidefinite program (SDP) with a matrix variable of order n+1 and n+m+1 constraints. On the kth level it adds all exact subgraph constraints (ESC) for subgraphs of order k to the SDP. An ESC ensures that the submatrix of the matrix variable corresponding to the subgraph is in the correct polytope. By including only some ESCs into the SDP the ESH can be exploited computationally. In this paper we introduce a variant of the ESH that computes ϑ(G) through an SDP with a matrix variable of order n and m+1 constraints. We show that it makes sense to include the ESCs into this SDP and introduce the compressed ESH (CESH) analogously to the ESH. Computationally the CESH seems favorable as the SDP is smaller. However, we prove that the bounds based on the ESH are always at least as good as those of the CESH. In computational experiments sometimes they are significantly better. We also introduce scaled ESCs (SESCs), which are a more natural way to include exactness constraints into the smaller SDP and we prove that including an SESC is equivalent to including an ESC for every subgraph.

The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs G and H is at least the product of the domination numbers of G and H. Recently Gaar, Krenn, Margulies and Wiegele used the graph class G of all graphs with nG vertices and domination number kG and reformulated Vizing's conjecture as the problem that for all graph classes G and H the Vizing polynomial is sum-of-squares (SOS) modulo the Vizing ideal. By solving semidefinite programs (SDPs) and clever guessing they derived SOS-certificates for some values of kG, nG, kH, and nH. In this paper, we consider their approach for kG=kH=1. For this case we are able to derive the unique reduced Gröbner basis of the Vizing ideal. Based on this, we deduce the minimum degree (nG+nH−1)/2 of an SOS-certificate for Vizing's conjecture, which is the first result of this kind. Furthermore, we present a method to find certificates for graph classes G and H with nG+nH−1=d for general d, which is again based on solving SDPs, but does not depend on guessing and depends on much smaller SDPs. We implement our new method in SageMath and give new SOS-certificates for all graph classes G and H with kG=kH=1 and nG+nH≤15.

If a graph G can be represented by means of paths on a grid, such that each vertex of G corresponds to one path on the grid and two vertices of G are adjacent if and only if the corresponding paths share a grid edge, then this graph is called EPG and the representation is called EPG representation. A k-bend EPG representation is an EPG representation in which each path has at most k bends. The class of all graphs that have a k-bend EPG representation is denoted by Bk. Bℓm is the class of all graphs that have a monotonic ℓ-bend EPG representation, i.e. an ℓ-bend EPG representation, where each path is ascending in both columns and rows. It is trivial that Bkm⊆Bk for all k. Moreover, it is known that Bkm⫋Bk, for k=1. By investigating the Bk-membership and the Bkm-membership of complete bipartite graphs we prove that the inclusion is also proper for k∈{2,3,5} and for k⩾7. In particular, we derive necessary conditions for this membership that have to be fulfilled by m, n and k, where m and n are the number of vertices on the two partition classes of the bipartite graph. We conjecture that Bkm⫋Bk holds also for k∈{4,6}. Furthermore, we show that Bk⁄⊆B2k−9m holds for all k⩾5. This implies that restricting the shape of the paths can lead to a significant increase of the number of bends needed in an EPG representation. So far no bounds on the amount of that increase were known. We prove that B1⊆B3m holds, providing the first result of this kind.

For non-negative integers k, we consider graphs in which every vertex has exactly k vertices at distance 2, i.e., graphs whose distance-2 graphs are k-regular. We call such graphs k-metamour-regular motivated by the terminology in polyamory. While constructing k-metamour-regular graphs is relatively easy – we provide a generic construction for arbitrary k – finding all such graphs is much more challenging. We show that only k-metamour-regular graphs with a certain property cannot be built with this construction. Moreover, we derive a complete characterization of k-metamour-regular graphs for each k=0, k=1 and k=2. In particular, a connected graph with n vertices is 2-metamour-regular if and only if n≥5 and the graph is a join of complements of cycles (equivalently every vertex has degree n−3), a cycle, or one of 17 exceptional graphs with n≤8. Moreover, a characterization of graphs in which every vertex has at most one metamour is acquired. Each characterization is accompanied by an investigation of the corresponding counting sequence of unlabeled graphs.

The discrete ‐neighbor ‐center problem (d‐‐CP) is an emerging variant of the classical ‐center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we need to locate facilities on these points in such a way that the maximum distance between each point where no facility is located and its ‐closest facility is minimized. The only existing algorithms in literature for solving the d‐‐CP are approximation algorithms and two recently proposed heuristics. In this work, we present two integer programming formulations for the d‐‐CP, together with lifting of inequalities, valid inequalities, inequalities that do not change the optimal objective function value and variable fixing procedures. We provide theoretical results on the strength of the formulations and convergence results for the lower bounds obtained after applying the lifting procedures or the variable fixing procedures in an iterative fashion. Based on our formulations and theoretical results, we develop branch‐and‐cut (B&C ) algorithms, which are further enhanced with a starting heuristic and a primal heuristic. We evaluate the effectiveness of our B&C algorithms using instances from literature. Our algorithms are able to solve 116 out of 194 instances from literature to proven optimality, with a runtime of under a minute for most of them. By doing so, we also provide improved solution values for 116 instances.

We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of discrete bilevel optimization. Using these disjunctive cuts, we establish a branch-and-cut algorithm for the problem class we study, and a cutting plane method for the problem variant with only binary variables. We present a preliminary computational study on instances with no second-order cone constraints at the upper level and a single linear constraint at the lower level. Our study demonstrates that both our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our test instances, where the non-linearities are linearized in a McCormick fashion.

Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz existence question. In particular, we select classes of graphs according to their number of vertices and their domination number and encode the conjecture as an ideal/polynomial pair such that the polynomial is non-negative on the variety associated with the ideal if and only if the conjecture is true for this graph class. Using semidefinite programming we obtain numeric sum-of-squares certificates, which we then manage to transform into symbolic certificates confirming non-negativity of our polynomials. Specifically, we obtain exact low-degree sparse sum-of-squares certificates for particular classes of graphs. The obtained certificates allow generalizations for larger graph classes. Besides computational verification of these more general certificates, we also present theoretical proofs as well as conjectures and questions for further investigations.

Vizing's conjecture (open since 1968) relates the sizes of dominating sets in two graphs to the size of a dominating set in their Cartesian product graph. In this paper, we formulate Vizing's conjecture itself as a Positivstellensatz existence question. In particular, we encode the conjecture as an ideal/polynomial pair such that the polynomial is nonnegative if and only if the conjecture is true. We demonstrate how to use semidefinite optimization techniques to computationally obtain numeric sum-of-squares certificates, and then show how to transform these numeric certificates into symbolic certificates approving nonnegativity of our polynomial.