A graph \( G \) is said to be \( E_k \)-Cordial if there is an edge labeling \( f : E(G) \rightarrow \{0,1,\ldots,k-1\} \) such that, at each vertex \( v \), the sum modulo \( k \) of the labels on the edges incident with \( v \) is \( f(v) \) and it satisfies the inequalities \( |v_f(i) – v_f(j)| \leq 1 \) and \( |e_f(i) – e_f(j)| \leq 1 \), where \( v_f(s) \) and \( e_f(t) \) are, respectively, the number of vertices labeled with \( s \) and the number of edges labeled with \( t \). The map \( f \) is then called an \( E_k \)-cordial labeling of \( G \).

This paper investigates \( E_3 \)-cordiality of snakes, one point unions, path unions, and coronas involving complete graphs.

A defensive \( k \)-alliance in a graph \( G = (V,E) \) is a set of vertices \( A \subseteq V \) such that for every vertex \( v \in A \), the number of neighbors \( v \) has in \( A \) is at least \( k \) more than the number of neighbors it has in \( V – A \) (where \( k \) is a measure of the strength of the alliance). In this paper, we deal with two types of sets associated with defensive \( k \)-alliances: maximum defensive \( k \)-alliance free and minimum defensive \( k \)-alliance cover sets.

Define a set \( X \subseteq V \) to be maximum defensive \( k \)-alliance free if \( X \) does not contain any defensive \( k \)-alliance and is the largest such set. A set \( Y \subseteq V \) is called a \({minimum\; defensive \; k -alliance \;cover}\) if \( Y \) contains at least one vertex from each defensive \( k \)-alliance and is a set of minimum cardinality satisfying this property. We present bounds on the cardinalities of maximum defensive \( k \)-alliance free and minimum defensive \( k \)-alliance cover sets.

This is the first in a series of three papers in which we investigate a special class of designs that we designate as “Moore-Greig Designs”. The sobriquet is associated with the fact that ideas gleaned from two constructions, one due to E. H. Moore (1896) and the other due to M. Greig (2003), are combined to produce designs that have remarkable properties and features. A Moore-Greig Design is an RBIBD that contains, simultaneously, nested RBIBDs, nested GWhDs, many GWhDs, frames, nested frames, GWhFrames, nested GWhFrames, GWhaFrames, RRDFs, and nested RRDFs. All of these designs are Z-cyclic.

To be more precise, let \( p \) be a prime and let \( \{s_i\}_{i=1}^m \) be a monotone increasing sequence of positive integers such that \( s_i | s_{i+1} \) for all \( i, 1 \leq i \leq m-1 \). Let \( n \) be a positive integer such that \( s_m \leq n \) and \( s_m | n \). A Moore-Greig Design is a Z-cyclic \( (p^n, p^{s_m}, p^{s_m} – 1) \)-RBIBD that contains: (1) a Z-cyclic \( (p^n, p^{s_i}, p^{s_i} – 1) \)-RBIBD for each \( i, 1 \leq i \leq m-1 \), (2) a Z-cyclic \( (p^{s_i}, p^{s_m}) \) GWhD\( (p^n) \) for each \( i, 1 \leq i \leq m-1 \), (3) for each \( i, 1 \leq i \leq m-1 \), a Z-cyclic \( (p^{s_i}, p^{s_m}) \) GWhD\(_a(p^n)\) for each \( a = \frac{\alpha}{p^{s_i} – 1} \), \( \alpha = 1, 2, \ldots, p^{s_i} – 2 \), (4) a Z-cyclic \( \{p^{s_m}\} \)-frame of type \( (p^{s_m} – 1)^q \), where \( q = \frac{p^{n} – 1}{p^{s_m} – 1} \), (5) a Z-cyclic \( (p^{s_i}, p^{s_m}) \) GWhFrame of type \( (p^{s_m} – 1)^q \) for each \( i, 1 \leq i \leq m-1 \), (6) a Z-cyclic \( (p^{n} – 1, p^{s_i} – 1, p^{s_i}, 1) \)-RRDF for each \( i, 1 \leq i \leq m \).

Other than a single published example, there is no literature pertaining to GWhDs. Therefore, the infinite classes of GWhDs constructed from the Moore-Greig Designs are the first general results related to this type of design. It is also believed that many of the other designs contained within the infinite classes of Moore-Greig designs are new.

In this paper, Part I, we provide detailed descriptions of both the Moore construction and the Greig construction. In the case of the Moore construction, we supply proofs since such proofs are lacking in Moore’s paper. Also included in this paper is a description of Moore-Greig Designs corresponding to \( m = 2 \) and a discussion is given of the presence of the GWhFrames, nested designs, and the RRDFs. Our methods are such that the constructions are straightforward if one has the (associated) Galois Field.

Anti-Pasch partial Steiner triple systems (anti-Pasch PSTSs) arise in erasure codes, extremal set systems, and combinatorial design theory. Maximal anti-Pasch PSTSs correspond to erasure-resilient codes that are used for handling failures in large disk arrays. These codes support the failure of any set of 3 disks and most sets of 4 disks while having the smallest possible update penalty and check-disk overhead.

In this article, we apply a general algorithm for isomorph-free exhaustive generation of incidence structures to the specific case of anti-Pasch PSTSs. We develop and implement a distributed version of the algorithm, which is experimentally analyzed. Using this implementation, we obtain a complete, isomorph-free catalogue of the maximal anti-Pasch PSTSs of order \( v \), for \( v \leq 15 \). The enumeration and classification results for \( 10 \leq v \leq 14 \) are new and computationally nontrivial.

Consider a lottery scheme consisting of randomly selecting a winning \( t \)-set from a universal \( m \)-set, while a player participates in the scheme by purchasing a playing set of any number of \( n \)-sets from the universal set prior to the draw. The player is awarded a prize if \( k \) or more elements in the winning \( t \)-set match those of at least one of the player’s \( n \)-sets in his playing set (\( 1 \leq k \leq \min\{n,t\} \leq m \)). This is called a \( k \)-prize. The player may wish to design a \emph{smallest} playing set which guarantees the player a \( k \)-prize, no matter which winning \( t \)-set is chosen from the universal set.

In this paper, we consider the optimality of the 302 cardinality 7 (or less) lottery design listings in \verb”BELIC” R: \({Lotto \;Systems\; and\; Toto \;Systems \;to \;win\; Wheel\; Game}\), [online], [cited 2003, October 31], available from: {http://www.xs4all.nl/\(\sim\) rbelic/}, for which \( m > 20 \). It is shown, by means of a computerized search technique, that 192 of these designs are optimal, whilst 78 are not, in which case we provide optimal designs.

Then, an additional 429 upper bounds in the tables of Belic (not necessarily of cardinality 7 or less) are improved; 126 of which are optimal. Thus, apart from the 192 designs that we show to be optimal, 204 new lottery numbers are established in this paper, and a further 304 upper bounds are improved. Finally, the optimality of 54 designs of cardinality 7 or less could not be established; however, in each of these cases, a hitherto best known lower bound is provided.

For a simple graph \( G \), consider an injection \( \mu: V \cup E \rightarrow \mathbb{N} \). If for every vertex \( x \in V \) we have \( \mu(x) + \sum_{y \sim x} \mu(xy) = h \), and for every edge \( xy \in E(G) \) we have \( \mu(x) + \mu(xy) + \mu(y) = k \), for some constants \( h \) and \( k \), then \( \mu \) is a totally magic injection (TMI) of \( G \). Also, \( m_t(G) \) is the smallest number in \( \mathbb{N} \) such that there is a TMI \( \mu: V \cup E \rightarrow \{1, 2, \ldots, m_t(G)\} \). Here we study TMIs and the number \( m_t(G) \) for certain \( G \). One theorem, the Star Theorem, is useful for eliminating many classes of well-known graphs that could have a TMI. For most \( n \) and \( n_j \), the following graphs do not have a TMI: every non-star tree, \( P_n \), \( C_n \), \( W_n \), \( K_n \), and \( K_{n_1, n_2, \ldots, n_p} \). We determine \( m_t(F) \) for every forest \( F \) that has a TMI, and \( m_t(G) \) for every graph \( G \) with \( \leq 6 \) vertices that has a TMI.

For a connected graph \( G \) of order \( n \geq 3 \) and an ordered factorization \( \mathcal{F} = \{G_1, G_2, \ldots, G_k\} \) of \( G \) into \( k \) spanning subgraphs \( G_i \) (\( 1 \leq i \leq k \)), the color code of a vertex \( v \) of \( G \) with respect to \( \mathcal{F} \) is the ordered \( k \)-tuple \( c(v) = (a_1, a_2, \ldots, a_k) \) where \( a_i = \text{deg}_{G_i} v \). If distinct vertices have distinct color codes, then the factorization \( \mathcal{F} \) is called a detectable factorization of \( G \); while the detection number \(\text{det}(G)\) of \( G \) is the minimum positive integer \( k \) for which \( G \) has a detectable factorization into \( k \) factors. We study detectable factorizations of cubic graphs. It is shown that there is a unique graph \( F \) for which the Petersen graph has a detectable \( F \)-factorization into three factors. Furthermore, if \( G \) is a connected cubic graph of order \( \binom{k+2}{3} \) with \( \text{det}(G) = k \), then \( k \equiv 2 \pmod{4} \) or \( k \equiv 3 \pmod{4} \). We investigate the largest order of a connected cubic graph with prescribed detection number.

An \((2,1)\) \(\text{coloring}\) of a graph \( G = (V,E) \) is a vertex coloring \( f : V(G) \rightarrow \{0,1,2,\ldots,k\} \) such that \( |f(u) – f(v)| \geq 2 \) for all \( uv \in E(G) \) and \( |f(u) – f(v)| \geq 1 \) if \( d(u,v) = 2 \). The \({span}\) \( \lambda(G) \) is the smallest \( k \) for which \( G \) has an \( L(2,1) \) \(\text{coloring}\). A \(\text{span coloring}\) is an \( L(2,1) \) coloring whose greatest color is \( \lambda(G) \). An \( L(2,1) \)-\(\text{coloring}\) \( f \) is a full-coloring if \( f : V(G) \rightarrow \{0,1,2,\ldots,\lambda(G)\} \) is onto and \( f \) is an irreducible no-hole coloring (inh-coloring) if \( f : V(G) \rightarrow \{0,1,2,\ldots,k\} \) is onto for some \( k \) and there does not exist an \( L(2,1) \)-\(\text{coloring}\) \( g \) such that \( g(u) < f(u) \) for all \( u \in V(G) \) and \( g(v) < f(v) \) for some \( v \in V(G) \). The Assignment sum of \( f \) on \( G \) is the sum of all the labels assigned to the vertices of \( G \) by the \( L(2,1) \) \(\text{coloring}\) \( f \). The \({Sum \;coloring\; number}\) of \( G \), introduced in this paper, \( \sum(G) \), is the minimum assignment sum over all the possible \( L(2,1) \) colorings of \( G \). \( f \) is a \(\text{Sum coloring}\) on \( G \) if its assignment sum equals the \({Sum\; coloring\; number}\). In this paper, we investigate the \({Sum\; coloring\; numbers}\) of certain classes of graphs. It is shown that \( \sum(P_n) = 2(n – 1) \) and \( \sum(C_n) = 2n \) for all \( n \). We also give an exact value for the Sum coloring number of a star and conjecture a bound for the Sum coloring number of an arbitrary graph \( G \) with span \( \lambda(G) \).

Let \( U(n, f) \) denote the graph with vertex set the set of unlabeled graphs of order \( n \) that have no vertex of degree greater than \( f \). Two vertices \( H \) and \( G \) of \( U(n, f) \) are adjacent if and only if \( H \) and \( G \) differ (up to isomorphism) by exactly one edge. The problem of determining the values of \( n \) and \( f \) for which \( U(n, f) \) contains a Hamilton path is investigated. There are only a few known non-trivial cases for which a Hamilton path exists. Specifically, these are \( U(5, 3) \), \( U(6, 3) \), and \( U(7, 3) \). On the other hand, there are many cases for which it is shown that no Hamilton path exists. The complete solution of this problem is unresolved.

We study nega-cyclic \(\pm 1\) matrices. We obtain preliminary results which are then used to decrease the search space. We find that there are \( 2 \), \( 4 \), \( 9 \), \( 23 \), \( 63 \), and \( 187 \) ip-equivalence classes for lengths \( 3 \), \( 5 \), \( 7 \), \( 9 \), \( 11 \), and \( 13 \) respectively. The matrices we find are used in a variant given here of the Goethals-Seidel array to form Hadamard matrices, the aim being to later check them for suitability for CDMA schemes.