MITSCHE , Dieter

The present report aims at giving a survey of my work since the end of my PhD thesis "Spectral Methods for Reconstruction Problems". Since then I focussed on the analysis of properties of different models of random graphs as well as their connection to real-world networks. This report's goal is to capture these problems in a common framework....

The metric dimension of a graph G is the minimum size of a subset S of vertices of G such that all other vertices are uniquely determined by their distances to the vertices in S. In this paper we investigate the metric dimension for two different models of random forests, in each case obtaining normal limit distributions for this parameter.

We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G ∈ G(n, r) in [0, sqrt(n)]^2. More precisely, let r_c denote the threshold radius for the appearance of the giant component in G(n, r). We then show that for any constant 0 < r < r_c , tw(G) = Θ(log n log log n), and for c being sufficiently large, and r =...

Let G = (V, E) be a connected graph with the usual (graph) distance metric d . Introduced by Gromov, G is δ-hyperbolic if for every four vertices u, v, x, y ∈ V , the two largest values of the three sums d(u, v) + d(x, y), d(u, x) + d(v, y), d(u, y) + d(v, x) differ by at most 2δ. In this paper, we determine precisely the value of this...

Random hyperbolic graphs have been suggested as a promising model of social networks. A few of their fundamental parameters have been studied. However, none of them concerns their spectra. We consider the random hyperbolic graph model as formalized by [GPP12] and essentially determine the spectral gap of their normalized Laplacian....

Pursuit-evasion games, such as the game of Revolutionaries and Spies, are a simplifi ed model for network security. In the game we consider in this paper, a team of r revolutionaries tries to hold an unguarded meeting consisting of m revolutionaries. A team of s spies wants to prevent this forever. For given r and m, the minimum number of spies...

Random hyperbolic graphs were recently introduced by Krioukov et. al. [KPK + 10] as a model for large networks. Gugelmann, Panagiotou, and Peter [GPP12] then initiated the rigorous study of random hyperbolic graphs using the following model: for α > 1/2 , C ∈ R, n ∈ N, set R = 2 ln n + C and build the graph G = (V, E) with |V | = n as follows:...

We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G(n, r) in [0,\sqrt{n}]^2. More precisely, we show that there exists some c1 > 0, such that for any constant 0 < r < c1, tw(G) = \Theta(log n/log log n), and also, there exists some c2 > c1, such that for any r = r(n) \geq c2, tw(G) = \Theta(r \sqrt{n}). Our...

We consider the random hyperbolic graph model introduced by [KPK + 10] and then formalized by [GPP12]. We show that, in the subcritical case α > 1, the size of the largest component is n^{1/(2α)+o(1)} , thus strengthening a result of [BFM15] which gave only an upper bound of n^{1/α+o(1)}.

Pursuit-evasion games, such as the game of Revolutionaries and Spies, are a simplifi ed model for network security. In the game we consider in this paper, a team of r revolutionaries tries to hold an unguarded meeting consisting of m revolutionaries. A team of s spies wants to prevent this forever. For given r and m, the minimum number of spies...

We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G(n, r) in [0,\sqrt{n}]^2. More precisely, we show that there exists some c1 > 0, such that for any constant 0 < r < c1, tw(G) = \Theta(log n/log log n), and also, there exists some c2 > c1, such that for any r = r(n) \geq c2, tw(G) = \Theta(r \sqrt{n}). Our...

In this paper we study the diameter of inhomogeneous random graphs G(n, κ, p) that are induced by irreducible kernels κ. The kernels we consider act on separable metric spaces and are almost everywhere continuous. We generalize results known for the Erd˝ os-Rényi model G(n, p) for several ranges of p. We find upper and lower bounds for the...

A unique-path labelling of a simple, fi nite graph is a labelling of its edges with real numbers such that, for every ordered pair of vertices (u,v), there is at most one nondecreasing path from u to v. In this paper we prove that any graph on n vertices that admits a unique-path labelling has at most n log_2(n)/2 edges, and that this bound is...

Let G be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex u to a neighbouring vertex v can be moved, provided that the weight on v is at least as large as the weight on u. The total acquisition number of G, denoted by a_t(G), is the minimum cardinality of the set of vertices with positive weight at the...

In this paper, we tackle the problem of designing a random mobility model generating a target node spatial distribution. More specifically, we solve a long standing open problem by presenting two versions of the well-known random waypoint (RWP) mobility model in bounded regions generating a uniform steady-state node spatial distribution. In the...

We examine a dynamic model for the disruption of information flow in hierarchical social networks by considering the vertex-pursuit game Seepage played in directed acyclic graphs (DAGs). In Seepage, agents attempt to block the movement of an intruder who moves downward from the source node to a sink. The minimum number of such agents required...

Given a class of graphs G closed under taking minors, we study the maximum degree Delta_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold with high probability. Among other results, we find classes of graphs providing orders of magnitude for Delta_n not observed before, such us log n/ log log log n and...

A mediator implements a correlated equilibrium when it pro- poses a strategy to each player con dentially such that the mediator's proposal is the best interest for every player to follow. In this paper, we present a mediator that implements the best correlated equilibrium for an extended El Farol game with symmetric players. The extended El...

The metric dimension of a graph $G$ is the minimum number of vertices in a subset $S$ of the vertex set of $G$ such that all other vertices are uniquely determined by their distances to the vertices in $S$. In this paper we investigate the metric dimension of the random graph $G(n,p)$ for a wide range of probabilities $p=p(n)$.

In this paper, we study a graph parameter that was recently introduced, the burning number, focusing on a few probabilistic aspects of the problem. The original burning number is revisited and analyzed for binomial random graphs G(n, p), random geometric graphs, and the Cartesian product of paths. Moreover, new variants of the burning number...

Suppose that you add rigid bars between points in the plane, and suppose that a constant fraction q of the points moves freely in the whole plane; the remaining fraction is constrained to move on fixed lines called sliders. When does a giant rigid cluster emerge? Under a genericity condition, the answer only depends on the graph formed by the...

A unique-path labelling of a simple, fi nite graph is a labelling of its edges with real numbers such that, for every ordered pair of vertices (u,v), there is at most one nondecreasing path from u to v. In this paper we prove that any graph on n vertices that admits a unique-path labelling has at most n log_2(n)/2 edges, and that this bound is...

A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number. In this paper, we study the asymptotic behaviour of the clique chromatic number of the random graph G(n, p) for a wide range of...

This paper proposes a comparison between rectilinear and radio-concentric networks. Indeed, those networks are often observed in urban areas, in several cities all over the world. One of the interesting properties of such networks is described by the \textit{straightness} measure from graph theory, which assesses how much moving from one node...

The cops-and-robber (CR) game has been used in mobile robotics as a discretized model (played on a graph G) of pursuit/evasion problems. The "classic" CR version is a perfect information game: the cops' (pursuer's) location is always known to the robber (evader) and vice versa. Many variants of the classic game can be defined: the robber can be...