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].