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.

We show that, for all primes \(p \equiv 1 \pmod{4}\), \(29 \leq p < 10,000\), \(p \neq 97, 193, 257, 449, 641, 769, 1153, 1409, 7681\), there exist \({Z}\)-cyclic triplewhist tournaments on \(p\) elements which are also Mendelsohn designs. We also show that such designs exist on \(v\) elements whenever \(v\) is a product of such primes \(p\).

An algorithm is presented in which a polynomial deck, \(\mathcal{P}D\), consisting of \(m\) polynomials of degree \(m-1\), is analysed to check whether it is the deck of characteristic polynomials of the one-vertex-deleted subgraphs of the line graph, \(H\), of a triangle-free graph, \(G\). We show that if two necessary conditions on \(\mathcal{P}D\), identified by counting the edges and triangles in \(H\), are satisfied, then one can construct potential triangle-free root graphs, \(G\), and by comparing the polynomial decks of the line graph of each with \(\mathcal{P}D\), identify the root graph.

Let \(\sigma_2(G) = \min\{d_G(u)+d_G(v) | u,v \in V(G), u,v \notin E(G)\}\) for a non-complete graph \(G\). An \([a, b]\)-factor of \(G\) is a spanning subgraph \(F\) with minimum degree \(\delta(F) \geq a\) and maximum degree \(\Delta(F) \leq b\).
In this note, we give a partially positive answer to a conjecture of M. Kano. We prove the following results:

Let \(G\) be a 2-edge-connected graph of order \(n\) and let \(k \geq 2\) be an integer. If \(\sigma_2(G) \geq {4n}/{(k +2)}\), then \(G\) has a 2-edge-connected \([2, k]\)-factor if \(k\) is even and a 2-edge-connected \([2, k + 1]\)-factor if \(k\) is odd.
Indeed, if \(k\) is odd, there exists a graph \(G\) which satisfies the same hypotheses and has no 2-edge-connected \([2, k]\)-factor.
Nevertheless, we have shown that if \(G\) is 2-connected with minimum degree \(\delta(G) \geq {2n}/{(k +2)}\), then \(G\) has a 2-edge-connected \([2, k]\)-factor.

The Ramsey numbers \(r(C_4,G)\) are determined for all graphs \(G\) of order six.

In a \(t-(\nu,k,\lambda)\) directed design, the blocks are ordered \(k\)-tuples and every ordered \(t\)-tuple of distinct points occurs in exactly \(\lambda\) blocks (as a subsequence). We show that a simple \(3-(\nu,4,2)\) directed design exists for all \(v\). This completes the proof that the necessary condition \(\lambda v\equiv 0 \pmod 2\) for the existence of a \(3-(\nu,4,\lambda)\) directed design is sufficient.

We give a conjecture for the total chromatic number \(\chi_T\) of all Steiner systems and show its relationship to the celebrated Erdős, Faber, Lovász conjecture. We show that our conjecture holds for projective planes, resolvable Steiner systems and cyclic Steiner systems by determining their total chromatic number.

We propose a number of problems about \(r\)-factorizations of complete graphs. By a completely novel method, we show that \(K_{2n+1}\) has a \(2\)-factorization in which all \(2\)-factors are non-isomorphic. We also consider \(r\)-factorizations of \(K_{rn+1}\) where \(r \geq 3\); we show that \(K_{rn+1}\) has an \(r\)-factorization in which the \(r\)-factors are all \(r\)-connected and the number of isomorphism classes in which the \(r\)-factors lie is either \(2\) or \(3\).