Umeå University's logo

In this paper we determine the metric dimension of Ka×Kb×Kc for all a,b,c∈N with a≤b≤c as follows. For 3a<b+c and 2b≤c, this value is c-1, for 3a<b+c and 2b>c, it is 23(b+c-1), and for 3a=b+c, it is a+b+c2-1. The only open case is 3a>b+c, where two values are possible, namely a+b+c2-1 and a+b+c2. This result extends previous results of [4], who computed the metric dimension of Ka×Kb, and of [14], who computed the metric dimension of Ka×Ka×Ka. We prove our result by introducing and analyzing a new variant of Static Black-Peg Mastermind, in which each peg has its own permitted set of colors. For all cases, we present strategies which we prove to be both feasible and optimal. Our main result follows, as the number of questions of these strategies is equal to the metric dimension of Ka×Kb×Kc.

Optimal solutions of combinatorial optimization problems can be sensitive to changes in the cost of one or more elements of the ground set E. Single and set tolerances measure the maximum possible change for which the current solution remains optimal for cost changes in one or more elements. The current definition of single and set tolerances does not consider all elements of E or all subsets of E. In this work, we broaden the definition to include all elements for single tolerances and all subsets of elements for set tolerances, while proving that key theoretical and computational properties still apply.

We consider a logical puzzle which we call the double pouring problem, which was originally defined for k=3 vessels. We generalize this definition to k≥2 as follows. Each of the k vessels contains an integer amount of water, called its value, where the values are a_i for i=1,2,…,k and the sum of values is n. A pouring step means pouring water from one vessel with value a_i to another vessel with value a_j, where 1≤i≠j≤k and a_j≤a_i. After this pouring step the first vessel has value 2a_i and the second one value a_j−a_i. Now the pouring problem is to find as few pourings steps as possible to empty at least one vessel, or to show that such an emptying is not possible (which is possible only in the case k=2). For k=2 each pouring step is unique. We give a necessary and sufficient condition, when for a given (a₁,a₂) with a₁+a₂=n the pouring problem is solvable. For k=3 we improve the upper bound of the pouring problem for some special cases. For k≥4 we extend the known lower bound for k=3 and improve the known upper bound O((log n)²) for k=3 to O(log nlog log n). Finally, for k≥3, we investigate values and bounds for some functions related to the pouring problem.

This paper considers the computation of lower tolerances of combinatorial optimization problems with an objective of type bottleneck, in which the objective is to minimize the element with maximum cost of a feasible solution. A lower tolerance can be defined as the supremum decrease such that the objective value remains the same. We develop a computational approach for generic problems with objective of type bottleneck and two specific approaches for the Linear Bottleneck Assignment Problem and the Bottleneck Shortest Path Problem, which have a similar complexity as solution approaches for these two problems. Finally, we present some experimental results on random instances for these problems.

We computationally completely enumerate a number of types of row-column designs up to isotopism, including double, sesqui, and triple arrays as known from the literature, and two newly introduced types that we call mono arrays and AO-arrays. We calculate autotopism group sizes for the designs we generate. For larger parameter values, where complete enumeration is not feasible, we generate examples of some of the designs, and for some admissible parameter sets, we prove non-existence results. We give some explicit constructions of sesqui arrays, mono arrays and AO-arrays, in particular, we prove constructively that AO-arrays exist for all feasible parameter sets. Finally, we investigate connections to Youden rectangles and binary pseudo-Youden designs.

We determine the sensitivity of a current optimal solution to a combinatorial optimization problem to cost changes in a set of elements. In a recent study, the concept of regular set tolerances has been introduced for a combinatorial optimization problem and for three types of cost functions, namely sum, product, and bottleneck. A regular set tolerance is the supremum amount of cost changes that can be distributed in the most favorable way to multiple elements such as not to change the current optimal solution. In this paper, we introduce an alternative concept, namely the reverse set tolerance, which is a measure of the infimum amount of cost changes to multiple elements such that the current optimal solution becomes non-optimal.

We characterize the specific cases in which reverse set upper and lower tolerances have positive values and in which they are infinite. We also show a criterion for the uniqueness of an optimal solution. Furthermore, we present bounds and exact formulas for reverse set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. We discuss the similarities and differences in the results between regular and reverse set tolerances. Finally, we motivate this new concept by analyzing them for special combinatorial optimization problems with important practical applications.

We study sets of mutually orthogonal Latin rectangles (MOLR), and a natural variation of the concept of self-orthogonal Latin squares which is applicable on larger sets of mutually orthogonal Latin squares and MOLR, namely that each Latin rectangle in a set of MOLR is isotopic to each other rectangle in the set. We call such a set of MOLR co-isotopic. In the course of doing this, we perform a complete enumeration of sets of t mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7, for all t < n up to isotopism, and up to paratopism. Additionally, for larger n we enumerate co-isotopic sets of MOLR, as well as sets of MOLR where the autotopism group acts transitively on the rectangles, and we call such sets of MOLR transitive. We build the sets of MOLR row by row, and in this process we also keep track of which of the MOLR are co-isotopic and/or transitive in each step of the construction process. We use the prefix stepwise to refer to sets of MOLR with this property at each step of their construction. Sets of MOLR are connected to other discrete objects, notably finite geometries and certain regular hypergraphs. Here we observe that all projective planes of order at most 9 except the Hughes plane can be constructed from a stepwise transitive MOLR.

The AB Game is a game similar to the popular game Mastermind. We study a version of this game called Static Black-Peg AB Game. It is played by two players, the codemaker and the codebreaker. The codemaker creates a so-called secret by placing a color from a set of c colors on each of p ≤ c pegs, subject to the condition that every color is used at most once. The codebreaker tries to determine the secret by asking questions, where all questions are given at once and each question is a possible secret. As an answer the codemaker reveals the number of correctly placed colors for each of the questions. After that, the codebreaker only has one more try to determine the secret and thus to win the game. 

For given p and c, our goal is to find the smallest number k of questions the codebreaker needs to win, regardless of the secret, and the corresponding list of questions, called a (k + 1)-strategy. We present a (⌈4c/3⌉ − 1)-strategy for p = 2 for all c ≥ 2, and a ⌊(3c − 1)/2⌋-strategy for p = 3 for all c ≥ 4 and show the optimality of both strategies, i.e., we prove that no (k + 1)-strategy for a smaller k exists. 

The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given graph G=(V,E), a dominating set of G is a subset S⊆V such that every vertex in V∖S is adjacent to at least one vertex in S. Furthermore, the DSP is the problem of finding a minimum-size dominating set and the corresponding minimum size, the domination number of G. In this, work we investigate a variant of the DSP, the super dominating set problem (SDSP), which has attracted much attention during the last years. A dominating set S is called a super dominating set of G, if for every vertex u∈S¯=V∖S, there exists a v∈S such that N(v)∩S¯=N(v)∖S={u}. Analogously, the SDSP is to find a minimum-size super dominating set, and the corresponding minimum size, the super domination number of G. The decision variants of both the DSP and the SDSP have been shown to be NP-hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, r-clique sum, and the Hajós sum of two graphs. Additionally, we present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some graph classes. In particular, the number of super dominating sets for cycles has quite surprising properties as it varies between values of the set [Formula presented] based on nmod4.

In this paper we first study k × n Youden rectangles of small orders. We have enumerated all Youden rectangles for a range of small parameter values, excluding the almost square cases where k = n − 1, in a large scale computer search. In particular, we verify the previous counts for (n, k) = (7, 3), (7, 4), and extend this to the cases (11, 5), (11, 6), (13, 4) and (21, 5). For small parameter values where no Youden rectangles exist, we also enumerate rectangles where the number of symbols common to two columns is always one of two possible values, differing by 1, which we call near Youden rectangles. For all the designs we generate, we calculate the order of the autotopism group and investigate to which degree a certain transformation can yield other row-column designs, namely double arrays, triple arrays and sesqui arrays. Finally, we also investigate certain Latin rectangles with three possible pairwise intersection sizes for the columns and demonstrate that these can give rise to triple and sesqui arrays which cannot be obtained from Youden rectangles, using the transformation mentioned above.