Source author record

Zhangdong Ouyang

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the size of matchings in 1-planar graph with high minimum degree

A matching of a graph is a set of edges without common end vertex. A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Recently, Biedl and Wittnebel proved that every 1-planar graph with minimum degree 3 and $n\geq 7$ vertices has a matching of size at least $\frac{n+12}{7}$ , which is tight for some graphs. They also provided tight lower bounds for the sizes of matchings in 1-planar graphs with minimum degree 4 or 5. In this paper, we show that any 1-planar graph with minimum degree 6 and $n \geq 36$ vertices has a matching of size at least $\frac{3n+4}{7}$ , and this lower bound is tight. Our result confirms a conjecture posed by Biedl and Wittnebel.

preprint2020arXiv

New upper bounds for the crossing numbers of crossing-critical graphs

A graph $G$ is { $k$ -crossing-critical} if $cr(G)\ge k$ , but $cr(G\setminus e)<k$ for each edge $e\in E(G)$ , where $cr(G)$ is the crossing number of $G$ . It is known that for any $k$ -crossing-critical graph $G$ , $cr(G)\le 2.5k+16$ holds, and in particular, if $δ(G)\ge 4$ , then $cr(G)\le 2k+35$ holds, where $δ(G)$ is the minimum degree of $G$ . In this paper, we improve these upper bounds to $2.5k +2.5$ and $2k+8$ respectively. In particular, for any $k$ -crossing-critical graph $G$ with $n$ vertices, if $δ(G)\ge 5$ , then $cr(G)\le 2k-\sqrt k/2n+35/6$ holds.

preprint2020arXiv

On the sizes of bipartite 1-planar graphs

A graph is called $1$ -planar if it admits a drawing in the plane such that each edge is crossed at most once. Let $G$ be a bipartite 1-planar graph with $n$ ( $\ge 4$ ) vertices and $m$ edges. Karpov showed that $m\le 3n-8$ holds for even $n\ge 8$ and $m\le 3n-9$ holds for odd $n\ge 7$ . Czap, Przybylo and uSkrabuláková proved that if the partite sets of $G$ are of sizes $x$ and $y$ , then $m\le 2n+6x-12$ holds for $2\leq x\leq y$ , and conjectured that $m\le 2n+4x-12$ holds for $x\ge 3$ and $y\ge 6x-12$ . In this paper, we settle their conjecture and our result is even under a weaker condition $2\le x\le y$ .

preprint2020arXiv

Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations

The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum\limits_{i=1}^n(-1)^{n-i}a_{i}x^i$ , where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $ε(G)=\sum\limits_{i=1}^n (n-i)a_i/\sum\limits_{i=1}^n a_i$ is the mean size of a broken-cycle-free spanning subgraph of $G$ . In this article, we confirm and strengthen a conjecture proposed by Lundow and Markström in 2006 that $ε(T_n)< ε(G)<ε(K_n)$ holds for any connected graph $G$ of order $n$ which is neither the complete graph $K_n$ nor a tree $T_n$ of order $n$ . The most crucial step of our proof is to obtain the interpretation of all $a_i$ 's by the number of acyclic orientations of $G$ .

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.

Zhangdong Ouyang

Research overview

Is this your work?

4 publications

On the size of matchings in 1-planar graph with high minimum degree

New upper bounds for the crossing numbers of crossing-critical graphs

On the sizes of bipartite 1-planar graphs

Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations

See the researcher in context

Building this map preview