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)\le \lceil \frac{3n-g}{6}\rceil$$

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

$$\gamma (G)\le \lceil \frac{3n-g-6}{8}\rceil$$

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

$$\gamma (G)\le \lceil \frac{3n-g-9}{6}\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\le 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 \ge \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\le k\le 32$, and index set $\lambda$ where $1\le \lambda \le 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.

This paper answers the question as to whether every natural number $n$ is realizable as the number of ones in the top portion of rows of a general binary Pascal triangle. Moreover, the minimum number $\kappa (n)$ of rows is determined so that $n$ is realizable.

A $(p,q)$-graph $G$ is said to be \textbf{edge-graceful} if the edges can be labeled by $1,2,\dots ,q$ so that the vertex sums are distinct, mod $p$. It is shown that if a tree $T$ is edge-graceful, then its order must be odd. Lee conjectured that all trees of odd orders are edge-graceful. The conjecture is still unsettled. In this paper, we give the state of the progress toward this tantalizing conjecture.

We use a new technique for decomposition of complete graphs with even number of vertices based on $2n$-cyclic blended labeling to show that for every $k>1$ odd, and every $d$, $3\le d\le 2^{q}k–1$, there exists a spanning tree of diameter $d$ that factorizes $K_{2^{q}k}$.

A constant composition code of length $n$ over a $k$-ary alphabet has the property that the numbers of occurrences of the $k$ symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. Using exhaustive and probabilistic clique search, and by applying theorems and constructions in past literature, we generate tables which summarize the best known lower bounds on constant composition codes for (i) $3\le k\le 8$, (ii) $k=3$, $9\le n\le 12$, and (iii) various other interesting parameters with $n\ge 9$.

In this paper, we develop a computational method for constructing transverse $t$-designs. An algorithm is presented that computes the $G$-orbits of $k$-element subsets transverse to a partition $\mathcal{H}$, given that an automorphism group $G$ is provided. We then use this method to investigate transverse Steiner quadruple systems. We also develop recursive constructions for transverse Steiner quadruple systems, and we provide a table of existence results for these designs when the number of points $v\le 24$. Finally, some results on transverse $t$-designs with $t>3$ are also presented.

A vertex-magic total labeling of a graph $G(V,E)$ is defined as a one-to-one mapping from $V\cup E$ to the set of integers $\{1,2,\dots ,|V|+|E|\}$ with the property that the sum of the label of a vertex and the labels of all edges incident to this vertex is the same constant for all vertices of the graph. A supermagic labeling of a graph $G(V,E)$ is defined as a one-to-one mapping from $E$ to the set of integers $\{1,2,\dots ,|E|\}$ with the property that the sum of the labels of all edges incident to a vertex is the same constant for all vertices of the graph.

In this paper, we present a technique for constructing vertex-magic total labelings of products of certain vertex-magic total $r$-regular graphs $G$ and certain $2_s$-regular supermagic graphs $H$. $H$ has to be decomposable into two $s$-regular factors and if $r$ is even, $|H|$ has to be odd.

At each vertex in a Cayley map, the darts emanating from that vertex are labeled by a generating set of a group. This generating set is closed under inverses. Two classes of Cayley maps are balanced and antibalanced maps. For these cases, the distributions of the inverses about the vertex are well understood. For a balanced Cayley map, either all the generators are involutions or each generator is directly opposite across the vertex from its inverse. For an antibalanced Cayley map, there is a line of reflection in the tangent plane of the vertex so that the inverse generator for each dart label is symmetric across that line. An $e$-balanced Cayley map is a recent generalization that has received much study, see for example [2, 6, 7, 13]. In this note, we examine the symmetries of the inverse distributions of $e$-balanced maps in a manner analogous to those of balanced and antibalanced maps.