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 \({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 \({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