Source author record

Jiangdong Ai

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

3works

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

k-Ary spanning trees contained in tournaments

A rooted tree is called a $k$ -ary tree, if all non-leaf vertices have exactly $k$ children, except possibly one non-leaf vertex has at most $k-1$ children. Denote by $h(k)$ the minimum integer such that every tournament of order at least $h(k)$ contains a $k$ -ary spanning tree. It is well-known that every tournament contains a Hamiltonian path, which implies that $h(1)=1$ . Lu et al. [J. Graph Theory {\bf 30}(1999) 167--176] proved the existence of $h(k)$ , and showed that $h(2)=4$ and $h(3)=8$ . The exact values of $h(k)$ remain unknown for $k\geq 4$ . A result of Erdős on the domination number of tournaments implies $h(k)=Ω(k\log k)$ . In this paper, we prove that $h(4)=10$ and $h(5)\geq13$ .

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.

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.