Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is a dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\). Furthermore, a set \(S \subseteq V\) is a restrained dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set, while the restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the minimum cardinality of a restrained dominating set of \(G\).
We show that if a connected graph \(G\) of order \(n\) has minimum degree at least \(2\) and is not one of eight exceptional graphs, then \(\gamma_r(G) \leq (n – 1)/2\). We show that if \(G\) is a graph of order \(n\) with \(\delta = \delta(G) \geq 2\), then \(\gamma_r(G) \leq n(1 + (\frac{1}{\delta})^\frac{\delta}{\delta-1} – (\frac{1}{\delta})^\frac{1}{\delta-1})\).

Given a two-dimensional text \(T\) and a set of patterns \(\mathcal{D} = \{P_1, \ldots, P_k\}\) (the dictionary), the two-dimensional \({dictionary\; matching}\) problem is to determine all the occurrences in \(T\) of the patterns \(P_i \in \mathcal{D}\). The two-dimensional \({dictionary\; prefix-matching}\) problem is to determine the longest prefix of any \(P_i \in \mathcal{D}\) that occurs at each position in \(T\). Given an alphabet \(\Sigma\), an \(n \times n\) text \(T\), and a dictionary \(\mathcal{D} = \{P_1, \ldots, P_k\}\), we present an algorithm for solving the two-dimensional dictionary prefix-matching problem. Our algorithm requires \(O(|T| + |\mathcal{D}|(log m + log |\Sigma|))\) units of time, where \(m \times m\) is the size of the largest \(P_i \in \mathcal{D}\). The algorithm presented here runs faster than the Amir and Farach [3] algorithm for the dictionary matching problem by an \(O(log k)\) factor. Furthermore, our algorithm improves the time bound that can be achieved using the Lsuffix tree of Giancarlo [6],[7] by an \(O(k)\) factor.

A connected graph \(G = (V, E)\) is said to be \((a, d)\)-antimagic if there exist positive integers \(a, d\) and a bijection \(g: E \to \{1,2,\ldots,|E|\}\) such that the induced mapping \(f_g: V \to {N}\), defined by \(f_g(v) = \sum\{g(u,v): (u, v) \in E(G)\} \), is injective and \(f_g(V) = \{a,a+d,\ldots,a+(|V|-1)d\}\). We deal with \((a, d)\)-antimagic labelings of the antiprisms.

Let \(s'(G)\) denote the Hall-condition index of a graph \(G\). Hilton and Johnson recently introduced this parameter and proved that \(\Delta(G) \leq s'(G) \leq \Delta(G) + 1\). A graph \(G\) is \(s’\)-Class 1 if \(s'(G) = \Delta(G)\) and is \(s’\)-Class 2 otherwise. A graph \(G\) is \(s’\)-critical if \(G\) is connected, \(s’\)-Class 2, and, for every edge \(e\), \(s'(G – e) < s'(G)\). We use the concept of the fractional chromatic index of a graph to classify \(s’\)-Class 2 in terms of overfull subgraphs, and similarly to classify \(s’\)-critical graphs. We apply these results to show that the following variation of the Overfull Conjecture is true;

A graph \(G\) is \(s’\)-Class 2 if and only if \(G\) contains an overfull subgraph \(H\) with \(\Delta(G) = \Delta(H)\).

We prove that if \(m\) be a positive integer and \(X\) is a totally ordered set, then there exists a function \(\phi: X \to \{1,\ldots,m\}\) such that, for every interval \(I\) in \(X\) and every positive integer \(r \leq |I|\), there exist elements \(x_1 < x_2 < \cdots < x_r\) of \(I\) such that \(\phi(x_{i+1}) \equiv \phi(x_{i}) + 1 \pmod{m}\) for \(i=1,\ldots,r-1\).

We prove that the complete graph \(K_v\) can be decomposed into cuboctahedra if and only if \(v \equiv 1 \text{ or } 33 \pmod{48}\).