The purpose of this article is to give combinatorial proofs of some binomial identities which were given by Z. Zhang.

Given \(t\geq 2\) cycles \(C_n\) of length \(n \geq 3\), each with a fixed vertex \(v^i_0\), \(i=1,2,\ldots,t\), let \(C^(t)_n\) denote the graph obtained from the union of the \(t\) cycles by identifying the \(t\) fixed vertices (\(v^1_0 = v^2_0 = \cdots = v^t_0\)). Koh et al. conjectured that \(C^(t)^n\) is graceful if and only if \(nt \equiv 0, 3 \pmod{4}\). The conjecture has been shown true for \(t = 3, 6, 4k\). In this paper, the conjecture is shown to be true for \(n = 5\).

Let \(G\) be a finite abelian group of exponent \(m\). By \(s(G)\) we denote the smallest integer \(c\) such that every sequence of \(t\) elements in \(G\) contains a zero-sum subsequence of length \(m\). Among other results, we prove that, let \(p\) be a prime, and let \(H = C_{p^{c_1}} \oplus \ldots C_{p^{c_l}}\) be a \(p\)-group. Suppose that \(1+\sum_{i=1}^{l}(p^{c_i}-1)=p^k\) for some positive integer \(k\). Then,\(4p^k – 3 \leq s(C_{p^k} \oplus H) \leq 4p^k – 2.\)

A connected dominating set \(D\) of a graph \(G\) has the property that not only does \(D\) dominate the graph but the subgraph induced by the vertices of \(D\) is also connected. We generalize this concept by allowing the subgraph induced by \(D\) to contain at most \(k\) components and examine the minimum possible order of such a set. In the case of trees, we provide lower and upper bounds and a characterization for those trees which achieve the former.

Let \(\sigma(K_{r,s}, n)\) denote the smallest even integer such that every \(n\)-term positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) with term sum \(\sigma(\pi) = d_1 + d_2 + \cdots + d_n \geq \sigma(K_{r,s}, n)\) has a realization \(G\) containing \(K_{r,s}\) as a subgraph, where \(K_{r,s}\) is the \(r \times s\) complete bipartite graph. In this paper, we determine \(\sigma(K_{2,3}, n)\) for \(m \geq 5\). In addition, we also determine the values \(\sigma(K_{2,s}, n)\) for \(s \geq 4\) and \(n \geq 2[\frac{(s+3)^2}{4}]+5\).

Formulas for vertex eccentricity and radius for the tensor product \(G \otimes H\) of two arbitrary graphs are derived. The center of \(G \otimes H\) is characterized as the union of three vertex sets of form \(A \times B\). This completes the work of Suh-Ryung Kim, who solved the case where one of the factors is bipartite. Kim’s result becomes a corollary of ours.

Let \(v, k,\lambda\) and \(n\) be positive integers. \((x_1, x_2, \ldots, x_k)\) is defined to be \(\{(x_i, x_j) : i \neq j, i,j =1,2,\ldots,k\},\) in which the ordered pair \((x_i, x_j)\) is called \((j-i)\)-apart for \(i > j\) and \((k+j-i)\)-apart for \(i > j\), and is called a cyclically ordered \(k\)-subset of \(\{x_1, x_2, \ldots, x_k\}\).

A perfect Mendelsohn design, denoted by \((v, k, \lambda)\)-PMD, is a pair \((X, B)\), where \(X\) is a \(v\)-set (of points), and \(B\) is a collection of cyclically ordered \(k\)-subsets of \(X\) (called blocks), such that every ordered pair of points of \(X\) appears \(t\)-apart in exactly \(\lambda\) blocks of \(B\) for any \(t\), where \(1 \leq t \leq k-1\).

If the blocks of a \((v, k, \lambda)\)-PMD for which \(v \equiv 0 \pmod{k}\) can be partitioned into \(\lambda(v-1)\) sets each containing \(v/k\) blocks which are pairwise disjoint, the \((v, k, \lambda)\)-PMD is called resolvable, denoted by \((v, k, \lambda)\)-RPMD.

In the paper [14], we have showed that a \((v, 4, 1)\)-RPMD exists for all \(v \equiv 0 \pmod{4}\) except for \(4, 8\) and with at most \(49\) possible exceptions of which the largest is \(336\).

In this article, we shall show that a \((v, 4, 1)\)-RPMD for all \(v \equiv 0 \pmod{4}\) except for \(4, 8, 12\) and with at most \(27\) possible exceptions of which the largest is \(188\).

The independence number of Cartesian product graphs is considered. An upper bound is presented that covers all previously known upper bounds. A construction is described that produces a maximal independent set of a Cartesian product graph and turns out to be a reasonably good lower bound for the independence number. The construction defines an invariant of Cartesian product graphs that is compared with its independence number. Several exact independence numbers of products of bipartite graphs are also obtained.

Multi-loop digraphs are widely studied mainly because of their symmetric properties and their applications to loop networks. A multi-loop digraph, \(G = G(N; s_1, \ldots, s_\Delta)\) with \(1 \leq s_1 < \cdots < s_\Delta \leq N-1\) and \(\gcd(N, s_1, \ldots, s_\Delta) = 1\), has set of vertices \(V ={Z}_N\) and adjacencies given by \(v \mapsto v + s_i \mod N, i = 1, \ldots, \Delta\). For every fixed \(N\), an usual extremal problem is to find the minimum value \[D_\Delta(N)=\min\limits_{s_1,\ldots,s_\Delta \in Z_N}(N; s_1, \ldots, s_\Delta)\] where \(D(N; s_1, \ldots, s_\Delta)\) is the diameter of \(G\). A closely related problem is to find the maximum number of vertices for a fixed value of the diameter. For \(\Delta = 2\), all optimal families have been found by using a geometrical approach. For \(\Delta = 3\), only some dense families are known. In this work, a new dense family is given for \(\Delta = 3\) using a geometrical approach. This technique was already adopted in several papers for \(\Delta = 2\) (see for instance [5, 7]). This family improves the dense families recently found by several authors.

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1 (1999), 387-400) considered a variation of the classical Turén-type extremal problems as follows: for a given graph \(H\), determine the smallest even integer \(\sigma (H,n)\) such that every \(n\)-term positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) with term sum \(\sigma(\pi) = d_1 + d_2 + \cdots + d_n \geq \sigma(H,n)\) has a realization \(G\) containing \(H\) as a subgraph. In particular, they pointed out that \(3n – 2 \leq \sigma(K_{4} – e, n) \leq 4n – 4\), where \(K_{r+1} – e\) denotes the graph obtained by removing one edge from the complete graph \(K_{r+1}\) on \(r+1\) vertices. Recently, Lai determined the values of \(\sigma(K_4 – e, n)\) for \(n \geq 4\). In this paper, we determine the values of \(\sigma(K_{r+1} – e, n)\) for \(r \geq 3\) and \(r+1 \leq n \leq 2r\), and give a lower bound of \(\sigma(K_{r+1} – e, n)\). In addition, we prove that \(\sigma(K_5 – e, n) = 5n – 6\) for even \(n\) and \(n \geq 10\) and \(\sigma(K_5 – e, n) = 5n – 7\) for odd \(n\) and \(n \geq 9\).