For two integers \(k > 0\) and \(s (\geq 0\)), a cycle of length \(s\) is called an \((s \mod k)\)-cycle if \(l \equiv s \mod k\). In this paper, the following conjecture of Chen, Dean, and Shreve [5] is proved:Every \(2\)-connected graph with at least six vertices and minimum degree at least three contains a (\(2 \mod 4\))-cycle.

In this paper we present graceful and nearly graceful labelings of some graphs. In particular, we show, graceful labelings of the \(kC_4-snake\) (for the general case),\(kC_6\) and \(kC_{12}-snakes\) (for the even case),and also establish some conditions to obtain graceful labelings of \(kC_{4n}-snakes\) with some related results. Moreover, for the linear \(kC_6\)-snake, we show:a graceful labeling when \(k\) is even,a nearly graceful labeling when \(k\) is odd.We also explore the connection of these labelings with more restrictive variations of graceful ones.

By considering the order of the largest induced bipartite subgraph of \(G\), Hagauer and Klaviar [4] were able to improve the bounds first published by V. G. Vizing [6] for the independence number of the Cartesian product \(G \Box H\) for any graph \(H\). In this paper, we study maximum independent sets in \(G \Box H\) when \(G\) is a caterpillar, and derive bounds for the independence number when \(H\) is bipartite. The upper bound we produce is less than or equal to that in [4] when \(H\) is also a caterpillar, and is shown to be strictly smaller when \(H\) comes from a restricted class of caterpillars.

Let \(T\) be a spanning tree of a graph \(G\). This paper is concerned with the following operation: we remove an edge \(e \in E(T)\) from \(T\), and then add an edge \(f \in E(G) – E(T)\) so that \(T – e + f\) is a spanning tree of \(G\). We refer to this operation of obtaining \(T – e + f\) from \(T\) as the transfer of \(e\) to \(f\). We prove that if \(G\) is a \(2\)-connected graph with \(|V(G)| \geq 5\), and if \(T_1\) and \(T_2\) are spanning trees of \(G\) which are not stars, then \(T_1\) can be transformed into \(T_2\) by repeated applications of a transfer of a nonpendant edge (an edge \(xy\) of a tree \(T\) is called a nonpendant edge of \(T\) if both of \(x\) and \(y\) have degree at least \(2\) in \(T\)).

We provide upper estimates on the weak exponent of indecomposability of an irreducible Boolean matrix.

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min\left\{\frac{|S|}{\omega(G-S)} \mid S \subseteq V(G), \omega(G-S) \geq 2\right\},\]

where \(\omega(G-S)\) is the number of components of \(G-S\). We also define \(t(K_n) = +\infty\) for every \(n\).

The middle graph \(M(G)\) of a graph \(G\) is the graph obtained from \(G\) by inserting a new vertex into every edge of \(G\) and by joining by edges those pairs of these new vertices which lie on adjacent edges of \(G\).

In this article, we give the toughness of the middle graph of a graph, and using this result we also give a sufficient condition for the middle graph to have a \(k\)-factor.

This paper gives constructions of balanced incomplete block designs and group divisible designs with \(k = 7, 8,\) or \(9\), and \(\lambda = 1\). The first objective is to give constructions for all possible cases with the exception of \(40, 78,\) and \(157\) values of \(v\). Many of these initial exceptions have now been removed by Abel. In an update section, more are removed; group divisible designs with groups of size \(k(k-1)\) are constructed for \(k = 7\) and \(8\) with \(124\) and \(87\) exceptions; it is also established that \(v \geq 294469\) and \(v \equiv 7\) mod \(42\) suffices for the existence of a resolvable balanced incomplete block design with \(k = 7\). Group divisible designs with group size \(k\) and resolvable designs are constructed.