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.

Rado numbers are closely related to Ramsey numbers, but pertaining to equations and integers instead of cliques within graphs. For every integer \( m \geq 3 \) and every integer \( c \), let the 2-color Rado number \( r(m,c) \) be the least integer, if it exists, such that for every 2-coloring of the set \( \{1,2,\ldots,r(m,c)\} \) there exists a monochromatic solution to the equation \(\sum_{i=1}^{m-1} x_i + c = x_m\) .The values of \( r(m,c) \) have been determined previously for nonnegative values of \( c \), as well as all values of \( m \) and \( c \) such that \( -m+2 < c < 0 \) and \( c < -(m-1)(m-2) \). In this paper, we find \( r(m,c) \) for the remaining values of \( m \) and \( c \).

This paper deals with the Orchard crossing number of some families of graphs which are based on cycles. These include disjoint cycles, cycles which share a vertex and cycles which share an edge. Specifically, we focus on the prism and ladder graphs.

Let \(i(G)\) be the number of isolated vertices in graph \(G\). The isolated toughness of \(G\) is defined as \(I(G) = +\infty\) if \(G\) is complete; \(I(G) = \text{min}\{|S|/i(G-S) : S \subseteq V(G), i(G-S) \geq 2\}\) otherwise. In this paper, we determine that \(G\) is a fractional \((g, f, n)\)-critical graph if \(I(G) \geq \frac{b^2 + bn – 1}{a}\) if \(b > a\); \(I(G) \geq b + n\) if \(a = b\).