Source author record

Stefanie Gerke

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Results on the Small Quasi-Kernel Conjecture

A {\em quasi-kernel} of a digraph $D$ is an independent set $Q\subseteq V(D)$ such that for every vertex $v\in V(D)\backslash Q$ , there exists a directed path with one or two arcs from $v$ to a vertex $u\in Q$ . In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. In 1976, Erdős and Sźekely conjectured that every sink-free digraph $D=(V(D),A(D))$ has a quasi-kernel of size at most $|V(D)|/2$ . In this paper, we give a new method to show that the conjecture holds for a generalization of anti-claw-free digraphs. For any sink-free one-way split digraph $D$ of order $n$ , when $n\geq 3$ , we show a stronger result that $D$ has a quasi-kernel of size at most $\frac{n+3}{2} - \sqrt{n}$ , and the bound is sharp.

preprint2020arXiv

Proximity and Remoteness in Directed and Undirected Graphs

Let $D$ be a strongly connected digraph. The average distance $\barσ(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the distances from $v$ to all other vertices of $D$ . The remoteness $ρ(D)$ and proximity $π(D)$ of $D$ are the maximum and the minimum of the average distances of the vertices of $D$ , respectively. We obtain sharp upper and lower bounds on $π(D)$ and $ρ(D)$ as a function of the order $n$ of $D$ and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament $T$ , we have $π(T)=ρ(T)$ if and only if $T$ is regular. Due to this result, one may conjecture that every strong digraph $D$ with $π(D)=ρ(D)$ is regular. We present an infinite family of non-regular strong digraphs $D$ such that $π(D)=ρ(D).$ We describe such a family for undirected graphs as well.

preprint2013arXiv

Non-Vertex-Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn and Vu \cite{JKV} regarding threshold functions for the existence of an $H$ -factor in a random graph \gnp. We prove that the conjectured threshold function is correct for any graph $H$ which is not covered by its densest subgraphs. We also demonstrate that the main result of \cite{JKV} generalises to multigraphs, digraphs, and a multipartite model.

preprint2010arXiv

No Dense Subgraphs Appear in the Triangle-free Graph Process

Consider the triangle-free graph process, which starts from the empty graph on $n$ vertices and a random ordering of the possible ${n \choose 2}$ edges; the edges are added in this ordering provided the graph remains triangle free. We will show that there exists a constant $c$ such that no copy of any fixed finite triangle-free graph on $k$ vertices with at least $ck$ edges asymptotically almost surely appears in the triangle-free graph process.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.