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.

We study the discrepancies of set systems whose incidence matrices are encoded by binary strings which are complex in the sense of Kolmogorov-Chaitin. We show that these systems display an optimal degree of irregularity of distribution.

We use the idea of compressibility to examine the discrepancy of set systems coded by complex sequences.

A multigraph is irregular if no two of its vertices have the same degree. It is known that every graph \(G\) with at most one trivial component and no component isomorphic to \(K_2\) is the underlying graph of some irregular multigraph. The irregularity cost of a graph with at most one trivial component and no component isomorphic to \(K_2\) is defined by \(ic(G) = \min\{|{E}(H)| – |{E}(G)| \mid H \text{ is an irregular multigraph containing } G \text{ as underlying graph}\}\). It is shown that if \(T\) is a tree on \(n\) vertices, then

\[\frac{n^2-3n+4}{4}\quad \leq \quad ic(T) \leq \binom{n-1}{2}\: \text{if}\: n\equiv0 \;\text{or}\; 3\pmod{4} \; \text{and}\]
\[\frac{n^2-3n+6}{4}\quad \leq \quad ic(T) \leq \binom{n-1}{2}\: \text{if}\: n\equiv1 \;\text{or}\; 2\pmod4 \]
Furthermore, these bounds are shown to be sharp.

The conjecture by E. Wojcicka, that every 3-domination-critical graph with minimum degree at least two is hamiltonian, has recently been proved in three different papers by five different authors. We survey the results which lead to the proof of the conjecture and consolidate them to form a unit.

The inflated graph \(G_1\) of a graph \(G\) is obtained by replacing every vertex of degree \(d\) by a clique \(K_d\). We pursue the investigation of domination related parameters of inflated graphs initialized by Dunbar and Haynes. They conjectured that the lower irredundance and domination parameters are equal for inflated graphs. Favaron showed that in general the difference between them can be as large as desired. In this article, we prove that the two parameters are equal for inflated trees.

This paper considers the following question: how many non-isomorphic proper edge-colourings (with any number of colours) are there of the complete graph \(K_n\)? We prove an asymptotic result and enumerate the solutions for \(n \leq 6\).

A directed network connecting a set \(A\) to a set \(B\) is a digraph containing an \(a\)-\(b\) path for each \(a \in A\) and \(b \in B\). Vertices in the directed network not in \(A \cup B\) are Steiner points. We show that in a finitely compact metric space in which geodesics exist, any two finite sets \(A\) and \(B\) are connected by a shortest directed network. We also bound the number of Steiner points by a function of the sizes of \(A\) and \(B\). Previously, such an existence result was known only for the Euclidean plane [M. Alfaro, Pacific J. Math. 167 (1995) 201-214]. The main difficulty is that, unlike the undirected case (Steiner minimal trees), the underlying graphs need not be acyclic.

Existence in the undirected case was first shown by E. J. Cockayne [Canad. Math. Bull. 10 (1967) 431-450].

A graph \(G\) is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let \(F\) be a 2-stratified graph rooted at some blue vertex \(v\). An \(F\)-coloring of a graph is a red-blue coloring of the vertices of \(G\) in which every blue vertex \(v\) belongs to a copy of \(F\) rooted at \(v\). The \(F\)-domination number \(\gamma_F(G)\) is the minimum number of red vertices in an \(F\)-coloring of \(G\). In this paper, we determine the \(F\)-domination number of the prisms \(C_n \times K_2\) for all 2-stratified claws \(F\) rooted at a blue vertex.

In this study, we consider the effect on the upper irredundance number \(IR(G)\) of a graph \(G\) when an edge is added joining a pair of non-adjacent vertices of \(G\). We say that \(G\) is \(IR\)-insensitive if \(IR(G + e) = IR(G)\) for every edge \(e \in \overline{E}\). We characterize \(IR\)-insensitive bipartite graphs and give a constructive characterization of graphs \(G\) for which the addition of any edge decreases \(IR(G)\). We also demonstrate the existence of a wide class of graphs \(G\) containing a pair of non-adjacent vertices \(u,v\) such that \(IR(G + uv) > IR(G)\).

A graph \(G\) is called \((a:b)\)-choosable if for every assignment of \(a\)-sets \(L(v)\) to the vertices of \(G\) it is possible to choose \(b\)-subsets \(M(v) \subseteq L(v)\) so that adjacent vertices get disjoint subsets. We give a different proof of a theorem of Tuza and Voigt that every \(2\)-choosable graph is \((2k:k)\)-choosable for any positive integer \(k\). Our proof is algorithmic and can be implemented to run in time \(O(k|V(G)|)\).

We prove some general results on irredundant sets of queens on chessboards, and determine the irredundance numbers of the queens graph \(Q_n\), for \(n = 5, 6\).

Let \(G\) be a graph. The weak domination number of \(G\), \(\gamma_w(G)\), is the minimum cardinality of a set \(D\) of vertices where every vertex \(u \notin D\) is adjacent to a vertex \(v \in D\), where \(\deg(v) \leq \deg(u)\). The strong domination number of \(G\), \(\gamma_s(G)\), is the minimum cardinality of a set  \(D\) of vertices where every vertex \(u \notin D\) is adjacent to a vertex \(v \in D\), where \(\deg(v) \geq \deg(u)\). Similarly, the independent weak domination number, \(i_w(G)\), and the independent strong domination number, \(i_{st}(G)\), are defined with the additional requirement that the set \(D\) is independent. We find upper bounds on the number of edges of a graph in terms of the number of vertices and for each of these four domination parameters. We also characterize all graphs where equality is achieved in each of the four bounds.

For \(k \geq 2\), the \(P_k\)-free domination number \(\gamma(G; -P_k)\) is the minimum cardinality of a dominating set \(S\) in \(G\) such that the subgraph \(\langle S \rangle\) induced by \(S\) contains no path \(P_k\) on \(k\) vertices. The path-free domination number is at least the domination number and at most the independent domination number of the graph. We show that if \(G\) is a connected graph of order \(n \geq 2\), then \(\gamma(G; -P_k) \leq n + 2(k – 1) – 2\sqrt{n(k-1)}\), and this bound is sharp. We also give another bound on \(\gamma(G; -P_k)\) that yields the corollary: if \(G\) is a graph with \(\gamma(G) \geq 2\) that is \(K_{1,t+1}\)-free and \((K_{1,t+1}+e)\)-free (\(t \geq 3\)), then \(\gamma(G; -P_3) \leq (t-2)\gamma(G) – 2(t-3)\), and we characterize the extremal graphs for the corollary’s bound. Every graph \(G\) with maximum degree at most \(3\) is shown to have equal domination number and \(P_3\)-free domination number. We define a graph \(G\) to be \(P_k\)-domination perfect if \(\gamma(H) = \gamma(H; -P_k)\) for every induced subgraph \(H\) of \(G\). We show that a graph \(G\) is \(P_3\)-domination perfect if and only if \(\gamma(H) = \gamma(H; -P_3)\) for every induced subgraph \(H\) of \(G\) with \(\gamma(H) = 3\).