A Gray code is a list of words such that each word differs from its successor by a number of letters which is bounded independently of the length of the word. We use Roelants van Baronaigien’s I-code for involutions to derive a Gray code for all length-$n$ involutions and one for those with a given number of length-2 cycles. In both Gray codes, each involution is transformed into its successor via one or two transpositions or a rotation of three elements. For both Gray codes we obtain algorithms for passing between a word and its position in the list and a non-recursive sequencing algorithm (transforming a given word into its successor or determining that it is the last word in the list) which runs in \(O(n)\) worst-case time and uses \(O(1)\) auxiliary variables; for involutions with a given number of length-2 cycles we also obtain a sequencing algorithm which runs in \(O(1)\) worst-case time and uses \(O(n)\) auxiliary variables. We generalize Chase’s method for obtaining non-recursive sequencing algorithms to any list of words in which all the words with a given suffix form an interval of consecutive words, and we show that if in addition the letter preceding the suffix always takes at least two distinct values in that interval, then Ehrlich’s method will find in \(O(1)\) time the rightmost letter in which a word differs from its successor.

An edge-colouring of a graph \(G\) is \emph{equitable} if, for each vertex \(v\) of \(G\), the number of edges of any one colour incident with \(v\) differs from the number of edges of any other colour incident with \(v\) by at most one. In the paper, we prove that any outerplanar graph has an equitable edge-colouring with \(k\) colours for any integer \(k \geq 3\).

In this paper we give alternative and shorter proofs of three theorems of Chetwynd and Hilton. All these three theorems have been widely used in many research papers.

The paper defines \((a, d)\)-face antimagic labeling of a certain class of convex polytopes. The possible values of \(d\) are determined as \(d = 2, 4\) or \(6\). For \(d = 2\) and \(4\) we produce \((9n + 3, 2)\) and \((6n + 4, 4)\)-face antimagic labelings for the polytopes.

The domination number \(\gamma(G)\) and the irredundance number \(ir(G)\) of a graph \(G\) have been considered by many authors. It is well known that \(ir(G) \leq \gamma(G)\) holds for all graphs \(G\). In this paper we determine all pairs of connected graphs \((X, Y)\) such that every graph \(G\) containing neither \(X\) nor \(Y\) as an induced subgraph satisfies \(ir(G) = \gamma(G)\).

We consider an inner product of a special type in the space of \(n\)-tuples over a finite field \({F}_q\), of characteristic \(p\). We prove that there is a very close relationship between the self-dual \(q\)-ary additive codes under this inner product and the self-dual \(p\)-ary codes under the usual dot product. We prove the MacWilliams identities for complete weight enumerators of \(q\)-ary additive codes with respect to the new inner product. We define a two-tuple weight enumerator of a binary self-dual code and prove that it is invariant of a group of order 384. We compute the Molien series of this group and find a good polynomial basis for the ring of its invariants.

Let \(G\) be a simple graph with \(n\) vertices, and let \(\overline{G}\) denote the complement of \(G\). A well-known theorem of Nordhaus and Gaddum [6] bounds the sum \(\chi(G) + \chi(\overline{G})\) and product \(\chi(G)\chi(\overline{G})\) of the chromatic numbers of \(G\) and its complement in terms of \(n\). The \emph{edge cost} \(ec(G)\) of a graph \(G\) is a parameter connected with node fault tolerance studies in computer science. Here we obtain bounds for the sum and product of the edge cost of a graph and its complement, analogous to the theorem of Nordhaus and Gaddum.

In this paper we obtain some results on orthogonal arrays (O-arrays) of strength six by considering balanced arrays (B-arrays) of strength six with \(\underline{\mu}’ = (\mu – 1, \mu, \mu, \mu, \mu, \mu, \mu – 1)\) which we call Near O-arrays. As a consequence we demonstrate that we obtain better bounds on the number of constraints for some O-arrays as compared to those given by Rao (1947).

Let \([n, k, d; q]\)-codes be linear codes of length \(n\), dimension \(k\) and minimum Hamming distance \(d\) over \({GF}(q)\). Let \(d_7(n, k)\) be the maximum possible minimum Hamming distance of a linear \([n, k, d; 7]\)-code for given values of \(n\) and \(k\). In this paper, fifty-eight new linear codes over \({GF}(7)\) are constructed, the nonexistence of sixteen linear codes is proved and a table of \(d_7(n,k)\) \, \(k\leq7\), \(n\leq100\) is presented.

We study problems related to the number of edges of a graph with diameter constraints. We show that the problem of finding, in a graph of diameter \(k \geq 2\), a spanning subgraph of diameter \(k\) with the minimum number of edges is NP-hard. In addition, we propose some efficient heuristic algorithms for solving this problem. We also investigate the number of edges in a critical graph of diameter 2. We collect some evidence which supports our conjecture that the number of edges in a critical graph of diameter 2 is at most \(\Delta(n-\Delta)\) where \(\Delta\) is the maximum degree. In particular, we show that our conjecture is true for \(\Delta \leq \frac{1}{2}n\) or \(\Delta \geq n-5\).