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\).

Finding the probability that there is an operational path between two designated vertices in a probabilistic computer network is known to be NP-hard. Edge-packing is an efficient strategy to compute a lower bound on the probability. We prove that finding the set of paths that produces the best edge-packing lower bound is NP-hard.

Using a contraction method, we find some best-possible sufficient conditions for \(3\)-edge-comected simple graphs such that either the graphs have spanning eulerian subgraphs or the graphs are contractible to the Petersen graph.

We examine the problem of finding longest cycles in inner triangulations, that is, \(2\)-connected planar graphs in which all interior faces are triangles. These include the important family of geometric graphs called Delaunay triangulations In particular, we present two efficient heuristics for finding a longest cycle in an inner triangulation. The heuristics operate by considering at each step a local set of faces adjacent to the current cycle as candidates for inclusion in the cycle.