We describe an algorithm that uses \( O(n) \) arithmetic operations for computing the determinant of the matrix \( M = (A + \alpha I) \), where \( A \) is the adjacency matrix of an order \( n \) tree. Combining this algorithm with interpolation, we derive a simple algorithm requiring \( O(n^2) \) arithmetic operations to find the characteristic polynomial of the adjacency matrix of any tree. We apply our algorithm and recompute a 22-degree characteristic polynomial, which had been incorrectly reported in the quantum chemistry literature.

A vertex set \( D \) of a graph \( G \) is a dominating set if every vertex not in \( D \) is adjacent to some vertex in \( D \). The domination number \( \gamma \) of a graph \( G \) is the minimum cardinality of a dominating set in \( G \). In 1989, Brigham and Dutton [1] proved

\[
\gamma(G) \leq \left\lceil\frac{3n-g}{6}\right\rceil
\]

for each graph \( G \) of order \( n \), minimum degree \( \delta \geq 2 \), and girth \( g \geq 5 \). For this class of graphs, Volkmann [8] recently gave the better bound

\[
\gamma(G) \leq \left\lceil\frac{3n-g-6}{8}\right\rceil
\]

if \( G \) is neither a cycle nor one of two exceptional graphs. If \( G \) is a graph of order \( n \), minimum degree \( \delta \geq 2 \), girth \( g \geq 5 \), then we show in this paper that

\[
\gamma(G) \leq \left\lceil\frac{3n-g-9}{6}\right\rceil
\]

if \( G \) is neither a cycle nor one of 40 exceptional graphs of order between 8 and 21.

A caterpillar \( R \) is a tree with the property that after deleting all vertices of degree 1, we obtain a path \( P \) or a single vertex. The path \( P \) is called the spine of caterpillar \( R \). If the spine has length 3 and \( R \) contains vertices of degrees \( r, s, 2, 2 \), where \( r, s > 2 \), then we say that \( R \) is a \( \{r, s, 2, 2\} \)-caterpillar of diameter 5. We completely characterize \( \{r, s, 2, 2\} \)-caterpillars of diameter 5 on \( 4k + 2 \) vertices that factorize \( K_{4k+2} \).

In the theory of cocyclic self-dual codes, three types of equivalences are encountered: cohomology or the equivalence of cocycles, Hadamard equivalence or the equivalence of Hadamard matrices, and the equivalence of binary linear codes. There are some results relating the latter two equivalences, see Ozeki [12], but not when the Hadamard matrices are un-normalised.

Recently, Horadam [9] discovered shift action, whereby every finite group \( G \) acts as a group of automorphisms of \( Z = Z^2(G, C) \), the finite abelian group of cocycles from \( G \times G \to C \), for each abelian group \( C \). These automorphisms fix the subgroup of coboundaries \( B \leq Z \) setwise. This shift action of \( G \) on \( Z \) partitions each cohomology class of \( Z \).

Here we show that shift-equivalent cocycles generate equivalent Hadamard matrices and that shift-equivalent cocyclic Hadamard matrices generate equivalent binary linear codes.

New identities involving the Catalan sequence ordinary generating function are developed, and a previously known one established from first principles using a hypergeometric approach.

We examine words \( w \) satisfying the following property: if \( x \) is a subword of \( w \) and \( |x| \) is at least \( k \) for some fixed \( k \), then the reversal of \( x \) is not a subword of \( w \).

For constructing routes in mobile ad-hoc networks (MANET) and sensor networks, it is highly desirable to perform primitive computations locally. If a network can be represented in the doubly connected edge list (DCEL) data structure, then many operations can be done locally. However, the DCEL data structure can be used to represent only planar graphs. In this paper, we propose an extended version of the DCEL data structure called ExtDCEL that can be used for representing non-planar graphs as well as their planar components. The proposed data structure can be used to represent geometric networks in mobile computing that include unit disk graphs, Gabriel graphs, and constrained Delaunay triangulations. We show how the proposed data structure can be used to implement a hybrid greedy face routing algorithm in optimum \( O(m) \) time, where \( m \) is the number of edges in the unit disk graph. We also report on the implementation of several routing algorithms for mobile computing by using the proposed data structure.

In this paper, we study the decomposition of the graph \( (\lambda D_v)^{+\alpha} \) into extended cyclic triples, for all \( \lambda \geq \alpha \). By an extended cyclic triple, we mean a loop, a loop with symmetric arcs attached (known as a lollipop), or a directed \( 3 \)-cycle (known as a cyclic triple).

In this paper, we consider the problem of the non-existence of some orthogonal arrays (O-arrays) of strength four with two levels, the number of constraints \( k \) satisfying \( 4 \leq k \leq 32 \), and index set \( \lambda \) where \( 1 \leq \lambda \leq 64 \).

We give a constructive proof that a planar graph on \( n \) vertices with degree of regularity \( k \) exists for all pairs \( (n,k) \) except for two pairs \( (7,4) \) and \( (14,5) \). We continue this theme by classifying all strongly regular planar graphs, and then consider a new class of graphs called \( 2 \)-\emph{strongly regular}. We conclude with a conjectural classification of all planar \( 2 \)-strongly regular graphs.