BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Zhongmei Qin

Zhongmei Qin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CO

Catalog footprint

What is connected

8works
1topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

8 published item(s)

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

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access