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 \emph{dictionary matching} problem is to determine all the occurrences in \(T\) of the patterns \(P_i \in \mathcal{D}\). The two-dimensional \emph{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}\).

In this paper, we present algorithms for locating the vertices in a tree of \(n\) vertices of positive edge-weighted tree and a positive vertex-weighted tree from which we broadcast multiple messages in a minimum cost. Their complexity is \(O(n^2 \log n)\). It improves a direct recursive approach which gives \(O(n^3)\). In the case where all the weights are equal to one, the complexity is \(O(n)\).

The affine resolvable 2-(27,9,4) designs were classified by Lam and Tonchev [9, 10]. We use their construction of the designs to examine the ternary codes of the designs and show, using Magma [3], that each of the codes, apart from two, contains, amongst its constant weight-9 codewords, a copy of the ternary code of the affine geometry design of points and planes in \(AG_3(F_3)\). We also show how the ternary codes of the 68 designs and of their dual designs, together with properties of the automorphism groups of the designs, can be used to characterize the designs.

A perfect hash function for a subset \(X\) of \(\{0,1,\ldots,n-1\}\) is an injection \(h\) from \(X\) into the set \(\{0,1,\ldots,m-1\}\).
Perfect hash functions are useful for the compact storage and fast retrieval of frequently used objects. In this paper, we discuss some new practical algorithms for efficient construction of perfect hash functions, and we analyze their complexity and program size.

A Kuratowski-type approach for \([2,3]\)-graphs, i.e., hypergraphs whose edges have cardinality not more than \(3\), is presented, leading to a well-quasi-order in such a context, with a complete obstruction set of six forbidden hypergraphs to plane embedding.