We provide graceful labelings for prisms \(C_{2m} \times P_n\), with even cycles, for all \(n \geq 2\), and prisms \(C_{2m+1} \times P_n\), with odd cycles when \(3 \leq mn \leq 12\). Further, we verify that the windmill graph \(K^{(m)}_{4}\) is graceful for \(r \leq 22\), and that the square of a path \(P_n\) is graceful for \(n \leq 32\).

In this paper, a composition result, \(viz\)., the number of \(r\)-compositions of \(n\) dominated by the \(r\)-compositions of \(m\) (\(m \geq n\)) subject to certain restrictions, has been derived by the method of induction.

Let \(G\) be a simple graph with \(n\) vertices. Let \(L(G)\) denote the line graph of \(G\). We show that if \(\kappa'(G) > 2\) and if for every pair of nonadjacent vertices \(v,u \in V(G)\), \(d(v) + d(u) > \frac{2n}{3} – 2\), then for any pair of vertices \(e, e’ \in V(L(G))\), either \(L(G)\) has a Hamilton \((e, e’)\)-path, or \(\{e, e’\}\) is a vertex-cut of \(L(G)\). When \(G\) is a triangle-free graph, this bound can be reduced to \(\frac{n}{3}\). These bounds are all best possible and they partially improve prior results in [J.Graph Theory 10(1986),411-425] and [Discrete Math.76(1989)95-116].

The link length of a walk in a multidimensional grid is the number of straight line segments constituting the walk. Alternatively, it is the number of turns that a mobile unit needs to perform in traversing the walk. A rectilinear walk consists of straight line segments which are parallel to the main axis. We wish to construct rectilinear walks with minimal link length traversing grids. If \(G\) denotes the multidimensional grid, let \(s(G)\) be the minimal link length of a rectilinear walk traversing all the vertices of \(G\). In this paper, we develop an asymptotically optimal algorithm for constructing rectilinear walks traversing all the vertices of complete multidimensional grids and analyze the worst-case behavior of \(s(G)\), when \(G\) is a multidimensional grid.

We proved that if a graph \(G\) of minimum valency \(\delta=6\alpha + 5\), with \(\alpha\) a non-negative integer, can triangulate a surface \(\Sigma\) with \(\chi(\Sigma) = -\alpha n + \beta\), where \(\beta \in \{0, 1, 2\}\), then \(G\) is edge reconstructible.

We introduce a concept of “pseudo dual” pseudographs which can be thought of as generalizing some of the recent work on iterated clique graphs. In particular, we characterize those pseudographs which have pseudo duals and show that they encompass several natural families of intersection pseudographs.

Let \(G\) be a simple graph, \(a\) and \(b\) integers and \(f: E(G) \to \{a,a+1,\ldots,b\}\) an integer-valued function with \(\sum_{e\in E(G)} f(e) \equiv 0 \pmod{2}\). We prove the following results:(1) If \(b \geq a \geq 2\), \(G\) is connected and \(\delta(G) \geq \max\left[\frac{b}{2}+2, \frac{(a+b+2)^2}{8a}\right]\), then the line graph \(L(G)\) of \(G\) has an \(f\)-factor;(2) If \(b\geq a \geq 2\), \(G\) is connected and \(\delta(L(G)) \geq \frac{(a+2b+2)^2}{8a}\), then \(L(G)\) has an \(f\)-factor.

We show that a cubic graph is \(\frac{3}{2}\)-tough if and only if it is equal to \(K_4\) or \(K_3 \times K_3\) or else is the inflation of a 3-connected cubic graph.

A directed triple system of order \(v\), denoted \(DT S(v)\), is said to be \(k\)-near-rotational if it admits an automorphism consisting of \(3\) fixed points and \(k\) cycles of length \(\frac{v-3}{3}\). In this paper, we give necessary and sufficient conditions for the existence of \(k\)-near-rotational \(DT S(v)\)s.