Certain graphs whose vertices are some collection of subsets of a fixed \(n\)-set, with edges determined by set intersection in some way, have long been conjectured to be Hamiltonian. We are particularly concerned with graphs whose vertex set consists of all subsets of a fixed size \(k\), with edges determined by empty intersection, on the one hand, and with bigraphs whose vertices are all subsets of either size \(k\) or size \(n-k\), with adjacency determined by set inclusion, on the other. In this note, we verify the conjecture for some classes of these graphs. In particular, we show how to derive a Hamiltonian cycle in such a bigraph from a Hamiltonian path in a quotient of a related graph of the first kind (based on empty intersection). We also use a recent generalization of the Chvatal-Erdos theorem to show that certain of these bigraphs are indeed Hamiltonian.

We determine the minimal number of queries sufficient to find an unknown integer \(x\) between \(1\) and \(n\) if at most one answer may be erroneous. The admissible form of query is: “Which one of the disjoint sets \(A_1, \ldots, A_k\) does \(x\) belong to?”

A \(\lambda\)-packing of pairs by quintuples of a \(v\)-set \(V\) is a family of \(5\)-subsets of \(V\) (called blocks) such that every \(2\)-subset of \(V\) occurs in at most \(\lambda\) blocks. The packing number is defined to be the maximum number of blocks in such a \(\lambda\)-packing. These numbers are determined here for \(\lambda \equiv 0 \mod 4\) and all integers \(v \geq 5\) with the exceptions of \((v, \lambda) \in \{(22, 16), (22, 36), (27, 16)\}\).

Recently, there has been substantial interest in the problem of the spectrum of possible support sizes of different families of BIB designs. In this paper, we first prove some theorems concerning the spectrum of any \(t\)-design with \(v = 2k\) and \(k = t + 1\), and then we study the spectrum of the case \(4-(10, 5, 6m)\) in more detail.

We obtain bounds for the separation number of a graph in terms of simpler parameters. With the aid of these bounds, we determine the separation number for various special graphs, in particular multiples of small graphs. This leads to concepts like robustness and asymptotic separation number.

A.M. Assaf, A. Hartman, and N. Shalaby determined in [1] the packing numbers \(\sigma(v, 6, 5)\) for all integers \(v \geq 6\), leaving six open cases of \(v = 41, 47, 53, 59, 62,\) and \(71\). In this paper, we deal with these open cases and thus complete the packing problem.

A hypergraph \(H\) is called connected over a graph \(G\) with the same vertex set as \(H\) if every hyperedge of \(H\) induces a connected subgraph in \(G\). A graph \(F\) is representable in the graph \(G\) if there is some hypergraph \(H\) which is connected over \(G\) and has \(F\) as its intersection graph. Generalizing the well-known problem of representability in forests, the following problems are investigated: Which hypergraphs are connected over some \(n\)-cyclomatic graph, and which graphs are representable in some \(n\)-cyclomatic graph, for any fixed integer \(n\)? Several notions developed in the theory of subtree hypergraphs and chordal graphs (i.e. in the case \(n = 0\)) yield necessary or sufficient conditions, and in certain special cases even characterizations.