A graph \(G\) is homogeneously traceable if for each vertex \(v\) of \(G\) there exists a hamiltonian path in \(G\) with initial vertex \(v\). A graph is called claw-free if it has no induced \(K_3\) as a subgraph.

In this paper, we prove that if \(G\) is a \(k\)-connected (\(k > 1\)) claw-free graph of order \(n\) such that the sum of degrees of any \(k+2\) independent vertices is at least \(n-k\), then \(G\) is homogeneously traceable. For \(k=2\), the bound \(n-k\) is best possible.

As a corollary we obtain that if \(G\) is a \(2\)-connected claw-free graph of order \(n\) such that \(NC(G) \geq (n-3)/2\), where \(NC(G) = \min\{|N(u) \cup N(v)|: uv \notin E(G)\}\), then \(G\) is homogeneously traceable. Moreover, the bound \((n-3)/2\) is best possible.

In this note, we consider the problem of constructing magic rectangles of size \(m\) by \(n\), where \(m\) and \(n\) are both multiples of two. What seems to be a new and relatively simple method for constructing many such rectangles is presented.

In [Discrete Math.75(1989)69-99], Bondy conjectured that if \(G\) is a 2-edge-connected simple graph with \(n\) vertices, then \(G\) admits a double cycle cover with at most \(n – 1\) cycles. In this note, we prove this conjecture for graphs without subdivision of \(K_4\) and characterize all the extremal graphs.

In this paper, partial answers to some open problems on harmonious labelings of graphs listed in \([2]\) are given.

It has been shown that there exists a resolvable spouse-avoiding mixed-doubles round robin tournament for any positive integer \(v \neq 2, 3, 6\) with \(27\) possible exceptions. We show that such designs exist for \(19\) of these values and the only values for which the existence is undecided are: \(10, 14, 46, 54, 58, 62, 66\), and \(70\).

Partitions of all quadruples of an \(n\)-set into pairwise disjoint packings with no common triples, have applications in the design of constant weight codes with minimum Hamming distance 4. Let \(\theta(n)\) denote the minimal number of pairwise disjoint packings, for which the union is the set of all quadruples of the \(n\)-set. It is well known that \(\theta(n) \geq n-3 \text{ if } n \equiv 2 \text{ or } 4 \text{ (mod } 6),\) \(\theta(n) \geq n-2 \text{ if } n \equiv 0, 1, \text{ or } 3 \text{ (mod } 6),\) and \(\theta(n) \geq n-1 \text{ for } n \equiv 5 \text{ (mod } 6).\) \(\theta(n) = n-3\) implies the existence of a large set of Steiner quadruple systems of order \(n\). We prove that \(\theta(2^k) \leq 2^k-2, \quad k \geq 3,\) and if \(\theta(2n) \leq 2n-2, \quad n \equiv 2 \text{ or } 4 \text{ (mod } 6),\) then \(\theta(4n) \leq 4n-2.\) Let \(D(n)\) denote the maximum number of pairwise disjoint Steiner quadruple systems of order \(n\). We prove that \(D(4n) \geq 2n + \min\{D(2n), n-2\}, \quad n \equiv 1 \text{ or } 5 \text{ (mod } 6), \quad n > 7,\) and \(D(28) \geq 18.\)

A group \((G, \cdot)\) with the property that, for a particular integer \(r > 0\), every \(r\)-set \(S\) of \(G\) possesses an ordering, \(s_1, s_2, \ldots, s_r\), such that the partial products \(s_1, s_1s_2, \ldots, s_1 s_2 \cdots s_r\) are all different, is called an \(r\)-set-sequenceable group. We solve the question as to which abelian groups are \(r\)-set-sequenceable for all \(r\), except that, for \(r = n – 1\), the question is reduced to that of determining which groups are \(R\)-sequenceable.

Let \(p(x > y)\) be the probability that a random linear extension of a finite poset has \(x\) above \(y\). Such a poset has a LEM (linear extension majority) cycle if there are distinct points \(x_1, x_2, \ldots, x_m\) in the poset such that \(p(x_1 > x_2) > \frac{1}{2}, p(x_2 > x_3) > \frac{1}{2}, \ldots, p(x_m > x_1) > \frac{1}{2}.\) We settle an open question by showing that interval orders can have LEM cycles.

We define the basis number, \(b(G)\), of a graph \(G\) to be the least integer \(k\) such that \(G\) has a \(k\)-fold basis for its cycle space. We investigate the basis number of the lexicographic product of paths, cycles, and wheels. It is proved that

\[b(P_n \otimes P_m) = b(P_n \otimes C_m) = 4 \quad \forall n,m \geq 7,\]
\[b(C_n \otimes P_m) = b(C_n \otimes C_m) = 4 \quad \forall n,m \geq 6,\]
\[b(P_n \otimes W_m) = 4 \quad \forall n,m \geq 9,\]
and
\[b(C_n \otimes W_n) = 4 \quad \forall n,m \geq 8.\]

It is also shown that \(\max \{4, b(G) + 2\}\) is an upper bound for \(b(P_n \otimes G)\) and \(b(C_n \otimes G)\) for every semi-hamiltonian graph \(G\).

Hare and Hare conjectured the 2-packing number of an \(m \times n\) grid graph to be \(\left\lceil \frac{mn}{5} \right\rceil\) for \(m, n \geq 9\). This is verified by finding the 2-packing number for grid graphs of all sizes.