In this paper, we consider three conjectures of the computer program GRAFFITI. Moreover, we prove that every connected graph with minimum degree \(\delta\) and diameter \(d_m\) contains a matching of size at least \(\frac{\delta(d_m + 1)}{6}\). This inequality improves one of the conjectures under the additional assumption that \(\delta \geq 6\).

Let \(G\) be a \(1\)-tough graph of order \(n\). If \(|N(S)| \geq \frac{n + |S| – 1}{3}\)
for every non-empty subset \(S\) of the vertex set \(V(G)\) of \(G\), then \(G\) is hamiltonian.

We introduce generalized hooked, extended, and near-Skolem sequences and determine necessary conditions for their existence, the minimum number of hooks, and their permissible locations. We also produce computational results for small orders in each case.

Let \(H\) be a graph. An \(H\)-colouring of a graph \(G\) is an edge-preserving mapping of the vertices of \(G\) to the vertices of \(H\). We consider the Extendable \(H\)-colouring Problem, that is, the problem of deciding whether a partial \(H\)-colouring of some finite subset of the vertices of \(G\) can be extended to an \(H\)-colouring of \(G\). We show that, for a class of finitely described infinite graphs, Extendable \(H\)-colouring is undecidable for all finite non-bipartite graphs \(H\), and also for some finite bipartite graphs \(H\). Similar results are established when \(H\) is a finite reflexive graph.

Each vertex of a graph \(G = (V, E)\) dominates every vertex in its closed neighborhood. A set \(S \subset V\) is a dominating set if each vertex in \(V\) is dominated by at least one vertex of \(S\), and is an \emph{efficient dominating set} if each vertex in \(V\) is dominated by exactly one vertex of \(S\).

The domination excess \(de(G)\) is the smallest number of times that the vertices of \(G\) are dominated more than once by a minimum dominating set.

We study graphs having efficient dominating sets. In particular, we characterize such coronas and caterpillars, as well as the graphs \(G\) for which both \(G\) and \(\bar{G}\) have efficient dominating sets.

Then we investigate bounds on the domination excess in graphs which do not have efficient dominating sets and show that for any tree \(T\) of order \(n\),
\(de(T) \leq \frac{2n}{3} – 2\).

Let \(G = (V, E)\) be a graph. A vertex \(u\) strongly dominates a vertex \(v\) if \(uv \in E\) and \(\deg(u) > \deg(v)\). A set \(S \subseteq V\) is a strong dominating set of \(G\) if every vertex in \(V – S\) is strongly dominated by at least one vertex of \(S\).

The minimum cardinality among all strong dominating sets of \(G\) is called the strong domination number of \(G\) and is denoted by \(\gamma_{st}(G)\). This parameter was introduced by Sampathkumar and Pushpa Latha in [4].

In this paper, we investigate sharp upper bounds on the strong domination number for a tree and a connected graph. We show that for any tree \(T\) of order \(p > 2\) that is different from the tree obtained from a star \(K_{1,3}\) by subdividing each edge once,
\(\gamma_{st}(T) \leq \frac{4p – 1}{7}\)
and this bound is sharp.

For any connected graph \(G\) of order \(p \geq 3\), it is shown that \(\gamma_{st}(G) \leq \frac{2(p – 1)}{3}\) and this bound is sharp. We show that the decision problem corresponding to the computation of \(\gamma_{st}\) is NP-complete, even for bipartite or chordal graphs.

Let \(V\) be a finite set of order \(\nu\). A \((\nu, \kappa\lambda)\) packing design of index \(\lambda\) and block size \(\kappa\) is a collection of \(\kappa\)-element subsets, called blocks, such that every 2-subset of \(V\) occurs in at most \(\lambda\) blocks.

The packing problem is to determine the maximum number of blocks, \(\sigma(\nu\kappa\lambda)\), in a packing design. It is well known that
\(\sigma(\nu, \kappa\lambda) \leq \left[\frac{\nu}{\kappa}\left[ \frac{(\nu-1)}{(\kappa-1)}\lambda\right]\right] = \Psi(\nu, \kappa, \lambda)\), where \([x]\) is the largest integer satisfying \(x \geq [x]\).

It is shown here that \(\sigma(\nu, 5, \lambda) = \Psi(\nu, 5, \lambda) – e\) for all positive integers \(\nu \geq 5\) and \(7 \leq \lambda \leq 21\), where \(e = 1\text{ if } \lambda(\nu-1) \equiv 0 \pmod{\kappa-1} \text{ and } \lambda\nu\frac{(\nu-1)}{(\kappa-1)} \equiv 1 \pmod{\kappa}\) and \(e = 0\) otherwise with the following possible exceptions of \((\nu, \lambda)\) = (28,7), (32,7), (44,7), (32,9), (28,11), (39,11), (28,13), (28,15), (28,19), (39,21).