Source author record

Haixing Zhao

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

preprint2021arXiv

Uniformly most reliable three-terminal graph of dense graphs

A graph $G$ with $k$ specified target vertices in vertex set is a $k$ -terminal graph. The $k$ -terminal reliability is the connection probability of the fixed $k$ target vertices in a $k$ -terminal graph when every edge of this graph survives independently with probability $p$ . For the class of two-terminal graphs with a large number of edges, Betrand, Goff, Graves and Sun constructed a locally most reliable two-terminal graph for $p$ close to $1$ , and illustrated by a counterexample that this locally most reliable graph is not the uniformly most reliable two-terminal graph. At the same time, they also determined that there is a uniformly most reliable two-terminal graph in the class obtained by deleting an edge from the complete graph with two target vertices. This article focuses on the uniformly most reliable three-terminal graph of dense graphs with $n$ vertices and $m$ edges. First, we give the locally most reliable three-terminal graphs of $n$ and $m$ in certain ranges for $p$ close to $0$ and $1$ . Then, it is proved that there is no uniformly most reliable three-terminal graph with specific $n$ and $m$ , where $n\geq7$ and $\binom{n}{2}-\lfloor\frac{n-3}{2}\rfloor\leq m\leq\binom{n}{2}-2$ . Finally, some uniformly most reliable graphs are given for $n$ vertices and $m$ edges, where $4\leq n\leq 6$ and $m=\binom{n}{2}-2$ or $n\geq5$ and $m=\binom{n}{2}-1$ .

preprint2016arXiv

On the Equitable Vertex Arboricity of Graphs

The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu, Zhang and Li introduced the concept of equitable $(t,k)$ -tree-coloring, which can be regarded as a generalization of proper equitable $t$ -coloring. The \emph{strong equitable vertex $k$ -arboricity} of $G$ , denoted by ${va_k}^\equiv(G)$ , is the smallest integer $t$ such that $G$ has an equitable $(t', k)$ -tree-coloring for every $t'\geq t$ . The exact value of strong equitable vertex $k$ -arboricity of complete equipartition bipartite graph $K_{n,n}$ was studied by Wu, Zhang and Li. In this paper, we first get a sharp upper bound of strong equitable vertex arboricity of complete bipartite graph $K_{n,n+\ell} \ (1\leq \ell\leq n)$ , that is, ${va_2}^\equiv(K_{n,n+\ell})\leq2\left\lfloor{\frac{n+\ell+1}{3}}\right\rfloor$ . Next, we obtain a sufficient and necessary condition on an equitable $(q,\infty)$ -tree coloring of a complete equipartition tripartite graph, and study the strong equitable vertex arboricity of forests. For a simple graph $G$ of order $n$ , we show that $1\leq {va_k}^\equiv(G)\leq \lceil n/2 \rceil$ . Furthermore, graphs with ${va_k}^\equiv(G)=1,\lceil\frac{n}{2}\rceil,\lceil\frac{n}{2}\rceil-1$ are characterized, respectively. In the end, we obtain the Nordhaus-Gaddum type results of strong equitable vertex $k$ -arboricity for general $k$ .

preprint2015arXiv

On the equitable vertex arboricity of complete tripartite graphs

The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu et al. introduced the concept of equitable (t,k)-tree-coloring, which can be viewed as a generalization of proper equitable t-coloring. The strong equitable vertex k-arboricity of complete bipartite equipartition graphs was investigated in 2013. In this paper, we study the exact value of the strong equitable vertex 3-arboricity of complete equipartition tripartite graphs.

preprint2015arXiv

On the regular k-independence number of graphs

The \emph{regular independence number}, introduced by Albertson and Boutin in 1990, is the maximum cardinality of an independent set of $G$ in which all vertices have equal degree in $G$ . Recently, Caro, Hansberg and Pepper introduced the concept of regular $k$ -independence number, which is a natural generalization of the regular independence number. A \emph{ $k$ -independent set} is a set of vertices whose induced subgraph has maximum degree at most $k$ . The \emph{regular $k$ -independence number} of $G$ , denoted by $α_{k-reg}(G)$ , is defined as the maximum cardinality of a $k$ -independent set of $G$ in which all vertices have equal degree in $G$ . In this paper, the exact values of the regular $k$ -independence numbers of some special graphs are obtained. We also get some lower and upper bounds for the regular $k$ -independence number of trees with given diameter, and the lower bounds for the regular $k$ -independence number of line graphs. For a simple graph $G$ of order $n$ , we show that $1\leqα_{k-reg}(G)\leq n$ and characterize the extremal graphs. The Nordhaus-Gaddum-type results for the regular $k$ -independence number of graphs are also obtained.

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.