In this paper, we prove that if \(G\) is a 3-connected planar graph and contains no vertex of degree \(4\), then \(G\) is edge reconstructible. This generalizes a result of J. Lauri [J1].

In this paper, we present a new generalization of the self-complementary graphs, called the \(t\)-sc graphs. Various properties of this class of graphs are studied, generalizing earlier results on self-complementary graphs. Certain existential results on \(t\)-sc graphs are presented, followed by the construction of some infinite classes of \(t\)-sc graphs. Finally, the notion of \(t\)-sc graphs is linked with the notion of factorization, leading to a generalization of \(r\)-partite self-complementary graphs.

In [1], we introduced the generalized exponent for primitive matrices. In this paper, the generalized exponents of tournament matrices are derived.

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.