Tournaments

A tournament is an orientation of a complete undirected graph. The name originates from the interpretation as the outcome of a single round-robin tournament without draws.

Semicomplete Digraphs

A digraph is semicomplete if every pair of vertices is connected by a single directed edge or by two directed edges forming a cycle of length two.

Locally Semicomplete Digraphs and Local Tournaments

A digraph is locally semicomplete (a local tournament) if the digraphs induced by in-neighbors and the out-neighbors of any vertex form a semicomplete digraph (a tournament).

In- and Out-Tournaments

A digraph is an in-tournament (out-tournament) if the digraph induced by the in-neighbors (out-neighbors) of any vertex form a tournament.

Multipartite Tournaments

A digraph is a multipartite tournament if there exists a partition of its vertex set such that there is no edge between vertices of the same partition and exactly one directed edge between vertices in different partitions.

Paths and Cycles

Tournaments have a rich path and cycle structure. For example, every tournament has a Hamiltonian path (Redei 1934) and every strongly connected tournament has a Hamiltonian cycle (Camion 1959). Even stronger, every strongly connected tournament is vertex pancyclic (Moon 1966). Moreover, every \(2\)-connected tournament is a weakly Hamiltonian-connected, every edge of every \(3\)-connected tournament lies on a Hamiltonian cycle, every \(4\)-connected tournament is strongly Hamiltonian-connected (Thomassen 1980).

Questions

We are interested in the existence of paths and cycles of generalizations of tournaments.

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.