An abdiff-tolerance competition graph, \(G = (V, E)\), is a graph for which each vertex \(i\) can be assigned a non-negative integer \(t_i\); and at most \(|V|\) subsets \(S_j\) of \(V\) can be found such that \(xy \in E\) if and only if \(x\) and \(y\) lie in at least \(|t_x – t_y|\) of the sets \(S_j\). If \(G\) is not an abdiff-tolerance competition graph, it still is possible to find \(r > |V|\) subsets of \(V\) having the above property. The integer \(r – |V|\) is called the abdiff-tolerance competition number. This paper determines those complete bipartite graphs which are abdiff-tolerance competition graphs and finds an asymptotic value for the abdiff-tolerance competition number of \(K_{l,n}\).

Let \(m \equiv 3 \pmod{6}\). We show that there exists an almost resolvable directed \(m\)-cycle system of \(D_n\) if and only if \(n \equiv 1 \pmod{m}\), except possibly if \(n \in \{3m+1, 6m+1\}\).

Let \(G\) be a connected plane bipartite graph. The \({Z}\)-transformation graph \({Z}(G)\) is a graph where the vertices are the perfect matchings of \(G\) and where two perfect matchings are joined by an edge provided their symmetric difference is the boundary of an interior face of \(G\). For a plane elementary bipartite graph \(G\) it is shown that the block graph of \({Z}\)-transformation graph \({Z}(G)\) is a path. As an immediate consequence, we have that \({Z}(G)\) has at most two vertices of degree one.

Block’s Lemma states that every automorphism group of a finite \(2-(v,k,\lambda)\) design acts with at least as many block orbits as point orbits: this is not the case for infinite designs. Evans constructed a block transitive \(2-(v,4,14)\) design with two point orbits using ideas from model theory and Camina generalized this method to construct a family of block transitive designs with two point orbits. In this paper, we generalize the method further to construct designs with \(n\) point orbits and \(l\) block orbits with \(l < n\), where both \(n\) and \(l\) are finite. In particular, we prove that for \(k \geq 4\) and \(n \leq k/2\), there exists a block transitive \(2-(v,k,\lambda)\) design, for some finite \(\lambda\), with \(n\) point orbits. We also construct \(2-(v, 4, \lambda)\) designs with automorphism groups acting with \(n\) point orbits and \(l\) block orbits, \(l < n\), for every permissible pair \((n, l)\).

Using a modification of the Kramer-Mesner method, \(4-(38,5,\lambda)\) designs are constructed with \(\text{PSL}(2,37)\) as an automorphism group and with \(\lambda\) in the set \(\{6,10,12,16\}\). It turns out also that there exists a \(4-(38,5,16)\) design with \(\text{PGL}(2,37)\) as an automorphism group.

Block’s Lemma states that every automorphism group of a finite \(2-(v,k,\lambda)\) design acts with at least as many block orbits as point orbits: this is not the case for infinite designs. Evans constructed a block transitive \(2-(v,4,14)\) design with two point orbits using ideas from model theory and Camina generalized this method to construct a family of block transitive designs with two point orbits. In this paper, we generalize the method further to construct designs with \(n\) point orbits and \(l\) block orbits with \(l < n\), where both \(n\) and \(l\) are finite. In particular, we prove that for \(k \geq 4\) and \(n \leq k/2\), there exists a block transitive \(2-(v,k,\lambda)\) design, for some finite \(\lambda\), with \(n\) point orbits. We also construct \(2-(v, 4, \lambda)\) designs with automorphism groups acting with \(n\) point orbits and \(l\) block orbits, \(l < n\), for every permissible pair \((n, l)\).

We investigate whether replicated paths and replicated cycles are graceful. We also investigate the number of different graceful labelings of the complete bipartite graph .

For positive integers \(k \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\}\) and edge set \(\{a_ib_j: 1 \leq j \leq n, j = i+1,i+2,\ldots,i+k \pmod{n}\}\). For any positive integer \(\lambda\), the multicrown \(\lambda C_{n,k}\) is the multiple graph obtained from the crown \(C_{n,k}\) by replacing each edge \(e\) by \(\lambda\) edges with the same end vertices as \(e\). A star \(S_l\) is the complete bipartite graph \(K_{1,k}\). If the edges of a graph \(G\) can be decomposed into subgraphs isomorphic to a graph \(H\), then we say that \(G\) has an \(H\)-decomposition. In this paper, we prove that \(\lambda C_{n,k}\) has an \(S_l\)-decomposition if and only if \(l \leq k\) and \(\lambda nk \equiv 0 \pmod{l}\). Thus, in particular, \(C_{n,k}\) has an \(S_l\)-decomposition if and only if \(l \leq k\) and \(nk \equiv 0 \pmod{l}\). As a consequence, we show that if \(n \geq 3, k < \frac{n}{2}\) then \(C_k^n\), the \(k\)-th power of the cycle \(C_n\), has an \(S_l\)-decomposition if and only if \(1 < k+1\) and \(nk \equiv 0 \pmod{1}\).

A set \(X\) of vertices of a graph is said to be dependent if \(X\) is not an independent set. For the graph \(G\), let \(P_k(G)\) denote the set of dependent sets of cardinality \(k\).

In this paper, we show that if \(G\) is a connected graph on \(2n\) vertices where \(n \geq 3\), then \(|P_n(G)| \geq |P_{n+1}(G)|\). This study is motivated by a conjecture of Lih.

The shares in a \((k,n)\) Shamir threshold scheme consist of \(n\) points on some polynomial of degree at most \(k-1\). If one or more of the shares are faulty, then the secret may not be reconstructed correctly. Supposing that at most \(\epsilon\) of the \(n\) shares are faulty, we show how a suitably chosen covering design can be used to compute the correct secret. We review known results on coverings of the desired type, and give some new constructions. We also consider a randomized algorithm for the same problem, and compare it with the deterministic algorithm obtained by using a particular class of coverings.