Domination

A dominating set of a graph \(G=(V,E)\) is a subset \(D\) of \(V\) such that every vertex outside of \(D\) has at least one neighbor in \(D\). The domination number \(\gamma(G)\) of \(G\) denotes the size of a minimum dominating set of \(G\). The corresponding decision problem is a classical NP-complete problem in complexity theory.

Variants and Related Parameters

There exists a vast number of variants. We cover the most important.

Connected Domination. The graph induced by \(D\) is connected.

Total Domination. Every vertex of \(G\) has at least one neighbor in \(D\).

\(k\)-Domination. Every vertex of \(G\) not in \(D\) has at least \(k\) neighbors in \(D\).

Multiple Domination. Every vertex of \(G\) has at least \(k\) neighbors in \(D\).

\(k\)-Distance Domination. Every vertex of \(G\) not in \(D\) is in distance at most \(k\) of \(D\).

Roman Domination. A partition of \(V\) into sets \(V_0,V_1,V_2\) such that every vertex in \(V_0\) has a neighbor in \(V_2\). The weight of such a partition is \(|V_1|+2|V_2|\), and the Roman domination number of \(G\) is the minimum weight taken over all feasible partitions. (This variant can be interpreted as a solution to the problem of stationing Roman legions such that towns without a legion are protected by neighboring towns with at least two legions.)

Domatic Partitions. A partition of \(V\) into disjoint dominating sets. The domatic number is the maximum size of a domatic partition.

Irredundance. A vertex \(v\) in a set \(I\) is irredundant in \(I\) if it has a private neighbor w.r.t. \(I\); otherwise it is redundant. The set \(I\) is irredundant if all of its vertices are irredundant in \(I\). The irredundance number \(ir(G)\) denotes the size of a maximum irredundant set of \(G\). Since every minimum dominating set is maximal irredundant, every graph satisfies \(ir\leq\gamma\).

Problems

Find bounds and algorithms for the above parameters or relations between them. Problems may become easier when restricted to suitable graph classes.

Edge Connectivity

In 1932, Whitney proved that the vertex connectivity \(\kappa\) of a graph never exceeds its edge connectivity \(\lambda\), thereby establishing the classic set \[\kappa\leq\lambda\leq\delta\] of inequalities. The starting point for the topic at hand is a result proved by Chartrand in 1966, that if the minimum degree in a graph of order \(n\) is at least \(\frac12(n-1)\), then its edge connectivity equals its minimum degree. By Whitney's inequality, this gives a family of graphs that are, in a certain sense, maximally edge-connected. There exist a variety of conditions on a graph that guarantee that it is maximally edge-connected, many of which involve the degrees of vertices and diameter or girth.

Besides the classical edge connectivity, conditional and especially restricted edge connectivity recently received much attention as a measure of fault-tolerance in networks. In 1983, Harary proposed the quite general concept of conditional edge connectivity of a graph \(G\) with respect to some property \(\mathcal{P}\) to be the cardinality of the smallest set of edges in \(G\) whose removal results in a disconnected graph in which each component has property \(\mathcal{P}\). In the special case where \(\mathcal{P}\) is the property of having at least \(k\) vertices, this is referred to as \(k\)-restricted edge connectivity \(\lambda_k\) which was introduced by Fàbrega and Fiol in 1996.

Graphs that allow \(k\)-restricted edge cuts are called \(\lambda_k\)-connected and for small values of \(k\), the class of \(\lambda_k\)-connected graphs has been completely determined. In order to generalize Whitney's inequality \(\lambda\leq\delta\), the minimum \(k\)-edge degree \(\xi_k\) of a graph has been defined as the minimum number of edges leading out of a connected subgraph of order \(k\). Every connected graph of order at least \(2k\), except for the graphs containing a cut vertex whose removal leaves only components with at most \(k-1\) vertices, satisfies the inequality \(\lambda_k\leq\xi_k\) if its order, girth, or minimum degree is large enough.

A \(\lambda_k\)-connected graph \(G\) belonging to a class of graphs that satisfies \(\lambda_k\leq\xi_k\) is \(\lambda_k\)-optimal if its \(k\)-restricted edge connectivity equals its minimum \(k\)-edge degree. In recent years, much effort has been devoted to developing necessary and sufficient conditions for a graph to be \(\lambda_k\)-optimal.

Degree Sequences

The degree sequence of a graph is the non-increasing sequence of its vertex degrees. The degree sequence problem is the problem of finding one or all graphs with a degree sequence equal to a given non-increasing sequence of positive integers.

Every sequence with an even sum is realizable by a multigraph with loops. A sequence \(d_1\geq d_2\geq\cdots\geq d_n\) of non-negative integers is realizable by a simple graph if \(\sum_{i=1}^n d_i\) is even and \[\sum_{i=1}^k d_i\leq k(k-1)+\sum_{i=k+1}^n \min\{d_i,k\}\] for every \(k\in [n]\) (Erdos and Gallai 1960). A corresponding recursive algorithm is due to Havel (1955) and Hakimi (1962). Moreover, there exist conditions for the realization of sequences by forests and trees, weighted forests and trees, bipartite graphs, Hamiltonian graphs, and graphs with other given properties.

Score Sequences

The score sequence of a tournament is the non-increasing sequence of the outdegrees of its vertices. Score sequences of tournaments can be characterized by a set of inequalities similar to the Erdos-Gallai theorem (Landau 1953).

Score Sets

Every non-empty set of non-negative integers is score set of a tournament (Yao 1989; non-constructive proof). If the differences between the elements of a set increase strictly monotonic, then a tournament with matching score set can be constructed inductively (Pirzada and Naikoo 2006).

Problems

Find graph properties that can be characterized by degree sequences or conditions for degree sequences that imply certain graph properties.