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\).

A digraph \(D\) is reversible if it is isomorphic to the digraph obtained by reversing all arcs of \(D\). A digraph is subreversible if adding any arc between two non-adjacent vertices results in a reversible digraph. We characterize all subreversible digraphs which do not contain cycles of length 3 or 4.

In this paper we prove that, except for the 4-cycle and the 5-cycle, every 2-connected \(K(1,3)\)-free graph of diameter at most two is pancyclic.

The well-known clique tree representation for chordal graphs is extended to multidimensional representations for arbitrary graphs in which the number of vertices in the representation, minus the number of edges, plus the number of distinguished cycles, minus the number of distinguished polyhedra, and so on, always equals one. This approach generalizes both chordal graphs and cycle spaces of graphs. It also leads to a `dimension’ parameter that is shown to be no greater than the boxicity, chromatic number, and tree-width parameters.

An \(e=1\) function is a function \(f: V(G) \rightarrow [0,1]\) such that every non-isolated vertex \(u\) is adjacent to some vertex \(v\) such that \(f(u) + f(v) = 1\), and every isolated vertex \(w\) has \(f(w) = 1\). A theory of \(e=1\) functions is developed focussing on minimal and maximal \(e=1\) functions. Relationships are traced between \(e=1\) parameters and some well-known domination parameters, which lead to results about classical and fractional domination parameters.

We formulate the construction of 1-rotational difference families as a combinatorial optimization problem. A tabu search algorithm is used to find an optimal solution to the optimization problem for various 1-rotational difference family parameters. In particular, we construct two new 1-rotational difference families which lead to an equal number of new 1-rotational RBIBDs with parameters: \((36, 9, 8)\) and \((40, 10, 9)\). Our algorithm also was able to construct six non-isomorphic \((36, 9, 8)\) and three \((40, 10, 9)\) RBIBDs

For two vertices \(u\)  and \(v\) of a connected graph \(G\) , the set \(H(u,v)\) consists of all those vertices lying on a \(u-v\) geodesic in \(G\) . Given a set \(S\) of vertices of \(G\) , the union of all sets \(H(u,v)\) for \(u,v\in S\) is denoted by \(H(S)\) . A convex set \(S\) satisfies \(H(S)=S\) . The convex hull \([S]\) is the smallest convex set containing \(S\) . The hull number \(h(G)\) is the minimum cardinality among the subsets \(S\) of \(V(G)\) with \([S]=V(G)\) . A set \(S\) is a geodetic set if \(H(S)=V(G)\) ; while \(S\) is a hull set if \([S]=V(G)\) . The minimum cardinality of a geodetic set of \(G\) is the geodetic number \(g(G)\) . A subset \(T\) of a minimum hull set \(S\) is called a forcing subset for \(S\) if \(S\) is the unique minimum hull set containing \(T\) . The forcing hull number \(f(S,h)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\) , and the forcing hull number \(f(G,h)\) of \(G\) is the minimum forcing hull number among all minimum hull sets of \(G\) . The forcing geodetic number \(f(S,g)\)  of a minimum geodetic set \(S\) in \(G\) and the forcing geodetic number \(f(G,g)\) of \(G\) are defined in a similar fashion. The forcing hull numbers of several classes of graphs are determined. It is shown that for integers \(a,b\) with \(0\leq a\leq b\) , there exists a connected graph \(G\) such that \(f(G,h)=a\) and \(h(G)=b\) . We investigate the realizability of integers \(a,b\geq0\) that are the forcing hull and forcing geodetic numbers, respectively, of some graph.

Let \(C\) be a perfect 1-error-correcting code of length \(15\). We show that a quotient \(H(C)\) of the minimum distance graph of \(C\) constitutes an invariant for \(C\) more sensible than those studied up to the present, namely the kernel dimension and the rank. As a by-product, we get a nonlinear Vasil’ev code \(C\) all of whose associated Steiner triple systems are linear. Finally, the determination of \(H(C)\) for known families of \(C\)’s is presented.

A computer search shows that there does not exist a nested BIB design \(\text{NB}(10, 15, 2, 3)\).

We construct several families of simple 4-designs, which are closely related to Alltop’s series with parameters \(4-(2^f+1,5,5)\), \(f\) odd. More precisely, for every \(q=2^f\), where \(gcd(f,6)=1\), \(f\geq5\), we construct designs with the following parameters:

\[4-(q+1,6,\lambda),\, \text{where}\, \lambda\in\{60,70,90,100,150,160\},\]
\[4-(q+1,8,35),\]
\[4-(q+1,9,\lambda),\, \text{where}\, \lambda\in\{63,147\}.\]

Eulerian numbers may be defined recursively and have applications to many branches of mathematics. We derive some congruence and divisibility properties of Eulerian numbers.

In this paper, we determine the spectrum of support sizes of indecomposable threefold triple systems of order \(v\) for all \(v > 15\).