MacGillivray and Seyffarth (J. Graph Theory \(22 (1996),213-229)\) proved that planar graphs of diameter three have domination number at most ten. Recently it was shown (J. Graph Theory \(40 (2002), 1-25)\) that a planar graph of diameter three and of radius two has domination number at most six while every sufficiently large planer graph of diameter three has domination number at most seven. In this paper we improve on these results. We prove that every planar graph of diameter three and of radius two has total domination number (and therefore domination number) at most five. We show then that every sufficiently large planar graph of diameter three has domination number at most six and this result is sharp, while a planar graph of diameter three has domination number at most nine.

A hypergraph is a generalization of an ordinary graph, in which an edge is not limited to contain exactly two vertices, instead, it can contain an arbitrary number of vertices. A number of desirable properties of database schemes have been shown to be equivalent to hypergraphs. In addition, hypergraph models are very important for cellular mobile communication systems. By applying Pólya’s Enumeration Theorem (PET) twice, the counting series is derived for unlabeled linear acyclic hypergraphs in this paper.

In a given graph \(G\), a set \(S\) of vertices with an assignment of colors is a defining set of the vertex coloring of \(G\), if there exists a unique extension of the colors of \(S\) to a \(\chi(G)\)-coloring of the vertices of \(G\). A defining set with minimum cardinality is called a smallest defining set (of vertex coloring) and its cardinality, the defining number, is denoted by \(d(G, \chi)\). Let \(d(n,r, \chi = k)\) be the smallest defining number of all \(r\)-regular \(k\)-chromatic graphs with \(n\) vertices. Mahmoodian and Mendelsohn (1999) proved that for each \(n\geq m\) and each \(r \geq 4\), \(d(n,r, \chi = 3) = 2\). They raised the following question: Is it true that for every \(k\), there exist \(n_0(k)\) and \(r_0(k)\), such that for all \(n \geq n_0(k)\) and \(r \geq r_0(k)\) we have \(d(n,r, \chi = k) = k-1\)? We show that the answer to this question is positive, and we prove that for a given \(k\) and for all \(n \geq 3k\), if \(r \geq 2(k – 1)\) then \(d(n,r, \chi = k) = k-1\).

In this paper subsets of a three-dimensional locally projective planar space which meet every plane either in \(2\) or in \(h, h > 2\), points are studied and classified.

Let \(G_1, G_2\) be simple graphs with \(n_1, n_2\) vertices and \(m_1, m_2\) edges respectively. The Corona graph \(G_1 \circ G_2\) of \(G_1\) with \(G_2\) is obtained by taking one copy of \(G_1\), \(v_1\) copies of \(G_2\) and then joining each vertex of \(G_1\) to all the vertices of a copy of \(G_2\).

For a graph \(G\), by the index of cordiality \(i(G)\) we mean \(\min{|e_f(0)-e_f(1)|}\), where the minimum is taken over all the binary labelings of \(G\) with \(|v_f(0)-v_f(1)|\leq 1\). In this paper, we investigate the cordiality of \(G_1 \circ \overline{K_t}, K_n \circ \overline{K_t}\) and \(G \circ C_t\), where \(G\) is a graph with the index of cordiality \(k\).

In this paper, we give a necessary condition for an odd degree graph to be Skolem-graceful and we prove that if \(G\) is a \((p, q)\) pseudograceful graph such that \(p=q+tl\), then \(G\cup S_m\) is Skolem-graceful for all \(m\geq 1\). Finally, we give some variations on the definition of cordial graphs.

The posets of dimension \(2\) are those posets whose minimal realizations have two elements, that is, which may be obtained as the intersection of two of their linear extensions. Gallai’s decomposition of a poset allows for a simple formula to count the number of the distinct minimal realizations of the posets of dimension \(2\). As an easy consequence, the characterization of M. El-Zahar and of N.W. Sauer of the posets of dimension \(2\), with an unique minimal realization, is obtained.

In this paper we give a new method for constructing modular \(n\)-queens solutions which, in particular, yields nonlinear solutions for all composite \(n\) such that \(\gcd(n,6) = 1\) and all prime \(n \geq 19\).

Path problems in graphs can generally be formulated and solved by using an algebraic structure whose instances are called path algebras. Each type of path problem is characterized by a different instance of the structure. This paper proposes a method for combining already known path algebras into new ones. The obtained composite algebras can be applied to solve relatively complex path problems, such as explicit identification of optimal paths or multi-criteria optimization. The paper presents proofs showing that the proposed construction is correct. Also, prospective applications of composite algebras are illustrated by examples. Finally, the paper explores possibilities of making the construction more general.

Automorphisms of Steiner \(2\)-designs \(S(2,4,37)\) are studied and used to find many new examples. Some of the constructed designs have \(S(2,3,9)\) subdesigns, closing the last gap in the embedding spectrum of \(S(2,3,9)\) designs into \(S(2,4,v)\) designs.