In this paper, we look at triangle-free graphs with maximum degree three. By an inequality proved by K. Fraughnaugh\(^*\) in 1990, the number of vertices \(v\), edges \(e\), and independence \(i\) of such a graph satisfy \(e \geq \frac{13v}{2} – 14i\). We prove that there is a unique non-cubic, connected graph for which this inequality is sharp. For the cubic case, we describe a computer algorithm that established that two such extremal cubic graphs exist with \(v = 14\), and none for \(v = 28\) or \(42\). We give a complete list of cubic, and provide some new examples of non-cubic, triangle-free graphs with \(v \leq 36\) and independence ratio \(\frac{i}{v}\) less than \(\frac{3}{8}\).

Fibonacci strings turn out to constitute worst cases for a number of computer algorithms which find generic patterns in strings. Examples of such patterns are repetitions, Abelian squares, and “covers”. In particular, we characterize in this paper the covers of a circular Fibonacci string \(\mathcal{C}(F_k)\) and show that they are \(\Theta(|F_k|^2)\) in number. We show also that, by making use of an appropriate encoding, these covers can be reported in \(\Theta(|F_k|)\) time. By contrast, the fastest known algorithm for computing the covers of an arbitrary circular string of length \(n\) requires time \(O(n \log n)\).

A polychrome labeling of a simple and connected graph \(G = (V, E)\) by an abelian group \(A\) is a bijective map from \(V\) onto \(A\) such that the induced edge labeling \(f^*(vw) = f(v) + f(w)\), \(vw \in E\), is injective. The paper completes the characterization of polychrome paths and cycles begun in [3].

We introduce a generalisation of the concept of a complete mapping of a group, which we call a quasi-complete mapping, and which leads us to a generalised form of orthogonality in Latin squares. In particular, the existence of a quasi-complete mapping of a group is shown to be sufficient for the existence of a pair of Latin squares such that if they are superimposed so as to form an array of unordered pairs, each unordered pair of distinct elements occurs exactly twice. We call such a pair of Latin squares quasi-orthogonal and prove that an abelian group possesses a quasi-complete mapping if and only if it is not of the form \(\mathbb{Z}_{4m+2} \oplus G\), \(|G|\) odd. In developing the theory of quasi-complete mappings, we show that the well-known concept of a quasi-complete Latin square arises quite naturally in this setting. We end the paper by giving a sufficient condition for the existence of a pair of quasi-orthogonal Latin squares which are also quasi-row-complete.

For different properties \(\mathcal{P}\) of a connected graph \(G\), we characterize the connected graphs \(F\) (resp. the pairs \((X,Y)\) of connected graphs) such that \(G\) has Property \(\mathcal{P}\) if \(G\) does not admit \(F\) (resp. neither \(X\) nor \(Y\)) as an induced subgraph.

We consider here the lower independence, domination, and irredundance parameters, which are related by the well-known inequalities \(ir \leq \gamma \leq i \leq \alpha \leq \Gamma \leq IR\), and the properties \(\mathcal{P}\) correspond to the equality between some
of these parameters.

Given that an array \(A[i_{1}, \ldots, i_{d}]\), \(1 \leq i_1 \leq m, \ldots 1 \leq i_d \leq m\), has a \emph{period} \(A[p_{1}, \ldots, p_{d}]\) of dimension \(p_1 \times \cdots p_{d}\) if \(A[i_{1}, \ldots, i_{d}] = A[i_{1} + p_{1}, \ldots, i_{d} + p_{d}]\)
for \(i_{1}, \ldots, i_{d} = 1, \ldots, m – (p_{1}, \ldots, p_{d})\). The \emph{period} of the array is \(A[p_{1}, \ldots, p_{d}]\) for the shortest such \(q = p_{1}, \ldots, p_{d}\).

Consider this array \(A\); we prove a lower bound on the computation of the period length less than \(m^{d}/2^d\) of \(A\) with time complexity
\[
\Omega({\log \log_a m}), \text{ where } a = m^{d^2}
\]
for \(O(m^d)\) work on the CRCW PRAM model of computation.

This paper contains a characterization of Baer \(^*\)-rings with finitely many elements in terms of matrix rings over finite fields. As an application, one can easily verify whether a given matrix ring over a finite field is a Baer \(^*\)-ring or not.

A function \(f: V \rightarrow \mathbb{R}\) is defined to be an \(\mathbb{R}\)-dominating function of graph \(G = (V, E)\) if the sum of the function values over any closed neighbourhood is at least 1. That is, for every \(v \in V\),
\(f(N(v) \cup \{v\}) \geq 1\).

The \(\mathbb{R}\)-domination number \(\gamma_{\mathbb{R}}(G)\) of \(G\) is defined to be the infimum of \(f(V)\) taken over all \(\mathbb{R}\)-dominating functions \(f\) of \(G\).

In this paper, we investigate necessary and sufficient conditions for \(\gamma_{\mathbb{R}}(G) = \gamma(G)\), where \(\gamma(G)\) is the standard domination number.

It is shown that the determinant of the variable adjacency matrix, and hence the determinant of the adjacency matrix of a graph, are circuit polynomials. From this, it is deduced that determinants of symmetric matrices are indeed circuit polynomials of associated graphs.
The results are then extended to general matrices

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