New sufficient conditions for equality of edge-connectivity and minimum degree of graphs are presented, including those of Chartrand, Lesniak, Plesnik, Plesník, and Ždmán, and Volkmann.

We show that \((81, 16, 3)\)-block designs have no involutionary automorphisms that fix just \(13\) points. Since the nonexistence of \((81, 16, 3)\)-designs with involutionary automorphism fixing \(17\) points has already been proved, it follows that any involution that an \((81, 16, 3)\)-design may have must fix just \(9\) points.

In this paper we construct a latin \((n \times n \times (n-d))\)-parallelepiped that cannot be extended to a latin cube of order \(n\) for any pair of integers \(d, n\) where \(d \geq 3\) and \(n \geq 2d+1\). For \(d = 2\), it is similar to the construction already known.

In this note the numbers of common triples in two simple balanced ternary designs with block size \(3\), index \(3\) and \(p_2 = 3\) are determined.

The class of parity graphs, those in which the cardinality of every maximal independent subset of vertices has the same parity, contains the well-covered graphs and arose in connection with the PSPACE-complete game “Generalized Kayles”. In 1983 [5] we characterized parity graphs of girth 8 or more. This is extended to a characterization of the parity graphs of girth greater than 5. We deduce that these graphs can be recognized in polynomial time.

In this paper we bring out more strongly the connection between the disconnection number of a graph and its cycle rank. We also show how to associate with a pizza sliced right across in a certain way with \(n-2\) cuts a graph with \(n\) vertices, and show that if the pizza is cut thereby into \(r\) pieces, then any set of \(r-1\) of these pieces corresponds to a basis for the cycle space of the associated graph. Finally we use this to explain why for \(n\geq 3\) the greatest number of regions that can be formed by slicing a pizza in the certain way with \(n-2\) cuts, namely \(\frac{1}{2}(n^2-3n+4)\), equals the disconnection number of \(K_n\).

For a graph \(G\), let \(\sigma_k = \min \{\sum_{i=1}^{k} d(v_i) \mid \{v_1, \ldots, v_k\}\) { is an independent set
of vertices in } G\}. Jung proved that every \(1\)-tough graph \(G\) with \(|V(G)| = n \geq 11\) and \(\sigma_2 > n-4\) is hamiltonian. This result is generalized as follows: if \(G\) is a \(1\)-tough graph with \(|V(G)| = n \geq 3\) such that \(\sigma_3 > n\) and for all \(x, y \in V(G)\), \(d(x,y) = 2\) implies \(\max\{d(x), d(y)\} \geq \frac{1}{2}(n-4)\), then \(G\) is hamiltonian. It is also shown that the condition \(\sigma_3 \geq n\), in the latter result, can be dropped if \(G\) is required to be \(3\)-connected and to have at least \(35\) vertices.

Recently, M. Lewin proved a property of the sum of squares of row sums and column sums of an \(n \times n\) \((0, 1)\)-matrix, which has more \(1\)’s than \(0\)’s in the entries. In this article we generalize Lewin’s Theorem in several aspects. Our results are: (1)For \(m \times n\) matrices, where \(m\) and \(n\) can be different,(2) For nonnegative integral matrices as well as \((0, 1)\)-matrices,(3) For the sum of any positive powers of row sums and column sums,(4) and For any distributions of values in the matrix.In addition,we also characterize the boundary cases.

We consider the realizations of a sequence \((p^*_3, p^*_5, p^*_6, \ldots)\) of nonnegative integers satisfying the equation \(\sum_{k\geq 3} (k-4)p_k + 8 = 0\) as an arrangement of simple curves defined by \(B\). Grünbaum [4]. In this paper, we show that an Eberhard-type theorem for a digon-free arrangement of simple curves is not valid in general, while some sequences are realizable as a digon-free arrangement of simple curves.

A \((12,6,3)\) cover is a family of 6-element subsets, called blocks, chosen from a 12-element universe, such that each 3-element subset is contained in at least one block. This paper constructs a \((12,6,3)\) cover with 15 blocks, and it shows that any \((12,6,3)\) cover has at least 15 blocks; thus the covering number \(C(12,6,3) = 15\). It also shows that the 68 nonisomorphic \((12,6,3)\) covers with 15 blocks fall into just two classes using a very natural classification scheme.

An algorithm is given to generate all \(k\)-subsets of \(\{1, \ldots, n\}\) as increasing sequences, in an order so that going from one sequence to the next, exactly one entry is changed by at most \(2\).

Given a graph \(G\) with weighting \(w : E(G) \to \mathbb{Z}^+\), the strength of \(G(w)\) is the maximum weight on any edge. The weight of a vertex in \(G(w)\) is the sum of the weights of all its incident edges. The network \(G(w)\) is irregular if the vertex weights are distinct. The irregularity strength of \(G\) is the minimum strength of the graph under all irregular weightings. We determine the irregularity strength of the \(m \times n\) grid for all \(m, n \geq 18\).

The blocks of a balanced ternary design, \(\mathrm{BTD}(V, B; p_1, p_2, R; K, \Lambda)\), can be partitioned into two sets: the \(b_1\) blocks that each contain no repeated elements, and the \(b_2 = B – b_1\) blocks containing repeated elements. In this note, we address, and answer in some particular cases, the following question. For which partitions of the integer \(B\) as \(b_1 + b_2\) does there exist a \(\mathrm{BTD}(V, B; p_1, p_2, R; K, \Lambda)\)?

A general formula is obtained for the number of points lying on a plane algebraic curve over the finite local ring \(\mathrm{GF}(q)[t]/(t^n)\) (\(n > 1\)) whose equation has coefficients in \(\mathrm{GF}(q)\) and under the restriction that it has only simple and ordinary singular points.

Through combinatorial analysis we study the jump number, greediness and optimality of the products of chains, the product of an (upward rooted) tree and a chain. It is well known [1] that the dimension of products of \(n\) chains is \(n\). We construct a minimum realizer \(L_1, \ldots, L_n\) for the products of \(n\) chains such that \(s(\bigcap_{i=1}^{j}L_i) \leq s(\bigcap_{i=1}^{j+1}L_i)\) where \(j = 1, \ldots, n-1\).

In this paper, new optimal \((pm,m)\) and \((pm,m-1)\) ternary linear codes of dimension 6 are presented. These codes belong to the class of quasi-twisted codes, and have been constructed using a greedy local search algorithm. Other codes are also given which provide a lower bound on the maximum possible minimum distance. The minimum distances of known quasi-twisted codes of dimension 6 are given.

We propose the following conjecture: Let \(m \geq k \geq 2\) be integers such that \(k \mid m\), and let \(T_m\) be a tree on \(m\) edges. Let \(G\) be a graph with \(\delta(G) \geq m+k-1\). Then for every \(Z_k\)-colouring of the edges of \(G\) there is a zero-sum (mod \(k\)) copy of \(T_m\) in \(G\). We prove the conjecture for \(m \geq k = 2\), and explore several relations to the zero-sum Turán numbers.

For any double sequence \((q_{k,n})\) with \(q_{k,0} = 0\), the “summatorial sequence” \((P_{k,n}) = \sum(q_{k,n})\) is defined by \(p_{0,0} = 1\) and \(P_{k,} = \sum_{j=0}^k \sum_{m=1}^n q_{ j,m}P_{k-j,n-m}\) If \(q_{k,n} = 0\) for \(k < n-1\) then there exists a unique sequence \((c_j)\) satisfying the recurrence \(P_{k,n} = \sum_{j=0}^k c_j P_{k-j,k-j,n-m}\) for \(k < n\). We apply this combinatorial recursion to certain counting functions on finite posets. For example, given a set \(A\) of positive integers, let \(P_{k,n}\) denote the number of unlabeled posets with \(n\) points and exactly \(k\) antichains whose cardinality belongs to \(A\), and let \(q_{k,n}\) denote the corresponding number of ordinally indecomposable posets. Then \((P_{k,n})\) is the summatorial sequence of \((q_{k,n})\). If \(2 \in A\) then \((P_{k,n})\) enjoys the above recurrence for \(k < 1\). In particular, for fixed \(k\), there is a polynomial \(p_k\) of degree \(k\) such that \(P_{n,k} = p_k(n)\) for all \(n \geq k\), and \(p_{k,n}\) is asymptotically equal to \(\binom{n-1}{k}\). For some special classes \(A\) and small \(k\), we determine the numbers \(c_k\) and the polynomials \(p_k\) explicitly. Moreover, we show that, at least for small \(k\), the remainder sequences \(p_{k,n} – p_k(n)\) satisfy certain Fibonacci recursions, proving a conjecture of Culberson and Rawlins. Similar results are obtained for labeled posets and for naturally ordered sets.

The paper \([2]\) claimed that a disconnected graph with at least two nonisomorphic components is determined by some three of its vertex deleted subgraphs. While this statement is true, the proof in \([2]\) is incorrect. We give a correct proof of this fact.

It is shown that the necessary conditions for the existence of a \(k\)-cycle system of order \(n\) are sufficient for \(k \in \{20, 24, 28, 30, 33, 35, 36, 39, 40, 42, 44, 45, 48\}\), thus settling the problem for all \(k \leq 50\).

In this paper we study competition graphs of digraphs of restricted degree.
We introduce the notion of restricted competition numbers of graphs.
We complete the characterization of competition graphs of indegree at most 2 and their restricted competition numbers.
We characterize interval \((2,3)\)-graphs and give a recognition algorithm for interval \((2,3)\)-digraphs.
We characterize competition graphs and interval competition graphs of digraphs of outdegree at most \(2\).
The relationship between restricted competition numbers and ordinary competition numbers are studied for several classes of graphs.