A kernel in a directed graph \(D(V, E)\) is a set \(S\) of vertices of \(D\) such that no two vertices in \(S\) are adjacent and for every vertex \(u\) in \(V \setminus S\) there is a vertex \(v\) in \(S\) such that \((u, v)\) is an arc of \(D\). The problem of existence of a kernel itself is NP-complete for a general digraph. But in this paper, we solve the strong kernel problem of certain oriented networks in polynomial time.

A double shell is defined to be two edge-disjoint shells with a common apex. In this paper, we prove that double shells (where the shell orders are \(m\) and \(2m+1\)) with exactly two pendant edges at the apex are \(k\)-graceful when \(k=2\). We extend this result to double shells of any order \(m\) and \(\ell\) (where \(m \geq 3\) and \(\ell \geq 3\)) with exactly two pendant edges at the apex.

A book consists of a line in the 3-dimensional space, called the spine, and a number of pages, each a half-plane with the spine as boundary. A book embedding \((\pi, p)\) of a graph consists of a linear ordering \(\pi\) of vertices, called the spine ordering, along the spine of a book and an assignment \(p\) of edges to pages so that edges assigned to the same page can be drawn on that page without crossing. That is, we cannot find vertices \(u, v, x, y\) with \(\pi(u) < \pi(x) < \pi(v) 2\) and \(C_n\) are given. If \(G\) is any graph, an upper bound for the page number of the Mycielski of \(G\) is given. When \(G\) and \(H\) are any two graphs with page number \(k\) and \(l\), it is proved that the amalgamation of \(G\) and \(H\) can be embedded in a \max(k, l)\) pages. Further, we remark that the amalgamation of \(G\) with itself requires the same number of pages as \(G\), irrespective of the vertices identified in the two copies of \(G\), to form an amalgamation.

In 2004, Blinco et al [1] introduced \(\gamma\)-labeling. A function \(h\) defined on the vertex set of a graph \(G\) with \(n\) edges is called a \(\gamma\)-labeling if:

1. \(h\) is a \(p\)-labeling of \(G\),
2. \(G\) admits a tripartition \((A, B, C)\) with \(C = \{c\}\) and there exists \(\overline{b} \in B\) such that \((\overline{b}, c)\) is the unique edge with the property that \(h(c) – h(\overline{b}) = n\),
3. for every edge \(\{a, v\} \in E(G)\) with \(a \in A\), \(h(a) < h(v)\).

In [1] they have also proved a significant result on graph decomposition that if a graph \(G\) with \(n\) edges admits a \(\gamma\)-labeling then the complete graph \(K_{2cn+1}\) can be cyclically decomposed into \(2cn + 1\) copies of the graph \(G\), where \(c\) is any positive integer.

Motivated by the result of Blinco et al [1], in this paper, we prove that the well-known almost-bipartite graph, the grid with an additional edge, \((P_m \Box P_n) + \hat{e}\), admits \(\gamma\)-labeling. Further, we discuss a related open problem.

A set \( S \) of vertices of a graph \( G(V,E) \) is a \({dominating \;set}\) if every vertex of \( V \setminus S \) is adjacent to some vertex in \( S \). A dominating set is said to be \({efficient}\) if every vertex of \( V \setminus S \) is dominated by exactly one vertex of \( S \). A paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. A set \( S \) of vertices in \( G \) is a total dominating set of \( G \) if every vertex of \( V \) is adjacent to some vertex in \( S \). In this paper, we construct a minimum paired dominating set and a minimum total dominating set for the infinite diamond lattice. The total domatic number of \( G \) is the size of a maximum cardinality partition of \( V \) into total dominating sets. We also demonstrate that the total domatic number of the infinite diamond lattice is 4.

In the classical book embedding problem, a \( k \)-book is defined to be a line \( L \) in \( 3 \)-space (the spine) together with \( k \) half-planes (the pages) joined together at \( L \). We introduce two variations on the classical book in which edges are allowed to wrap in either one or two directions. The first is a cylindrical book where the spine is a line \( L \) in \( 3 \)-space and the pages are nested cylindrical shells joined together at \( L \). The second is a torus book where the spine is the inner equator of a torus and the pages are nested torus shells joined together at this equator. We give optimal edge bounds for embeddings of finite simple graphs in cylinder and torus books and give best-possible embeddings of \( K_n \) in torus books. We also compare both books with the classical book.

We give necessary and sufficient conditions for the decomposition of the complete graphs with multiple holes, \( K_n \setminus hK_v \), into the graph-pair of order \( 4 \).

A vertex cover of a graph \( G = (V, E) \) is a subset \( S \subseteq V \) such that every edge is incident with at least one vertex in \( S \), and \( \alpha(G) \) is the cardinality of a smallest vertex cover. Let \( \mathcal{T} \) be a collection of vertex covers, not necessarily minimum. We say \( \mathcal{T} \) is closed if for every \( S \in \mathcal{T} \) and every \( e \in E \) there is a one-to-one function \( f : S \to V \) such that (1) \(f(S)\) is a vertex cover,(2) for some \(s \in S\), \(\{s, f(s)\} = e\), (3)for each \(s\) in \(S\), either \(s = f(s)\) or \(s\) is adjacent to \(f(s)\), and (4) \(f(S) \in \mathcal{T}\).A set is an eternal vertex cover if and only if it is a member of some closed family of vertex covers. The cardinality of a smallest eternal vertex cover is denoted \( \alpha_m^\infty(G) \). Eternal total vertex covers are defined similarly, with the restriction that the cover must also be a total dominating set. The cardinality of a smallest eternal total vertex cover is denoted \( \alpha_{mt}^\infty(G) \). These three vertex cover parameters satisfy the relation \(\alpha(G) \leq \alpha_{m}^\infty(G) \leq \alpha_{mt}^\infty(G) \leq 2\alpha(G).\) We define a triple \( (p, q, r) \) of positive integers such that \( p \leq q \leq r \leq 2p \) to be feasible if there is a connected graph \( G \) such that \( \alpha(G) = p \), \( \alpha_{m}^\infty(G) = q \), and \( \alpha_{mt}^\infty(G) = r \). This paper shows all triples with the above restrictions are feasible if \( p \neq q \) or \( r \leq \frac{3p}{2} \) and conjectures that there are no feasible triples of the form \( (p, p, r) \) with \( r > \frac{3p}{2} \). The graphs with triple \( (p, p + 1, 2p) \) are characterized and issues related to the conjecture are discussed.

We study the area distribution of closed walks of length \( n \), starting and ending at the origin. The concept of algebraic area of a walk in the square lattice is slightly modified and the usefulness of this concept is demonstrated through a simple argument. The idea of using a generating function of the form \( (x + x^{-1} + y + y^{-1})^n \) to study these walks is then discussed from a special viewpoint. Based on this, a polynomial time algorithm for calculating the exact distribution of such walks for a given length is concluded. The presented algorithm takes advantage of the Chinese remainder theorem to overcome the problem of arithmetic with large integers. Finally, the results of the implementation are given for \( n = 32, 64, 128 \).

The Wiener polarity index of a graph \( G \) is the number of unordered pairs of vertices \( u, v \) such that the distance between \( u \) and \( v \) is three, which was introduced by Harold Wiener in 1947. A linear time algorithm for computing the Wiener polarity index of trees was described, and also an algorithm which computes the index \( W_p(G) \) for any given connected graph \( G \) on \( n \) vertices in time \( O(M(n)) \) was presented, where \( M(n) \) denotes the time necessary to multiply two \( n \times n \) matrices of small integers (which is currently known to be \( O(n^{2.376}) \)). In this paper, we establish one polynomial algorithm to calculate the value of the Wiener polarity index of a bipartite graph.