For any integers \(r\) and \(n\), \(2 < r < n-1\), it is proved that there exists an order \(n\) regular graph of degree \(r\) whose amida number is \(r + 1\).

An \(h\)-cluster in a graph is a set of \(h\) vertices which maximizes the number of edges in the graph induced by these vertices. We show that the connected \(h\)-cluster problem is NP-complete on planar graphs.

Lee conjectures that for any \(k > 1\), a \((n,nk)\)-multigraph decomposable into \(k\) Hamiltonian cycles is edge-graceful if \(n\) is odd. We investigate the edge-gracefulness of a special class of regular multigraphs and show that the conjecture is true for this class of multigraphs.

A balanced incomplete block design \(B[k, \alpha; v]\) is said to be a nested design if one can add a point to each block in the design and so obtain a block design \(B[k + 1, \beta; v]\). Stinson (1985) and Colbourn and Colbourn (1983) proved that the necessary condition for the existence of a nested \(B[3, \alpha; v]\) is also sufficient. In this paper, we investigate the case \(k = 4\) and show that the necessary condition for the existence of a nested \(B[4, \alpha; v]\), namely \(\alpha = 3\lambda\), \(\lambda(v – 1) \equiv 0 \pmod{4}\) and \(v \geq 5\), is also sufficient. To do this, we need the concept of a doubly nested design. A \(B[k, \alpha; v]\) is said to be doubly nested if the above \(B[k + 1, \beta; v]\) is also a nested design. When \(k = 3\), such a design is called a doubly nested triple system. We prove that the necessary condition for the existence of a doubly nested triple system \(B[3, \alpha; v]\), namely \(\alpha = 3\lambda\), \(\lambda(v – 1) \equiv 0 \pmod{2}\) and \(v \geq 5\), is also sufficient with the four possible exceptions \(v = 39\) and \(\alpha = 3, 9, 15, 21\).

We exhibit here an infinite family of planar bipartite graphs which admit a \(k\)-graceful labeling for all \(k \geq 1\).

It is shown that under certain conditions, the embeddings of chessboards in square boards, yield non-isomorphic associated graphs which have the same chro- matic polynomials. In some cases, sets of non-isomorphic graphs with this property are formed.

A diagonal Latin square is a Latin square whose main diagonal and back diagonal are both transversals. In this paper we give some constructions of pairwise orthogonal diagonal Latin squares (PODLS). As an application of such constructions we improve the known result about three PODLS and show that there exist three PODLS of order \(n\) whenever \(n > 46\); orders \(2 \leq n \leq 6\) are impossible, the only orders for which the existence is undecided are: \(10, 14, 15, 18, 21, 22, 26, 30, 33, 34\) and \(46\).