Source author record

Zhongmei Qin

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

8works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On two conjectures about the proper connection number of graphs

A path in an edge-colored graph is called proper if no two consecutive edges of the path receive the same color. For a connected graph $G$ , the proper connection number $pc(G)$ of $G$ is defined as the minimum number of colors needed to color its edges so that every pair of distinct vertices of $G$ are connected by at least one proper path in $G$ . In this paper, we consider two conjectures on the proper connection number of graphs. The first conjecture states that if $G$ is a noncomplete graph with connectivity $κ(G) = 2$ and minimum degree $δ(G)\ge 3$ , then $pc(G) = 2$ , posed by Borozan et al.~in [Discrete Math. 312(2012), 2550-2560]. We give a family of counterexamples to disprove this conjecture. However, from a result of Thomassen it follows that 3-edge-connected noncomplete graphs have proper connection number 2. Using this result, we can prove that if $G$ is a 2-connected noncomplete graph with $diam(G)=3$ , then $pc(G) = 2$ , which solves the second conjecture we want to mention, posed by Li and Magnant in [Theory \& Appl. Graphs 0(1)(2015), Art.2].

preprint2016arXiv

Solution to a conjecture on the proper connection number of graphs

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path receive the same color. For a connected graph $G$ , the proper connection number $pc(G)$ of $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one proper path in $G$ . Recently, Li and Magnant in [Theory Appl. Graphs 0(1)(2015), Art.2] posed the following conjecture: If $G$ is a connected noncomplete graph of order $n \geq 5$ and minimum degree $δ(G) \geq n/4$ , then $pc(G)=2$ . In this paper, we show that this conjecture is true except for two small graphs on 7 and 8 vertices, respectively. As a byproduct we obtain that if $G$ is a connected bipartite graph of order $n\geq 4$ with $δ(G)\geq \frac{n+6}{8}$ , then $pc(G)=2$ .

preprint2016arXiv

Some upper bounds for the $3$ -proper index of graphs

A tree $T$ in an edge-colored graph is a {\it proper tree} if no two adjacent edges of $T$ receive the same color. Let $G$ be a connected graph of order $n$ and $k$ be a fixed integer with $2\le k\le n$ . For a vertex subset $S \subseteq V(G)$ with $\left|S\right| \ge 2$ , a tree containing all the vertices of $S$ in $G$ is called an $S$ -tree. An edge-coloring of $G$ is called a \emph{ $k$ -proper coloring} if for every $k$ -subset $S$ of $V(G)$ , there exists a proper $S$ -tree in $G$ . For a connected graph $G$ , the \emph{ $k$ -proper index} of $G$ , denoted by $px_k(G)$ , is the smallest number of colors that are needed in a $k$ -proper coloring of $G$ . In this paper, we show that for every connected graph $G$ of order $n$ and minimum degree $δ\geq 3$ , $px_{3}(G)\le n\frac{\ln(δ+1)}{δ+1}(1+o_δ(1))+2$ . We also prove that for every connected graph $G$ with minimum degree at least $3$ , $px_{3}(G) \le px_{3}(G[D])+3$ when $D$ is a connected $3$ -way dominating set of $G$ and $px_{3}(G) \le px_{3}(G[D])+1$ when $D$ is a connected $3$ -dominating set of $G$ . In addition, we obtain tight upper bounds of the 3-proper index for two special graph classes: threshold graphs and chain graphs. Finally, we prove that $px_3(G) \le \lfloor\frac{n}{2}\rfloor$ for any 2-connected graphs with at least four vertices.

preprint2016arXiv

The $(k,\ell)$ -proper index of graphs

A tree $T$ in an edge-colored graph is called a {\it proper tree} if no two adjacent edges of $T$ receive the same color. Let $G$ be a connected graph of order $n$ and $k$ be an integer with $2\leq k \leq n$ . For $S\subseteq V(G)$ and $|S| \ge 2$ , an $S$ -tree is a tree containing the vertices of $S$ in $G$ . Suppose $\{T_1,T_2,\ldots,T_\ell\}$ is a set of $S$ -trees, they are called \emph{internally disjoint} if $E(T_i)\cap E(T_j)=\emptyset$ and $V(T_i)\cap V(T_j)=S$ for $1\leq i\neq j\leq \ell$ . For a set $S$ of $k$ vertices of $G$ , the maximum number of internally disjoint $S$ -trees in $G$ is denoted by $κ(S)$ . The $κ$ -connectivity $κ_k(G)$ of $G$ is defined by $κ_k(G)=\min\{κ(S)\mid S$ is a $k$ -subset of $V(G)\}$ . For a connected graph $G$ of order $n$ and for two integers $k$ and $\ell$ with $2\le k\le n$ and $1\leq \ell \leq κ_k(G)$ , the \emph{ $(k,\ell)$ -proper index $px_{k,\ell}(G)$ } of $G$ is the minimum number of colors that are needed in an edge-coloring of $G$ such that for every $k$ -subset $S$ of $V(G)$ , there exist $\ell$ internally disjoint proper $S$ -trees connecting them. In this paper, we show that for every pair of positive integers $k$ and $\ell$ with $k \ge 3$ , there exists a positive integer $N_1=N_1(k,\ell)$ such that $px_{k,\ell}(K_n) = 2$ for every integer $n \ge N_1$ , and also there exists a positive integer $N_2=N_2(k,\ell)$ such that $px_{k,\ell}(K_{m,n}) = 2$ for every integer $n \ge N_2$ and $m=O(n^r) (r \ge 1)$ . In addition, we show that for every $p \ge c\sqrt[k]{\frac{\log_a n}{n}}$ ( $c \ge 5$ ), $px_{k,\ell}(G_{n,p})\le 2$ holds almost surely, where $G_{n,p}$ is the Erdös-Rényi random graph model.

preprint2015arXiv

Proper connection number of random graphs

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored the same. For a connected graph $G$ , the proper connection number $pc(G)$ of $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one proper path in $G$ . In this paper, we show that almost all graphs have the proper connection number 2. More precisely, let $G(n,p)$ denote the Erdös-Rényi random graph model, in which each of the $\binom{n}{2}$ pairs of vertices appears as an edge with probability $p$ independent from other pairs. We prove that for sufficiently large $n$ , $pc(G(n,p))\le2$ if $p\ge\frac{\log n +α(n)}{n}$ , where $α(n)\rightarrow \infty$ .

preprint2014arXiv

An extension of Mantel's theorem to random 4-uniform hypergraphs

A sparse version of Mantel's Theorem is that, for sufficiently large $p$ , with high probability (w.h.p.), every maximum triangle-free subgraph of $G(n,p)$ is bipartite. DeMarco and Kahn proved this for $p>K \sqrt{\log n/n}$ for some constant $K$ , and apart from the value of the constant, this bound is the best possible. Denote by $T_3$ the 3-uniform hypergraph with vertex set $\{a,b,c,d,e\}$ and edge set $\{abc,ade,bde\}$ . Frankl and Füredi showed that the maximum 3-uniform hypergraph on $n$ vertices containing no copy of $T_3$ is tripartite for $n> 3000$ . For some integer $k$ , let $G^k(n,p)$ be the random $k$ -uniform hypergraph. Balogh et al. proved that for $p>K \log n/n$ for some constant $K$ , every maximum $T_3$ -free subhypergraph of $G^3(n,p)$ w.h.p. is tripartite and it does not hold when $p=0.1 \sqrt{\log n}/n$ . Denote by $T_4$ the 4-uniform hypergraph with vertex set $\{1,2,3,4,5,6,7\}$ and edge set $\{1234,1235,4567\}$ . Pikhurko proved that there is an $n_0$ such that for all $n\ge n_0$ , the maximum 4-uniform hypergraph on $n$ vertices containing no copy of $T_4$ is 4-partite. In this paper, we extend this type of extremal problem in random 4-uniform hypergraphs. We show that for some constant $K$ and $p>K \log n/n$ , w.h.p. every maximum $T_4$ -free subhypergraph of $G^4(n,p)$ is 4-partite.

preprint2014arXiv

Colorful monochromatic connectivity of random graphs

An edge-coloring of a connected graph $G$ is called a {\it monochromatic connection coloring} (MC-coloring, for short), introduced by Caro and Yuster, if there is a monochromatic path joining any two vertices of the graph $G$ . Let $mc(G)$ denote the maximum number of colors used in an MC-coloring of a graph $G$ . Note that an MC-coloring does not exist if $G$ is not connected, and in this case we simply let $mc(G)=0$ . We use $G(n,p)$ to denote the Erdös-Rényi random graph model, in which each of the $\binom{n}{2}$ pairs of vertices appears as an edge with probability $p$ independently from other pairs. For any function $f(n)$ satisfying $1\leq f(n)<\frac{1}{2}n(n-1)$ , we show that if $\ell n \log n\leq f(n)<\frac{1}{2}n(n-1)$ where $\ell\in \mathbb{R}^+$ , then $p=\frac{f(n)+n\log\log n}{n^2}$ is a sharp threshold function for the property $mc\left(G\left(n,p\right)\right)\ge f(n)$ ; if $f(n)=o(n\log n)$ , then $p=\frac{\log n}{n}$ is a sharp threshold function for the property $mc\left(G\left(n,p\right)\right)\ge f(n)$ .

preprint2014arXiv

Novel Inequalities for Generalized Graph Entropies Revisited, Graph Energies and Topological Indices

The entropy of a graph is an information-theoretic quantity which expresses the complexity of a graph \cite{DM1,M}. After Shannon introduced the definition of entropy to information and communication, many generalizations of the entropy measure have been proposed, such as Rényi entropy and Daròczy's entropy. In this article, we prove accurate connections (inequalities) between generalized graph entropies, distinct graph energies and topological indices. Additionally, we obtain some extremal properties of nine generalized graph entropies by employing distinct graph energies and topological indices.

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.

Zhongmei Qin

Research overview

Is this your work?

8 publications

On two conjectures about the proper connection number of graphs

Solution to a conjecture on the proper connection number of graphs

Some upper bounds for the $3$ -proper index of graphs

The $(k,\ell)$ -proper index of graphs

Proper connection number of random graphs

An extension of Mantel's theorem to random 4-uniform hypergraphs

Colorful monochromatic connectivity of random graphs

Novel Inequalities for Generalized Graph Entropies Revisited, Graph Energies and Topological Indices

See the researcher in context

Building this map preview

Zhongmei Qin

Research overview

Is this your work?

8 publications

On two conjectures about the proper connection number of graphs

Solution to a conjecture on the proper connection number of graphs

Some upper bounds for the 333-proper index of graphs

The (k,ℓ)(k,\ell)(k,ℓ)-proper index of graphs

Proper connection number of random graphs

An extension of Mantel's theorem to random 4-uniform hypergraphs

Colorful monochromatic connectivity of random graphs

Novel Inequalities for Generalized Graph Entropies Revisited, Graph Energies and Topological Indices

See the researcher in context

Building this map preview

Some upper bounds for the $3$ -proper index of graphs

The $(k,\ell)$ -proper index of graphs