In [Discrete Math. 46 (1983) 191 – 198], the concept of inclusive edge connectivity was introduced and discussed. Given a vertex \(v \in V(G)\), the inclusive edge connectivity of \(v\), denoted by \(\lambda_i(v,G)\), is the minimum number of edges whose deletion results in a subgraph of \(G\) in which \(v\) is a cut-vertex. Define

\[\lambda_i(v,G) = \min\{\lambda_i(v,G) : v \in V(G), \text{ and } d_G(v) \geq 2\}\]

to be the inclusive edge connectivity of \(G\). Extremal problems on \(\lambda_i(G)\) are studied in this paper.

If the binding number of a graph \(G\) is more than \(1 + \frac{a-1}{b}\), does \(G\) have an \([a,b)\)-factor? The answers to this question for the case of either \(a = b\) or \(a \leq 3\) can be found in [1], [2], [4], and [7]. Here we give some more answers for \(4 \leq a \leq b\).

The design of de Bruijn sequences is equivalent to finding spanning trees in certain graphs. We give an algorithm which finds spanning
trees in these graphs using the universal circuit matrix defined in \([9]\).

In this note, we obtain nonexistence results for \((m,2,m-1,\frac{m-2}{2})\) relative difference sets. In particular, we obtain further restriction on the parameters of splitting \((m,2,m-1,\frac{m-2}{2})\) relative difference set under certain condition.

We define a new embedding invariant, namely \(n\)-polyhedrality, and we propose a program of research in which the objective is to enumerate the \(n\)-polyhedral embeddings of a given graph for various values of \(n\). We begin the program for the cartesian products of cycles by showing that \(C_3 \times C_n\) has exactly one \(3\)-polyhedral embedding.

A near \(d\)-angulation is a planar graph in which every region has degree \(d\) except for the boundary region. Let \(T\) be a spanning tree with all of its vertices of odd degree on the boundary. Then the interior regions can be 2-colored so that regions that share edges of \(T\) receive different colors and regions which share edges not in \(T\) receive the same color. The boundary region is given a third color. We prove that the number of regions of each color can be determined from only knowing the behavior on the boundary.

It is known that the boundary function \(\alpha\) on union-closed collections containing \(n\) sets has property \(\alpha(n) \leq \alpha(n)\), where \(\alpha(n)\) is Conway’s sequence. Herein a function \(f\) is defined on the positive integers and it is shown that for each value of \(n > 1\) a union-closed collection of \(n\) sets can be constructed with greatest element frequency \(\beta(n)\) and hence \(\alpha(n) \leq \beta(n)\); the inequality \(\beta(n) \leq \alpha(n)\) is proven for \(n \geq 1\) and so \(f\) is a closer approximation than \(\alpha\) to the boundary function \(\alpha\). It is also shown that \(\beta(n) \geq \frac{n}{2}\), thus incidentally providing an alternative proof to that of Mallows, that \(\alpha(n) \geq \frac{n}{2}\) for \(n \geq 1\).

Let \(G\) be a connected graph and \(T\) be a spanning tree of \(G\). (Here, trees and cycles are equated with their edge sets.) Then, the gi-pair \((G,T)\) is a dfs-pair if there exists a digraph \(D\) such that the underlying graph of \(D\) is \(G\), \(T\) is a rooted-ditree in \(D\), and every fundamental cycle of \((G,T)\) is a dicycle of \(D\). Two gi-pairs \((G,T)\) and \((G’,T)\) are cycle-isomorphic if there is a 1-1 mapping between \(Z(G)\) and \(Z(G’)\) so that \((G,T)\) and \((G’,T)\) have the same sets of fundamental cycles. Shinoda, Chen, Yasuda, Kajitani, and Mayeda [6] showed that a 2-connected graph \(G\) is series-parallel if and only if for every spanning tree \(T\) of \(G\), the gi-pair \((G,T)\) is cycle-isomorphic to a dfs-pair. In this paper, an alternate proof of this characterization is given. An efficient algorithm to find such a cycle-isomorphic dfs-pair is also described.

We determine the exact closure of all subsets \(K\) of \(\{3,\ldots,10\}\) which contain \(3\).

Let \(G\) be a simple graph on \(n\) vertices and an even number of edges. It was proved in [15] that the zero-sum (mod 2) Ramsey numbers are given by

\[R(G,\mathbb{Z}_2) =
\begin{cases}
n+2 & \text{if } G = K_{n}, n \equiv 0,1 \pmod{4} \\
n+1 & \text{if } G = K_{p} \cup K_q({\frac{p}{2}}) + (\frac{q}{2}) \equiv 0 \pmod{2} \\
n+1 & \text{if all degrees in } G \text{ are odd} \\
n & \text{otherwise}
\end{cases}
\]

The proof is rather long and based on complicated algebraic machinery. Here we shall prove that \(R(G,\mathbb{Z}_2) \leq n+2\) with equality holding iff \(G = K_{n,}n \equiv 0,1 \pmod{4}\).

The proof uses simple combinatorial arguments and it is also applied to the case, not considered before, when \(G\) has an odd number of edges. Some algorithmic aspects, which cannot be tackled using the methods of [1] and [15], are also considered.