We provide graceful and harmonious labelings for all vertex deleted and edge-deleted prisms. We also show that with the sole exception of the cube all prisms are harmonious.

Let \(G\) be a 2-connected simple graph of order \(n\) (\(\geq 3\)) with connectivity \(k\). One of our results is that if there exists an integer \(t\) such that for any distinct vertices \(u\) and \(v\), \(d(u,v) = 2\) implies \(|N(u) \bigcup N(v)| \geq n-t\), and for any independent set \(S\) of cardinality \(k+1\), \(\max\{d(u) \mid u \in S\} \geq t\), then \(G\) is hamiltonian. This unifies many known results for hamiltonian graphs. We also obtain a similar result for hamiltonian-connected graphs.

A graph \(G = (V(G), E(G))\) is the competition graph of an acyclic digraph \(D = (V(D), A(D))\) if \(V(G) = V(D)\) and there is an edge in \(G\) between vertices \(x, y \in V(G)\) if and only if there is some \(v \in V(D)\) such that \(xv, yv \in A(D)\). The competition number \(k(G)\) of a graph \(G\) is the minimum number of isolated vertices needed to add to \(G\) to obtain a competition graph of an acyclic digraph. Opsut conjectured in 1982 that if \(\theta(N(v)) \leq 2\) for all \(v \in V(G)\), then the competition number \(k(G)\) of \(G\) is at most \(2\), with equality if and only if \(\theta(N(v)) = 2\) for all \(v \in V(G)\). (Here, \(\theta(H)\) is the smallest number of cliques covering the vertices of \(H\).) Though Opsut (1982) proved that the conjecture is true for line graphs and recently Kim and Roberts (1989) proved a variant of it, the original conjecture is still open. In this paper, we introduce a class of so-called critical graphs. We reduce the question of settling Opsut’s conjecture to the study of critical graphs by proving that Opsut’s conjecture is true for all graphs which are disjoint unions of connected non-critical graphs. All \(K_4\)-free critical graphs are characterized. It is proved that Opsut’s conjecture is true for critical graphs which are \(K_4\)-free or are \(K_4\)-free after contracting vertices of the same closed neighborhood. Some structural properties of critical graphs are discussed.

We investigate the existence of \(a\)-valuations and sequential labelings for a variety of grids in the plane, on a cylinder and on a torus.

Let \(G\) be a simple graph of order \(n\) with independence number \(\alpha\). We prove in this paper that if, for any pair of nonadjacent vertices \(u\) and \(v\), \(d(u)+d(v) \geq n+1\) or \(|N(u) \cap N(v)| \geq \alpha\), then \(G\) is \((4, n-1)\)-connected unless \(G\) is some special graphs. As a corollary, we investigate edge-pancyclicity of graphs.

In this paper, we study the powers of two important classes of graphs — strongly chordal graphs and circular arc graphs. We show that for any positive integer \(k \geq 2\), \(G^{k-1}\) is a strongly chordal graph implies \(G^k\) is a strongly chordal graph. In case of circular arc graphs, we show that every integral power of a circular arc graph is a circular arc graph.

A partial plane of order \(n\) is a family \(\mathcal{L}\) of \(n+1\)-element subsets of an \(n^2+n+1\)-element set, such that no two sets meet more than \(1\) element. Here it is proved, that if \(\mathcal{L}\) is maximal, then \(|\mathcal{L}| \geq \lfloor\frac{3n}{2}\rfloor + 2\), and this inequality is sharp.

The binding number of a graph \(G \) is defined to be the minimum of \(|N(S)|/|S| \) taken over all nonempty \(S \subseteq V(G) \) such that \(N(S) \neq V(G) \). In this paper, two general results for the binding numbers of product graphs are obtained. (1) For any \(G \) on \(m \) vertices, it is shown that \( bind (G \times K_n) = \frac{nm-1}{nm-\delta(G)-n+1} \) for all \(n \) sufficiently large.(2) For arbitrary \(G \) and for \(H \) with \( bind(H) \geq 1 \), a (relatively) simple expression is derived for \( bind (G[H]) \).

We give explicit expressions for the sixth and seventh chromatic coefficients of a bipartite graph. As a consequence, we obtain a necessary condition for two bipartite graphs to be chromatically equivalent.