Let \(G\) be a graph with \(r \geq 0\) special vertices, \(b_1, \ldots, b_r\), called pins. \(G\) can be composed with another graph \(H\) by identifying each \(b_i\) with another vertex \(a_i\) of \(H\). The resulting graph is denoted \(H \circ G\). Let \(\Pi\) denote a decision problem on graphs. We consider the problem of constructing a “small” minor \(G^*\) of \(G\) that is “equivalent” to \(G\) with respect to the problem \(\Pi\). Specifically, \(G^*\) should satisfy the following:

(C1) \(G^b\) has the same pins as \(G\).

(C2) \(\Pi(H \circ G^b) = \Pi(H \circ G)\) for every \(H\) for which \(H \circ G\) is defined.

(C3) \(|V(G^b)| + |E(G^b)| \leq c \cdot p\), where \(p\) is the number of pins of \(G\), \\and \(c\) is a constant depending only on \(\Pi\).

(C4) \(G^b\) is a minor of \(G\).

We provide linear-time algorithms for constructing such graphs when \(\Pi\) stands for either series-parallelness or outer-planarity. These algorithms lead to linear-time algorithms that determine whether a hierarchical graph is series-parallel or outer-planar and to linear-space algorithms for generating a forbidden subgraph of a hierarchical graph, when one exists.

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.