Source author record

Hongjian Lai

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

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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

Interval minors of complete multipartite graphs

Interval minors of bipartite graphs were introduced by Jacob Fox in the study of Stanley-Wilf limits. Recently, Mohar, Rafiey, Tayfeh-Rezaie and Wu investigated the maximum number of edges in $K_{k,\ell}$ -interval minor free bipartite graphs when $k=2$ and $k=3$ . In this paper, we investigate the maximum number of edges in $K_{k,\ell}$ -interval minor free bipartite graphs for general $k$ and $\ell$ . We also study the maximum number of edges in $K_{\ell_1,\ell_2,\cdots,\ell_t}$ -interval minor free multipartite 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.