In a secret sharing scheme, a dealer has a secret. The dealer gives each participant in the scheme a share of the secret. There is a set \(\Gamma\) of subsets of the participants with the property that any subset of participants that is in \(\Gamma\) can determine the secret. In a perfect secret sharing scheme, any subset of participants that is not in \(\Gamma\) cannot obtain any information about the secret. We will say that a perfect secret sharing scheme is ideal if all of the shares are from the same domain as the secret. Shamir and Blakley constructed ideal threshold schemes, and Benaloh has constructed other ideal secret sharing schemes. In this paper, we construct ideal secret sharing schemes for more general access structures which include the multilevel and compartmented access structures proposed by Simmons.

It is shown that the collection of all \(\dbinom{12}{5}\) quintuples chosen from a set of twelve points can be partitioned into twelve mutually disjoint \(4-(11,5,1)\) designs in precisely \(24\) non-isomorphic ways. The results obtained are then used to show that the collection of all \(\dbinom{13}{6}\) hextuples chosen from a set of thirteen points cannot be partitioned into thirteen mutually disjoint \(5-(12,6,1)\) designs.

The set of Lyndon words of length \(n\), \(\Lambda_n\), is the set obtained by choosing those strings of length \(n\) over any finite alphabet \(\Sigma\) of cardinality \(\sigma\) which are lexicographically least in the primitive or aperiodic equivalence classes determined by cyclic permutation. It is well-known that \(\Lambda_n\) is a maximal synchronizable code with bounded synchronization delay for fixed word length \(n\). If the Lyndon words of length \(n\) are represented as vertices of the \(n\)-cube, we show that they form a connected set for arbitrary alphabets. Indeed, we show that between any two Lyndon words, there is a path consisting of at most \(2n\) Lyndon words in the \(n\)-cube. Further, we show that there always exists a path of \(n(\sigma – 1) – 1\) Lyndon words in the \(n\)-cube.

The conjugation relation among the subspaces of a finite unitary geometry and its properties are studied. Then they are used to find some enumeration formulas for the subspaces of the unitary geometry, to prove a type of transitivity of the unitary group, to construct Partially Balanced Incomplete Block (PBIB) designs, and to establish the isomorphism between some known PBIB designs.

Incomplete group divisible designs (IGDDs) are the group divisible designs (GDDs) missing disjoint sub-GDDs, which need not exist. We denote by \(\text{IGDD}_\text{u}^\text{k}(v, n)\) the design \(\text{GDD}[k, 1, v; uv]\) missing a sub-\(\text{GDD}[k, 1, n; un]\). In this paper, we give the necessary condition for the existence of \(\text{IGDD}_\text{u}^\text{k}(v, n)\) and prove that the necessary condition is also sufficient for \(k = 3\).

The \({vertex \; integrity}\) of a graph \(I(G)\), is given by \(I(G) = \min_{V’} (|V’| + m(G – V’))\) where \(V’ \subseteq V(G)\) and \(m(G – V’)\) is the maximum order of a component of \(G – V’\). The \({edge \; integrity}\), \(I'(G)\), is similarly defined to be \(I'(G) = \min_{E’} (|E’| + m(G – E’))\). Both of these are measures of the resistance of networks to disruption. It is shown that for each positive integer \(k\), the family of finite graphs \(G\) with \(I'(G) \leq k\) is a lower ideal in the partial ordering of graphs by immersions. The obstruction sets for \(k\leq 4\) are determined and it is shown that the obstructions for arbitrary \(k\) are computable. For every fixed positive integer \(k\), it is decidable in time \(O(n)\) for an arbitrary graph \(G\) of order \(n\) whether \(I(G)\) is at most \(k\), and also whether \(I'(G)\) is at most \(k\). For variable \(k\), the problem of determining whether \(I'(G)\) is at most \(k\) is shown to be NP-complete, complementing a similar previous result concerning \(I(G)\).

For positive integers \(d\) and \(m\), let \(P_{d,m}(G)\) denote the property that between each pair of vertices of the graph \(G\), there are \(m\) openly disjoint paths of length at most \(d\). A collection of such paths is called a \({Menger \; path \; system}\). Minimal conditions involving various combinations of the connectivity, minimal degree, sum of degrees, and unions of neighborhoods of pairs of nonadjacent vertices that insure the existence of Menger path systems are investigated. For example, if for fixed positive integers \(d \geq 2\) and \(m\), a graph \(G\) has order \(n\), connectivity \(k \geq m\), and minimal degree \(\delta > (n – (k – m + 1)(d – 2))/{2} + m – 2\), then \(G\) has property \(P_{d,m}(G)\) for \(n\). Also, if a graph \(G\) of order \(n\) satisfies \(NC(G) > {5n}/(d + 2) + 2m\), then \(P_{d,m}(G)\) is satisfied. (A graph \(G\) satisfies \(NC(G) \geq t\) if the union of the neighborhoods of each pair of nonadjacent vertices is at least \(t\).) Other extremal results related to Menger path systems are considered.

Let \(\mathcal{G}(n, m)\) denote the class of simple graphs on \(n\) vertices and \(m\) edges, and let \(G \in \mathcal{G}(n, m)\). For suitably restricted values of \(m\), \(G\) will necessarily contain certain prescribed subgraphs such as cycles of given lengths and complete graphs. For example, if \(m > \frac{1}{4}{n}^2\), then \(G\) contains cycles of all lengths up to \(\lfloor \frac{1}{2}(n+3) \rfloor\). Recently, we have established a number of results concerning the existence of certain subgraphs (cliques and cycles) in the subgraph of \(G\) induced by the vertices of \(G\) having some prescribed minimum degree. In this paper, we present some further results of this type. In particular, we prove that every \(G \in \mathcal{G}(n, m)\) contains a pair of adjacent vertices each having degree (in \(G\)) at least \(f(n, m)\) and determine the best possible value of \(f(n, m)\). For \(m > \frac{1}{4}{n}^{2}\), we find that \(G\) contains a triangle with a pair of vertices satisfying this same degree restriction. Some open problems are discussed.