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.

We give a construction for a new family of Group Divisible Designs \((6s + 2, 3, 4; 2, 1)\) using Mutually Orthogonal Latin Squares for all positive integers \(s\). Consequently, we have proved that the necessary conditions are sufficient for the existence of GDD’s of block size four with three groups, \(\lambda_1 = 2\) and \(\lambda_2 = 1\).

For a balanced incomplete block (BIB) design, the following problem is considered: Find \(s\) different incidence matrices of the BIB design such that (i) for \(1 \leq t \leq s-1\), sums of any \(t\) different incidence matrices yield BIB designs and (ii) the sum of all \(s\) different incidence matrices becomes a matrix all of whose elements are one. In this paper, we show general results and present four series of such BIB designs with examples of three other BIB designs.