We modify the Knuth-Klingsberg Gray code for unrestricted integer compositions to obtain a Gray code for integer compositions each of whose parts is bounded between zero and some positive integer. We also generalize Ehrlich’s method for loop-free sequencing to implement this Gray code in \(O(1)\) worst-case time per composition. The \((n-1)\)-part compositions of \(r\) whose \(i\)th part is bounded by \(n-i\) are the inversion vectors of the permutations of \(\{1,\ldots,n\}\) with \(r\) inversions; we thus obtain a Gray code and a loop-free sequencing algorithm for this set of permutations.

The following problem was introduced at a conference in 1995. Fires start at \(F\) nodes of a graph and \(D\) defenders (firefighters) then protect \(D\) nodes not yet on fire. Then the fires spread to any neighbouring unprotected nodes. The fires and the firefighters take turns until the fires can no longer spread. We examine two cases: when the fires erupt at random and when they start at a set of nodes which allows the fires to maximize the damage. In the random situation, for a given number of nodes, we characterize the graphs which minimize the damage when \(D = F = 1\) and we show that the Star is an optimal graph for \(D = 1\) regardless of the value of \(F\). In the latter case, optimal graphs are given whenever \(D\) is at least as large as \(F\).

In this paper, we are concerned with the existence of sets of mutually quasi-orthogonal Latin squares (MQOLS). We establish a correspondence between equidistant permutation arrays and MQOLS, which has facilitated a computer search to identify all sets of MQOLS of order \(\leq 6\). In particular, we report that the maximum number of Latin squares of order 6 in a mutually quasi-orthogonal set is 3, and give an example of such a set. We also report on a non-exhaustive computer search for sets of 3 MQOLS of order 10, which, whilst not identifying such a set, has led to the identification of all the resolutions of each \((10, 3, 2)\)-balanced incomplete block design. Improvements are given on the existence results for MQOLS based on groups, and a new construction is given for sets of MQOLS based on groups from sets of mutually orthogonal Latin squares based on groups. We show that this construction yields sets of \(2^n – 1\) MQOLS of order \(2^n\), based on two infinite classes of groups. Finally, we give a new construction for difference matrices from mutually quasi-orthogonal quasi-orthomorphisms, and use this to construct a \((2^n, 2^n; 2)\)-difference matrix over \({C}_2^{n-2} \times {C}_4\).

For a countable bounded principal ideal poset \(P\) and a natural number \(r\), there exists a countable bounded principal ideal poset \(P’\) such that for an arbitrary \(r\)-colouring of the points (resp. two-chains) of \(P’\), a monochromatically embedded copy of \(P\) can be found in \(P’\). Moreover, a best possible upper bound for the height of \(P’\) in terms of \(r\) and the height of \(P\) is given.

A vertex set \(S \subseteq V(G)\) is a perfect code or efficient dominating set for a graph \(G\) if each vertex of \(G\) is dominated by \(S\) exactly once. Not every graph has an efficient dominating set, and the efficient domination number \(F(G)\) is the maximum number of vertices one can dominate given that no vertex is dominated more than once. That is, \(F(G)\) is the maximum influence of a packing \(S \subseteq V(G)\). In this paper, we begin the study of \(LF(G)\), the lower efficient domination number of \(G\), which is the minimum number of vertices dominated by a maximal packing. We show that the decision problem associated with deciding if \(LF(G) \leq K\) is an NP-complete problem. The principal result is a characterization of trees \(T\) where \(LF(T) = F(T)\).

We introduce a new class of colorings of graphs and define and study two new graph coloring parameters. A \emph{coloring} of a graph \(G = (V,E)\) is a partition \(\Pi = \{V_1, V_2, \ldots, V_k\}\) of the vertices of \(G\) into independent sets \(V_i\), or \emph{color classes}. A vertex \(v_i \in V_i\) is called \emph{colorful} if it is adjacent to at least one vertex in every color class \(V_j\), \(i \neq j\). A \emph{fall coloring} is a coloring in which every vertex is colorful. If a graph \(G\) has a fall coloring, we define the \emph{fall chromatic number} (\emph{fall achromatic number}) of \(G\), denoted \(\chi_f(G)\), (\(\psi_f(G)\)) to equal the minimum (maximum) order of a fall coloring of \(G\), respectively. In this paper, we relate fall colorings to other colorings of graphs and to independent dominating sets in graphs.

This paper revises Park’s proof of Shannon inequality and also gives a new simple proof.

For \(\pi\) one of the upper domination parameters \(\beta\), \(\Gamma\), or \(IR\), we investigate graphs for which \(\pi\) decreases ( \(\pi\)-edge-critical graphs) and graphs for which \(\pi\) increases ( \(\pi^+\)-edge-critical graphs) whenever an edge is added. We find characterisations of \(\beta\)- and \(\Gamma\)-edge-critical graphs and show that a graph is \(IR\)-edge-critical if and only if it is \(\Gamma\)-edge-critical. We also exhibit a class of \(\Gamma^+\)-edge-critical graphs.

For a graph \(G = (V, E)\), a set \(S \subseteq V\) is a \(k\)-packing if the distance between every pair of distinct vertices in \(S\) is at least \(k+1\), and \(\rho_k(G)\) is the maximum cardinality of a \(k\)-packing. A set \(S \subseteq V\) is a distance-\(k\) dominating set if for each vertex \(u \in V – S\), the distance \(d(u, v) \leq k\) for some \(v \in S\). Call a vertex set \(S\) a \(k\)-independent dominating set if it is both a \(k\)-packing and a distance-\(k\) dominating set, and let the \(k\)-independent domination number \(i_k(G)\) be the minimum cardinality of a \(k\)-independent dominating set. We show that deciding if a graph \(G\) is not \(k\)-equipackable (that is, \(i_k(G) < \rho_k(G)\)) is an NP-complete problem, and we present a lower bound on \(i_k(G)\). Our main result shows that the sequence \((i_1(G), i_2(G), i_3(G), \ldots)\) is surprisingly not monotone. In fact, the difference \(i_{k+1}(G) – i_k(G)\) can be arbitrarily large.

Corresponding to chessboards, we introduce game boards with triangles or hexagons as cells and chess-like pieces for these boards. The independence number \(\beta\) is determined for many of these pieces.