Given a matrix in companion form over \(GF(2)\), whose characteristic polynomial is irreducible, a tridiagonal matrix, similar to the original one, is found, by constructing the similarity transformation. The theoretical basis is founded on the Lanczos tridiagonalization method, valid in the Complex domain. A variant of the Lanczos method, based on LU decomposition requirements, is modified to apply in the finite field \(GF(2)\). The work is derived from an application in VLSI design, where the matrices in companion form and in tridiagonal form represent two similar linear finite state machines, used for pseudo-random pattern generation and digital circuit testing. The construction of the similarity transformation between the matrices makes it possible to obtain directly the separate implementation of the two corresponding machines.

We determine all graphs \(G\) of order at least \(k + 1\), \(k \geq 3\), with the property that for any \(k\)-subset \(S\) of \(V(G)\) there is a unique vertex \(x, x \in V(G) – S\), which has exactly two neighbours in \(S\). Such graphs have exactly \(k + 1\) vertices and consist of a family of vertex-disjoint cycles. When \(k = 2\) it is clear that graphs with this property are the so-called friendship graphs.

In this paper, we deal with recursive constructions for incomplete group divisible designs (IGDDs). Denoting \(GD[k,1,v; uv] – GD[k,1,n; un]\) by \((u,k)-IGD[v,n]\), we will prove, as an application, that a \((7,4)-IGD[v,n]\) exists if and only if \(v \geq 3n\) and \(\text{v – n} \equiv 0 \pmod{2}\).

We investigate the labellings of sum graphs, necessary conditions for a graph to be a sum graph, and the range of edge numbers of sum graphs.

A set \(S\) of vertices of a graph is \(k\)-independent if each vertex in \(S\) is adjacent to at most \(k-1\) other vertices in \(S\). A graph \(G\) is well-\(k\)-covered if every maximal \(k\)-independent set is maximum. We shall characterize the well-\(k\)-covered trees and for \(k=2\) all such graphs of girth \(8\) or more.

We derive a first-order recurrence for \(a_n(t) = \sum_{k=0}^{n} \frac{(-1)^{n-k}}{1+tk} \binom{n}{k}\) (\(t\) fixed \(t\neq -\frac{1}{m}, m\in \mathbb{N}\)). The first-order recurrence yields an alternative proof for Riordan’s theorem: \(a_n(t) = \binom{1/{t+n}}{n}^{-1}(-1)^n\) and also yields the ordinary generating function \(\sum_{n=0}^{\infty} a_n(t) x^n\) for \(t \in \mathbb{N}.\)From the latter, one easily computes \(\sum_{n=0}^{\infty}a_n(t)\) which turns out to be the well-known \(\sum_{n=0}^{\infty} \frac{(-1)^n}{n+1} = \ln 2\) for \(t=1\). For \(t=2\), we get \(\sum_{n=0}^{\infty} (-1)^n\frac{2n}{(2n+1)} = \frac{\ln(\sqrt{2}+1)}{\sqrt{2}}\).

Avis has shown that the number of vertices of a minimal triangle-free \(5\)-chromatic graph is no fewer than \(19\). Mycielski has shown that this number is no more than \(23\). In this paper, we improve these bounds to \(21\) and \(22\), respectively.

By a refinement of a rank argument used to prove a directed version of the Graham-Pollak theorem, we show that \(n\) bicliques are needed to partition the arc-set of the complement of a directed cycle.

In this paper, we obtain a polynomial inequality of degree three in \(m\) (the number of constraints), with coefficients involving the parameters \(\mu_i\)’s, on the existence of balanced arrays of strength four and with two symbols. Applications of the inequality to specific balanced arrays for obtaining an upper bound on the number of constraints are also discussed.

Let \(r(G)\) denote the rank, over the field of rational numbers, of the adjacency matrix of a graph \(G\). Van Nuffelen and Ellingham have obtained several inequalities which relate \(r(G)\) to other graph parameters such as chromatic number, clique number, Dilworth number, and domination number. We obtain additional results of this type. Our main theorem is that for graphs \(G\) having no isolated vertices, \(OIR(G) \leq r(G)\), where \(OIR(G)\) denotes the upper open irredundance number of \(G\).