Narrow Results

One of the well-known NP-hard optimization problems in graph theory is finding the longest path in a graph. This problem remains NP-hard for general grid graphs, and its complexity is open for grid graphs that have a limited number of holes. In this paper, we study this problem for odd-sized $O$-shaped grid graphs, i.e. a rectangular grid graph with a rectangular hole. We show that this problem can be solved in linear time.

We introduce the concept of multi-directional width-bounded geometric separators and obtain an improved separator for grid graphs. This yields an improved exact algorithm for the protein folding problem in the HP-model. For a grid graph G with n grid points P, there exists a separator A ⊆ P such that A has at most points, and G − A has two disconnected subgraphs each with at most nodes. This improves the previous upper bound of . We also derive a lower bound for such a separator in grid graphs.

Finding the best rectilinear path with respect to the bends and teh lengths of paths connecting two given points in the presence of rectilinear obstacles in a two-layer model is studied in this paper. In this model, rectilinear obstacles on each layer are specified separately, and the orientation of routing in each layer is fixed. An algorithm is presented to transform any problem instance in the two-layer model to one in a one-layer model, so that almost all algorithms for finding rectilinear paths among obstacles in the plane can be applied. The transformation algorithm runs in O(e log e) time where e is the number of edges on obstacles lying on both layers. A direct graph-theoretic approach to finding a shortest path in the two-layer model, which is easier to implement is also presented. The algorithm runs in O(e log² e) time.

Let us consider a mapping $\varphi :E(G)\to \{0,1,\dots ,k-1\}$ of a graph $G$, where $k$ is an integer, $2\le k\le |E(G)|$. The mapping $\varphi$ induces for every vertex $v$ of $G$ the label ${\varphi }^{\ast }(v)={\prod }_{uv\in E(G)}\varphi (uv)(modk)$. Let $e_{\varphi }(i)$ ($v_{\varphi }(i)$) denote the number of edges (vertices) in $G$ that are labeled with the number $i$ under the labeling $\varphi$, $0\le i\le k-1$.

The function $\varphi$ is called a $k$-total edge product cordial labeling of $G$ if $|(e_{\varphi }(i)+v_{\varphi }(i))-(e_{\varphi }(j)+v_{\varphi }(j))|\le 1$ for $0\le i<j\le k-1$. A graph $G$ with a $k$-total edge product cordial labeling is called a $k$-total edge product cordial graph.

In this paper, we prove that the grid graph $P_m\square P_n$ for $m,n\ge 2$ admits a $3$-total edge product cordial labeling.

In this paper, we consider dominating sets $D$ and $D^{\prime }$ such that $D$ and $D^{\prime }$ are disjoint and there exists a perfect matching between them. Let $D{D}_{\mathrm{\text{m}}}(G)$ denote the cardinality of smallest such sets $D,D^{\prime }$ in $G$ (provided they exist, otherwise $D{D}_{\mathrm{\text{m}}}(G)=\infty$). This concept was introduced in [W. F. Klostermeyer, M. E. Messinger and A. Angeli Ayello, An eternal domination problem in grids, Theory Appl. Graphs4(1) (2017) 23pp.] in the context of studying a certain graph protection problem. We characterize the trees $T$ for which $D{D}_{\mathrm{\text{m}}}(T)$ equals a certain graph protection parameter and for which $D{D}_{\mathrm{\text{m}}}(T)=\alpha (T)$, where $\alpha (G)$ is the independence number of $G$. We also further study this parameter in graph products, e.g., by giving bounds for grid graphs, and in graphs of small independence number.

The minimum edge version of metric basis is the smallest set $S_E$ of edges in a connected graph $G$ such that for every pair of edges $e_1,e_2$$\in$$E_G,$ there exists an edge $e$$\in$$S_E$ for which $d_E(e_1,e)$$\ne$$d_E(e_2,e)$ holds. In this paper, the families of grid graphs and generalized prism graphs have been studied for edge version of metric dimension. Edge version of metric dimension is found to be constant for both families of graphs.