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,\dots ,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\mathrm{mod}4$ and all integers $v\ge 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\ge 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.

Let $s$ and $r$ be positive integers with $s\ge r$ and let $G$ be a graph. A set $I$ of vertices of $G$ is an $(r,s)$-set if no two vertices of $I$ are within distance $r$ from each other and every vertex of $G$ not in $I$ is within distance $s$ from some vertex of $I$. The minimum cardinality of an $(r,s)$-set is called the $(r,s)$-domination number and is denoted by $i_{r,s}(G)$. It is shown that if $G$ is a connected graph with at least $s>r\ge 1$ vertices, then there is a minimum $(r,s)$-set $I$ of $G$ such that for each $v\in I$, there exists a vertex $w\in V(G)–I$ at distance at least $s-r$ from $v$, but within distance $s$ from $v$, and at distance greater than $s$ from every vertex of $I–\{v\}$. Using this result, it is shown that if $G$ is a connected graph with $p\ge 9\ge 2$ vertices, then $i_{r,s}(G)<p/s$ and this bound is best possible. Further, it is shown that for $s\in \{1,2,3\}$, if $T$ is a tree on $p\ge s+1$ vertices, then $i_{r,s}(T)\le p/(s+1)$ and this bound is sharp.

We consider the problem of finding the intersection points of a pencil of lines with rational slope on the $2$-dimensional torus. We show that the intersection points belonging to all the lines in the pencil form a finite cyclic group. We also exhibit a generator for this group in terms of the coefficients of the lines. The need for the results presented in this paper arose in dealing with a discrete limited angle model for computerized tomography $(Cf.[3],[5])$.

An orthogonal double cover of the complete graph $K_n$ is a collection of $n$ spanning subgraphs $G_1,G_2,\dots ,G_n\$of\text{(}{K}_n$ such that every edge of $K_n$ belongs to exactly 2 of the $G_i$’s and every pair of $G_i$s intersect in exactly one edge.
It is proved that an orthogonal double cover exists for all $n\ge 4$, where the $G_i$’s consist of short cycles; this result also proves a conjecture of Chung and West.

The induced path number of a graph $G$ is the minimum number of subsets into which the vertex set of $G$ can be partitioned so that each subset induces a path. The induced path number is investigated for bipartite graphs. Formulas are presented for the induced path number of complete bipartite graphs and complete binary trees. The induced path number of all wheels is determined. The induced path numbers of meshes, hypercubes, and butterflies are also considered.

Triple Youden rectangles are defined and examples are given. These combinatorial arrangements constitute a special class of $k\times v$ row-and-column designs, $k<v$, with superimposed treatments from three sets, namely a single set of $v$ treatments and two sets of $k$ treatments. The structure of each of these row-and-column designs incorporates that of a symmetrical balanced incomplete block design with $v$ treatments in blocks of size $k$. Indeed, when either of the two sets of $k$ treatments is deleted from a $k\times v$  triple Youden rectangle, a $k\times v$ double Youden rectangle is obtained; when both are deleted, a $k\times v$ Youden square remains. The paper obtains an infinite class of triple Youden rectangles of size $k\times (k+1)$. Then it presents a $4\times 13$ triple Youden rectangle which provides a balanced layout for two packs of playing-cards, and a $7\times 15$ triple Youden rectangle which incorporates a particularly remarkable $7\times 15$ Youden square. Triple Youden rectangles are fully balanced in a statistical as well as a combinatorial sense, and those discovered so far are statistically very efficient.

The Hall-condition number $s(G)$ of a graph $G$ is defined and some of its fundamental properties are derived. This parameter, introduced in [6], bears a certain relation to the chromatic number $\chi (G)$ and the choice number $c(G)$ (see [3] and [7]).

One result here, that $\chi (G)–s(G)$ may be arbitrarily large, solves a problem posed in [6].

The sum of a set of graphs $G_1,G_2,\dots ,G_k$, denoted $\sum _{k=1}^k{G}_i$, is defined to be the graph with vertex set $V(G_1)\cup V(G_2)\cup \dots \cup V(G_k)$ and edge set $E(G_1)\cup E(G_2)\cup \dots \cup E(G_k)\cup \{uw:u\in V(G_i),w\in V(G_j)fori\ne j\}$. In this paper, the bandwidth $B\left(\sum _{k=1}^k{G}_i\right)$ for $|V(G_i)|=n_i\ge n_{i+1}=|v(G_{i+1})|,(1\le i<k)$ with $B(G_1)\le \lceil n_1/2\rceil$ is established. Also, tight bounds are given for $B\left(\sum _{k=1}^k{G}_i\right)$ in other cases. As consequences, the bandwidths for the sum of a set of cycles, a set of paths, and a set of trees are obtained.

The main result of this study is that if $p,q$ are primes such that $q\equiv 3(mod4),q\le 7,p\equiv 1(mod4),hef(q-1,p^{n-1}(p–1))=2$ and if there exists a Z-cyclic Wh(q+ 1) then a Z-cyclic Wh$(q{p}^n+1)$ exists forall $n\ge 0$. As an ingredient sufficient for this result we prove a version of Mann’s Lemma in the ring $Z_{q{p}^n}$.

In this paper we study the existence of perfect Mendelsohn designs without repeated blocks and give several general constructions. We prove that for $k=3$ and any $\lambda$, and $(k,\lambda )=(4,2),(4,3)$ and $(4,4)$, the necessary conditions are also sufficient for the existence of a simple $(v,k,\lambda )$-PMD, with the exceptions $(k,\lambda )=(6,1)$ and $(6,3)$.

A connected balanced bipartite graph $G$ on $2n$ vertices is almost vertex bipancyclic (i.e., $G$ has cycles of length $6,8,\dots ,2n$ through each vertex of $G$) if it satisfies the following property $P(n)$: if $x,y\in V(G)$ and $d(x,y)=3$ then $d(x)+d(y)\ge n+1$. Furthermore, all graphs except $C_4$ on $2n$ ($n\ge 3$) vertices satisfying $P(n)$ are bipancyclic (i.e., there are cycles of length $4,6,\dots ,2n$ in the graph).

Let $T(m,n)$ denote the number of $m\times n$ rectangular standard Young tableaux with the property that the difference of any two rows has all entries equal. Let $T(n)=\sum _{d|n}T(d,n/d)$. We find recurrence relations satisfied by the numbers $T(m,n)$ and $\hat{T}(n)$, compute their generating functions, and express them explicitly in some special cases.

A labeling (function) of a graph $G$ is an assignment $f$ of nonnegative integers to the vertices of $G$. Such a labeling of $G$ induces a labeling of $L(G)$, the line graph of $G$, by assigning to each edge $uv$ of $G$ the label $|f(u)–f(v)|$. In this paper we investigate the iteration of such graph labelings.

In this thesis we examine the $k$-equitability of certain graphs. We prove the following: The path on $n$ vertices, $P_n$, is $k$-equitable for any natural number $k$. The cycle on $k$ vertices, $C_n$, is $k$-equitable for any natural number $k$, if and only if all of the following conditions hold:$n\ne k$; if $k\equiv 2,3(\mathrm{mod}4)$ then $n\ne k-1$;if $k\equiv 2,3(\mathrm{mod}4)$ then $n\not\equiv k(\mathrm{mod}2k)$ The only $2$-equitable complete graphs are $K_1$, $K_2$, and $K_3$.
The complete graph on $n$ vertices, $K_n$, is not $k$-equitable for any natural number $k$ for which $3\le k<n$. If $k\ge n$, then determining the $k$-equitability of $K_n$ is equivalent to solving a well-known open combinatorial problem involving the notching of a metal bar.The star on $n+1$ vertices, $S_n$, is $k$-equitable for any natural number $k$. The complete bipartite graph $K_{2,n}$ is $k$-equitable for any natural number $k$ if and only if $n\equiv k-1(\mathrm{mod}k)$; or $n\equiv 0,1,\dots ,[k/2]–1(\mathrm{mod}k)$;or $n=\lfloor k/2\rfloor$ and $k$ is odd.

The minimal number of triples required to represent all quintuples on an $n$-element set is determined for $n\le 13$ and all extremal constructions are found. In particular, we establish that there is a unique minimal system on 13 points, namely the 52 collinear triples of the projective plane of order 3.

A set $T$ with a binary operation $+$ is called an operation set and denoted as $(T,+)$. An operation set $(S,+)$ is called $q$-free if $qx\notin S$ for all $x\in S$. Let ${\psi }_q(T)$ be the maximum possible cardinality of a $q$-free operation subset $(S,+)$ of $(T,+)$.

We obtain an algorithm for finding ${\psi }_q(N_n)$, ${\psi }_q(Z_n)$ and ${\psi }_q(D_n)$, $q\in N$, where $N_n=\{1,2,\dots ,n\}$, $(Z_n,{+}_n)$ is the group of integers under addition modulo $n$ and $(D_n,{+}_n)$ is the dihedral group of order $2n$.