We present an optimal algorithm to label the edges of a complete graph with integer lengths so that every Hamilton cycle has the same length. The algorithm is complete in the sense that every edge-labelling with this property is the output labelling of some run of this algorithm. Such edge-labellings are induced by half-integer vertex-labellings by adding the vertex labels on an edge’s ends to determine its label. The Fibonacci sequence arises in this connection.

Two players are presented with a finite, simple graph \( G = (V, E) \) that has no isolated vertices. They take turns deleting an edge from the graph in such a way that no isolated vertex is created. The winner is the last player able to remove an edge. We analyze this game when the graph \(G\) is a path of arbitrary length. In addition, some observations are made in the situation that the graph has an automorphism of a special type.

A (previously reported) surprising and attractive hypergeometric identity is established from first principles using three hypergeometric transformations.

Computational Algebra methods have been used successfully in various problems in many fields of Mathematics. Computational Algebra encompasses a set of powerful algorithms for studying ideals in polynomial rings and solving systems of nonlinear polynomial equations efficiently. The theory of Gröbner bases is a cornerstone of Computational Algebra, since it provides us with a constructive way of computing a kind of particular basis of an ideal which enjoys some important properties. In this paper, we introduce the concept of Hadamard ideals in order to establish a new approach to the construction of Hadamard matrices with circulant core. Hadamard ideals reveal the rich interplay between Hadamard matrices with circulant core and ideals in multivariate polynomial rings. Hadamard ideals yield an exhaustive search for Hadamard matrices with circulant core for any specific dimension. In particular, we furnish all solutions for Hadamard matrices of the 12 orders 4, 8, \ldots, 44, 48 with circulant core. We establish the dihedral structure of the varieties associated with Hadamard ideals. Finally, we furnish the complete lists (exhaustive search) of inequivalent Hadamard matrices of the 12 orders 4, 8, \ldots, 44, 48 with circulant core.

Let \( K_v \) be the complete graph on \( v \) vertices, and \( C_5 \) be a cycle of length five. A simple minimum \( (v, C_5, 1) \)-covering is a pair \( (V, C) \) where \( V = V(K_v) \) and \( C \) is a family of edge-disjoint 5-cycles of minimum cardinality which partition \( E(K_v) \cup E \), for some \( E \subset E(K_v) \). The collection of edges \( E \) is called the excess. In this paper, we determine the necessary and sufficient conditions for the existence of a simple minimum \( (v, C_5, 1) \)-covering. More precisely, for each \( v \geq 6 \), we prove that there is a simple minimum \( (v, C_5, 1) \)-covering having all possible excesses.

The resolution of workshop problems, such as the Flow Shop or the Job Shop, has great importance in industrial areas. Criteria to optimize are generally the minimization of the makespan time or the tardiness time. However, few resolution approaches take into account those different criteria simultaneously. This paper presents a comparative and progressive study of different multicriteria optimization techniques. Several strategies of selection, diversity maintaining, and hybridization will be exposed. Their performances will be compared and tested. A parallel GA model is proposed, which allows increasing the population size and the limit generations number, and leads to better results. In parallel to the work on the optimization technique, we propose here a new bi-criteria flow shop benchmark, responding to the need for common problem instances in the field of multicriteria optimization.

In this paper we determine a class of critical sets in the abelian \(2\)-group that may be obtained from a greedy algorithm. These new critical sets are all \(2\)-critical (each entry intersects an intercalate, a trade of size \(4\)) and complete in a top-down manner.

In a \((k, n)\)-threshold scheme, a secret key \(K\) is split into \(n\) shares in such a way that \(K\) can be recovered from \(k\) or more shares, but no information about \(K\) can be obtained from any \(k-1\) or fewer shares. We are interested in the situation where there are some number of incorrect (i.e., faulty) shares. When there are faulty shares, we might need to examine more than \(k\) shares in order to reconstruct the secret correctly. Given an upper bound, namely \(t\), on the number of faulty shares, we focus on finding efficient algorithms for reconstructing the secret in a \((k, n)\)-threshold scheme. We call this the threshold scheme with cheaters problem.

We first review known combinatorial algorithms that use covering designs, as presented in Rees et al. [11] and Tso et al. [13]. Then we extend the ideas of their algorithms to a more general one. We also link the threshold scheme with cheaters problem to decoding generalized Reed-Solomon codes. Then we adapt two decoding algorithms, namely, the Peterson-Gorenstein-Zierler Algorithm and Gao’s Algorithm, to solve our problem. Finally, we contribute a general algorithm that combines both the combinatorial and decoding approaches, followed by an experimental analysis of all the algorithms we describe.

Let \( G \) be a simple graph, and let \( p \) be a positive integer. A subset \( D \subseteq V(G) \) is a \( p \)-\({dominating}\) set of the graph \( G \), if every vertex \( v \in V(G) – D \) is adjacent to at least \( p \) vertices of \( D \). The \( p \)-domination number \( \gamma_p(G) \) is the minimum cardinality among the \( p \)-dominating sets of \( G \). Note that the \( 1 \)-domination number \( \gamma_1(G) \) is the usual domination number \( \gamma(G) \). The covering number of a graph \( G \) is denoted by \( \beta(G) \). If \( T \) is a tree of order \( n(T) \), then Fink and Jacobson [1] proved in 1985 that

\[\gamma_p(T) \geq \frac{(p-1)n(T) + 1}{p}\]

The special case \( p = 2 \) of this inequality easily leads to

\[\gamma_2(T) \geq \beta(T) + 1 \geq \gamma(T) + 1\]

for every non-trivial tree \( T \). Inspired by the article of Fink and Jacobson [1], we characterize in this paper the family of trees \( T \) with \( \gamma_p(T) = \left\lceil \frac{(p-1)n(T) + 1}{p} \right\rceil \) as well as all non-trivial trees \( T \) with \( \gamma_2(T) = \gamma(T) + 1 \) and \( \gamma_2(T) = \beta(T) + 1 \).

Alliances in undirected graphs were introduced by Hedetniemi, Hedetniemi, and Kristiansen, and generalized to \( k \)-alliances by Shafique and Dutton. We translate these definitions of alliances to directed graphs. We establish basic properties of alliances and examine bounds on the size of minimal alliances in directed graphs. In general, the bounds established for alliances in undirected graphs do not hold when alliances are considered over the larger class of directed graphs and we construct examples which break these bounds.