BZPEER

preprint2022arXiv

Counting spanning trees in a complete bipartite graph which contain a given spanning forest

In this article, we extend Moon's classic formula for counting spanning trees in complete graphs containing a fixed spanning forest to complete bipartite graphs. Let $(X,Y)$ be the bipartition of the complete bipartite graph $K_{m,n}$ with $|X|=m$ and $|Y|=n$ . We prove that for any given spanning forest $F$ of $K_{m,n}$ with components $T_1,T_2,\ldots,T_k$ , the number of spanning trees in $K_{m,n}$ which contain all edges in $F$ is equal to $\frac 1{mn}\left(\prod_{i=1}^k (m_in+n_im)\right) \left (1-\sum_{i=1}^{k}\frac{m_in_i}{m_in+n_im}\right ),$ where $m_i=|V(T_i)\cap X|$ and $n_i=|V(T_i)\cap Y|$ for $i=1,2,\ldots,k$ .

preprint2022arXiv

DP color functions versus chromatic polynomials (II)

For any connected graph $G$ , let $P(G,m)$ and $P_{DP}(G,m)$ denote the chromatic polynomial and DP color function of $G$ , respectively. It is known that $P_{DP}(G,m)\le P(G,m)$ holds for every positive integer $m$ . Let $DP_\approx$ (resp. $DP_<$ ) be the set of graphs $G$ for which there exists an integer $M$ such that $P_{DP}(G,m)=P(G,m)$ (resp. $P_{DP}(G,m)<P(G,m)$ ) holds for all integers $m \ge M$ . Determining the sets $DP_\approx$ and $DP_<$ is a key problem on the study of the DP color function. For any edge set $E_0$ of $G$ , let $\ell_G(E_0)$ be the length of a shortest cycle $C$ in $G$ such that $|E(C)\cap E_0|$ is odd whenever such a cycle exists, and $\ell_G(E_0)=\infty$ otherwise. Write $\ell_G(E_0)$ as $\ell_G(e)$ if $E_0=\{e\}$ . In this paper, we prove that if $G$ has a spanning tree $T$ such that $\ell_G(e)$ is odd for each $e\in E(G)\setminus E(T)$ , the edges in $E(G)\setminus E(T)$ can be labeled as $e_1,e_2,\cdots, e_q$ with $\ell_G(e_i)\le \ell_G(e_{i+1})$ for all $1\le i\le q-1$ and each edge $e_i$ is contained in a cycle $C_i$ of length $\ell_G(e_i)$ with $E(C_i)\subseteq E(T)\cup \{e_j: 1\le j\le i\}$ , then $G$ is a graph in $DP_{\approx}$ . As a direct application of this conclusion, all plane near-triangulations and complete multipartite graphs with at least three partite sets belong to $DP_{\approx}$ . We also show that if $E^*$ is an edge set of $G$ such that $\ell_{G}(E^*)$ is even and $E^*$ satisfies certain conditions, then $G$ belongs to $DP_<$ . In particular, if $\ell_G(E^*)=4$ , where $E^*$ is a set of edges between two disjoint vertex subsets of $G$ , then $G$ belongs to $DP_<$ . Both results extend known ones in [DP color functions versus chromatic polynomials, $Advances\ in\ Applied\ Mathematics$ 134 (2022), article 102301].

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

A survey on the study of real zeros of flow polynomials

For a bridgeless graph $G$ , its flow polynomial is defined to be the function $F(G,q)$ which counts the number of nonwhere-zero $Γ$ -flows on an orientation of $G$ whenever $q$ is a positive integer and $Γ$ is an additive Abelian group of order $q$ . It was introduced by Tutte in 1950 and the locations of zeros of this polynomial have been studied by many researchers. This article gives a survey on the results and problems on the study of real zeros of flow polynomials.

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

Polynomials related to chromatic polynomials

For a simple graph $G$ , let $χ(G,x)$ denote the chromatic polynomial of $G$ . This manuscript introduces some polynomials which are related to chromatic polynomial and their relations.

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$ .

preprint2020arXiv

The rank of a complex unit gain graph in terms of the matching number

A complex unit gain graph (or ${\mathbb T}$ -gain graph) is a triple $Φ=(G, {\mathbb T}, φ)$ (or $(G, φ)$ for short) consisting of a simple graph $G$ , as the underlying graph of $(G, φ)$ , the set of unit complex numbers $\mathbb{T}= \{ z \in C:|z|=1 \}$ and a gain function $φ: \overrightarrow{E} \rightarrow \mathbb{T}$ with the property that $φ(e_{i,j})=φ(e_{j,i})^{-1}$ . In this paper, we prove that $2m(G)-2c(G) \leq r(G, φ) \leq 2m(G)+c(G)$ , where $r(G, φ)$ , $m(G)$ and $c(G)$ are the rank of the Hermitian adjacency matrix $H(G, φ)$ , the matching number and the cyclomatic number of $G$ , respectively. Furthermore, the complex unit gain graphs $(G, \mathbb{T}, φ)$ with $r(G, φ)=2m(G)-2c(G)$ and $r(G, φ)=2m(G)+c(G)$ are characterized. These results generalize the corresponding known results about undirected graphs, mixed graphs and signed graphs. Moreover, we show that $2m(G-V_{0}) \leq r(G, φ) \leq 2m(G)+b(G)$ holds for any subset $V_0$ of $V(G)$ such that $G-V_0$ is acyclic and $b(G)$ is the minimum integer $|S|$ such that $G-S$ is bipartite for $S \subset V(G)$ .

preprint2020arXiv

Zero-free intervals of chromatic polynomials of mixed hypergraphs

In this paper, we prove that $(-\infty, 0)$ is a zero-free interval for chromatic polynomials of a family ${\cal L}_0$ of hypergraphs and $(0, 1)$ is a zero-free interval for chromatic polynomials of a subfamily ${\cal L}_0'$ of ${\cal L}_0$ of hypergraphs. These results extend known results on zero-free intervals of chromatic polynomials of graphs and hypergraphs.

preprint2019arXiv

Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs

Using the theory of electrical network, we first obtain a simple formula for the number of spanning trees of a complete bipartite graph containing a certain matching or a certain tree. Then we apply the effective resistance (i.e., resistance distance in graphs) to find a formula for the number of spanning trees in the nearly complete bipartite graph $G(m,n,p)=K_{m,n}-pK_2$ $(p\leq \min\{m,n\})$ , which extends a recent result by Ye and Yan who obtained the effective resistances and the number of spanning trees in $G(n,n,p)$ . As a corollary, we obtain the Kirchhoff index of $G(m,n,p)$ which extends a previous result by Shi and Chen.

preprint2018arXiv

On non-feasible edge sets in matching-covered graphs

Let $G=(V,E)$ be a matching-covered graph and $X$ be an edge set of $G$ . $X$ is said to be feasible if there exist two perfect matchings $M_1$ and $M_2$ in $G$ such that $|M_1\cap X|\not \equiv|M_2\cap X|\ (\mbox{mod } 2)$. For any $V_0\subseteq V$ , $X$ is said to be switching-equivalent to $X\oplus \nabla_G(V_0)$ , where $\nabla_G(V_0)$ is the set of edges in $G$ each of which has exactly one end in $V_0$ and $A \oplus B$ is the symmetric difference of two sets $A$ and $B$ . Lukot'ka and Rollová showed that when $G$ is regular and bipartite, $X$ is non-feasible if and only if $X$ is switching-equivalent to $\emptyset$ . This article extends Lukot'ka and Rollová's result by showing that this conclusion holds as long as $G$ is matching-covered and bipartite. This article also studies matching-covered graphs $G$ whose non-feasible edge sets are switching-equivalent to $\emptyset$ or $E$ and partially characterizes these matching-covered graphs in terms of their ear decompositions. Another aim of this article is to construct infinite many $r$ -connected and $r$ -regular graphs of class 1 containing non-feasible edge sets not switching-equivalent to either $\emptyset$ or $E$ for an arbitrary integer $r$ with $r\ge 3$ , which provides negative answers to problems asked by Lukot'ka and Rollová and He, et al respectively.

preprint2014arXiv

On Zero-free Intervals of Flow Polynomials

This article studies real roots of the flow polynomial $F(G,λ)$ of a bridgeless graph $G$ . For any integer $k\ge 0$ , let $ξ_k$ be the supremum in $(1,2]$ such that $F(G,λ)$ has no real roots in $(1,ξ_k)$ for all graphs $G$ with $|W(G)|\le k$ , where $W(G)$ is the set of vertices in $G$ of degrees larger than $3$ . We prove that $ξ_k$ can be determined by considering a finite set of graphs and show that $ξ_k=2$ for $k\le 2$ , $ξ_3=1.430\cdots$ , $ξ_4=1.361\cdots$ and $ξ_5=1.317\cdots$ . We also prove that for any bridgeless graph $G=(V,E)$ , if all roots of $F(G,λ)$ are real but some of these roots are not in the set $\{1,2,3\}$ , then $|E|\ge |V|+17$ and $F(G,λ)$ has at least 9 real roots in $(1,2)$ .

Fengming Dong

Research overview

Is this your work?

13 publications

Counting spanning trees in a complete bipartite graph which contain a given spanning forest

DP color functions versus chromatic polynomials (II)

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

A survey on the study of real zeros of flow polynomials

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

On the sizes of bipartite 1-planar graphs

Polynomials related to chromatic polynomials

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

The rank of a complex unit gain graph in terms of the matching number

Zero-free intervals of chromatic polynomials of mixed hypergraphs

Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs

On non-feasible edge sets in matching-covered graphs

On Zero-free Intervals of Flow Polynomials

See the researcher in context

Building this map preview