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