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 \)-\emph{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.

For given integers \( k \) and \( \ell \), \( 3 \leq k \leq \ell \), a graphic sequence \( \pi = (d_1, d_2, \dots, d_n) \) is said to be potentially \({}_{k}C_\ell\)-graphic if there exists a realization of \( \pi \) containing \( C_r \), for each \( r \), where \( k \leq r \leq \ell \) and \( C_r \) is the cycle of length \( r \). Luo (Ars Combinatoria 64(2002)301-318) characterized the potentially \( C_\ell \)-graphic sequences without zero terms for \( r = 3, 4, 5 \). In this paper, we characterize the potentially \(\prescript{}{k}C_\ell\)-graphic sequences without zero terms for \( k = 3, 4 \leq \ell \leq 5 \) and \( k = 4, \ell = 5 \).

We show that deciding if a set of vertices is an eternal \(1\)-secure set is complete for \(\text{co-}NP^{\text{NP}}\), solving a problem stated by Goddard, Hedetniemi, and Hedetniemi \([JCMCC, \text{vol. 52}, \text{pp. 160-180}]\).

A Sarvate-Beam type of triple system is defined in the case \( v \equiv 2 \pmod{3} \) and an enumeration is given of such systems for \( v = 5 \).

Informally, a set of guards positioned on the vertices of a graph \( G \) is called eternally secure if the guards are able to respond to vertex attacks by moving a single guard along a single edge after each attack regardless of how many attacks are made. The smallest number of guards required to achieve eternal security is the eternal security number of \( G \), denoted \( es(G) \), and it is known to be no more than \( \theta_v(G) \), the vertex clique cover number of \( G \). We investigate conditions under which \( es(G) = \theta_v(G) \).

We apply Computational Algebra methods to the construction of Hadamard matrices from two circulant submatrices, given by C. H. Yang. We associate Hadamard ideals to this construction, to systematize the application of Computational Algebra methods. Our approach yields an exhaustive search for Hadamard matrices from two circulant submatrices for this construction, for the first eight admissible values \(2, 4, 8, 10, 16, 18, 20, 26\) and partial searches for the next three admissible values \(32, 34, 40\). From the solutions we found, for the admissible values \(26\) and \(34\), we located new inequivalent Hadamard matrices of orders \(52\) and \(68\) with two circulant submatrices, thus improving the lower bounds for the numbers of inequivalent Hadamard matrices of orders \(52\) and \(68\). We also propose a heuristic decoupling of one of the equations arising from this construction, which can be used together with the PSD test to search for solutions more efficiently.

A Hamilton cycle in an \( n \)-cube is said to be \( k \)-warped if its \( k \)-paths have their edges running along different parallel \( 1 \)-factors. No Hamilton cycle in the \( n \)-cube can be \( n \)-warped. The equivalence classes of Hamilton cycles in the \( 5 \)-cube are represented by the circuits associated to their corresponding minimum change-number sequences, or minimum \( H \)-circuits. This makes feasible an exhaustive search of such Hamilton cycles allowing their classification according to class cardinalities, distribution of change numbers, duplicity, reversibility, and \( k \)-warped representability, for different values of \( k < n \). This classification boils down to a detailed enumeration of a total of \( 237675 \) equivalence classes of Hamilton cycles in the \( 5 \)-cube, exactly four of which do not traverse any sub-cube. One of these four classes is the unique class of \( 4 \)-warped Hamilton cycles in the \( 5 \)-cube. In contrast, there is no \( 5 \)-warped Hamilton cycle in the \( 6 \)-cube. On the other hand, there is exactly one class of Hamilton cycles in the graph of middle levels of the \( 5 \)-cube. A representative of this class possesses an elegant geometrical and symmetrical disposition inside the \( 5 \)-cube.

The main objective of this paper is to introduce a generalization of distance called superior distance in graphs. For two vertices \( u \) and \( v \) of a connected graph, we define \( \text{D}_{u,v} = \text{N}[u] \cup \text{N}[v] \). We define a \( \text{D}_{u,v} \)-walk as a \( u \)-\( v \) walk that contains every vertex of \( \text{D}_{u,v} \). The superior distance \( \text{d}_D(u,v) \) from \( u \) to \( v \) is the length of a shortest \( \text{D}_{u,v} \)-walk. In this paper, first we give the bounds for the superior diameter of a graph and a property that relates the superior eccentricities of adjacent vertices. Finally, we investigate those graphs that are isomorphic to the superior center of some connected graph and those graphs that are isomorphic to the superior periphery of some connected graph.

For any \( h \in \mathbb{N} \), a graph \( G = (V, E) \) is said to be \( h \)-magic if there exists a labeling \( l: E(G) \to \mathbb{Z}_h – \{0\} \) such that the induced vertex set labeling \( l^+: V(G) \to \mathbb{Z}_h \) defined by

$$l^+(v) = \sum_{uv \in E(G)} l(uv)$$

is a constant map. For a given graph \( G \), the set of all \( h \in \mathbb{Z}_+ \) for which \( G \) is \( h \)-magic is called the integer-magic spectrum of \( G \) and is denoted by \( IM(G) \). The concept of integer-magic spectrum of a graph was first introduced in [4]. But unfortunately, this paper has a number of incorrect statements and theorems. In this paper, first we will correct some of those statements, then we will determine the integer-magic spectra of caterpillars.

A sequence \( S \) is potentially \( K_{m}-C_4 \)-graphical if it has a realization containing a \( K_m-C_4 \) as a subgraph. Let \( \sigma(K_m-C_4,n) \) denote the smallest degree sum such that every \( n \)-term graphical sequence \( S \) with \( \sigma(S) \geq \sigma(K_m-C_4,n) \) is potentially \( K_m-C_4 \)-graphical. In this paper, we prove that \( \sigma(K_m-C_4,n) \geq (2m-6)n-(m-3)(m-2)+2 \), for \( n \geq m \geq 4 \). We conjecture that equality holds for \( n \geq m \geq 4 \). We prove that this conjecture is true for \( m = 5 \).

In 1975, Leech introduced the problem of finding trees whose edges can be labeled with positive integers in such a way that the set of distances (sums of weights) between vertices is \(\{1, 2, \dots, \binom{n}{2}\}\), where \(n\) is the number of vertices. We refer to such trees as perfect distance trees. More generally, we define a distinct distance tree to be a weighted tree in which the distances between vertices are distinct. In this article, we focus on identifying minimal distinct distance trees. These are the distinct distance trees on \(n\) vertices that minimize the maximum distance between vertices. We determine \(M(n)\), the maximum distance in a minimal distinct distance tree on \(n\) vertices, for \(n \leq 10\), and give bounds on \(M(n)\) for \(n \geq 11\). This includes a determination of all perfect distance trees for \(n < 18\). We then consider trees according to their diameter and show that there are no further perfect distance trees with diameter at most \(3\). Finally, generalizations to graphs, forests, and distinct distance sets are considered.

A bijection \( \lambda: V \cup E \cup F \to \{1, 2, 3, \dots, |V| + |E| + |F|\} \) is called a \( d \)-antimagic labeling of type \( (1, 1, 1) \) of plane graph \( G(V, E, F) \) if the set of \( s \)-sided face weights is \( W_s = \{a_s + a_s+d, a_s+2d, \dots, a_s + (f_s-1)d\} \) for some integers \( s \), \( a_s \), and \( d \), where \( f_s \) is the number of \( s \)-sided faces and the face weight is the sum of the labels carried by that face and the edges and vertices surrounding it. In this paper, we examine the existence of \( d \)-antimagic labelings of type \( (1, 1, 1) \) for a special class of plane graphs \( {C}_a^b \).

GWhD(\(v\))s, or Generalized Whist Tournament Designs on \( v \) players, are a relatively new type of design. GWhD(\(v\))s are (near) resolvable (\(v,k,k-1\)) BIBDs. For \( k = et \), each block of the design is considered to be a game involving \( e \) teams of \( t \) players each. The design is subject to the requirements that every pair of players appears together in the same game exactly \( t-1 \) times as teammates and exactly \( k-t \) times as opponents. These conditions are referred to as the Generalized Whist Conditions, and when met, we refer to the (N)RBIBD as a (\( t, k \)) GWhD(\(v\)). When \( k = 10 \), necessary conditions on \( v \) are that \( v \equiv 0, 1 \pmod{10} \). In this study, we focus on the existence of (\(2,10\)) GWhD(\(v\)), \(v \equiv 1 \pmod{10}\). It is known that a (\(2,10,9\))-NRBIBD does not exist. Therefore, it is impossible to have a (\(2,10\)) GWhD(\(21\)). It is established here that (\(2,10\)) GWhD(\(10n+1\)) exist for all other \(v\) with at most 42 additional possible exceptions.