BZPEER

preprint2016arXiv

Algorithm on rainbow connection for maximal outerplanar graphs

In this paper, we consider rainbow connection number of maximal outerplanar graphs(MOPs) on algorithmic aspect. For the (MOP) $G$ , we give sufficient conditions to guarantee that $rc(G) = diam(G).$ Moreover, we produce the graph with given diameter $d$ and give their rainbow coloring in linear time. X.Deng et al. $\cite{XD}$ give a polynomial time algorithm to compute the rainbow connection number of MOPs by the Maximal fan partition method, but only obtain a compact upper bound. J. Lauri $\cite{JL}$ proved that, for chordal outerplanar graphs given an edge-coloring, to verify whether it is rainbow connected is NP-complete under the coloring, it is so for MOPs. Therefore we construct Central-cut-spine of MOP $G,$ by which we design an algorithm to give a rainbow edge coloring with at most $2rad(G)+2+c,0\leq c\leq rad(G)-2$ colors in polynomial time.

preprint2013arXiv

Lower bounds for the spanning tree numbers of two graph products

For any graph $G$ of order $n$ , the spanning tree packing number \emph{ $STP(G)$ }, is the maximum number of edge-disjoint spanning trees contained in $G$ . In this paper, we obtain some sharp lower bounds for the spanning tree numbers of Cartesian product graphs and Lexicographic product graphs.

preprint2013arXiv

On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

The problem of determining the smallest number of edges, $h(n;\barκ\geq r)$ , which guarantees that any graph with $n$ vertices and $h(n;\barκ\geq r)$ edges will contain a pair of vertices joined by $r$ internally disjoint paths was posed by Erdös and Gallai. Bollobás considered the problem of determining the largest number of edges $f(n;\barκ\leq \ell)$ for graphs with $n$ vertices and local connectivity at most $\ell$ . One can see that $f(n;\barκ\leq \ell)= h(n;\barκ\geq \ell+1)-1$ . These two problems had received a wide attention of many researchers in the last few decades. In the above problems, only pairs of vertices connected by internally disjoint paths are considered. In this paper, we study the number of internally disjoint Steiner trees connecting sets of vertices with cardinality at least 3.

preprint2012arXiv

Graphs with large generalized 3-connectivity

Let $S$ be a nonempty set of vertices of a connected graph $G$ . A collection $T_1,..., T_\ell$ of trees in $G$ is said to be internally disjoint trees connecting $S$ if $E(T_i)\cap E(T_j)= \emptyset$ and $V(T_i)\cap V(T_j)=S$ for any pair of distinct integers $i, j$ , where $1 \leq i, j \leq r$ . For an integer $k$ with $2 \leq k \leq n$ , the generalized $k$ -connectivity $κ_k(G)$ of $G$ is the greatest positive integer $r$ such that $G$ contains at least $r$ internally disjoint trees connecting $S$ for any set $S$ of $k$ vertices of $G$ . Obviously, $κ_2(G)$ is the connectivity of $G$ . In this paper, sharp upper and lower bounds of $κ_3(G)$ are given for a connected graph $G$ of order $n$ , that is, $1 \leq κ_3(G) \leq n - 2$ . Graphs of order $n$ such that $κ_3(G) = n - 2, n - 3$ are characterized, respectively.

preprint2012arXiv

Note on minimally $k$ -rainbow connected graphs

An edge-colored graph $G$ , where adjacent edges may have the same color, is {\it rainbow connected} if every two vertices of $G$ are connected by a path whose edge has distinct colors. A graph $G$ is {\it $k$ -rainbow connected} if one can use $k$ colors to make $G$ rainbow connected. For integers $n$ and $d$ let $t(n,d)$ denote the minimum size (number of edges) in $k$ -rainbow connected graphs of order $n$ . Schiermeyer got some exact values and upper bounds for $t(n,d)$ . However, he did not get a lower bound of $t(n,d)$ for $3\leq d<\lceil\frac{n}{2}\rceil$ . In this paper, we improve his lower bound of $t(n,2)$ , and get a lower bound of $t(n,d)$ for $3\leq d<\lceil\frac{n}{2}\rceil$ .

preprint2011arXiv

Asymptotic value of the minimal size of a graph with rainbow connection number 2

A path in an edge (vertex)-colored graph $G$ , where adjacent edges (vertices) may have the same color, is called a rainbow path if no pair of edges (internal vertices) of the path are colored the same. The rainbow (vertex) connection number $rc(G)$ ( $rvc(G)$ ) of $G$ is the minimum integer $i$ for which there exists an $i$ -edge (vertex)-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. Denote by $\mathcal{G}_d(n)$ ( $\mathcal{G'}_d(n)$ ) the set of all graphs of order $n$ with rainbow (vertex) connection number $d$ , and define $e_d(n)=\min\{e(G)\,|\, G\in \mathcal{G}_d(n)\}$ ( $e_d'(n)=\min\{e(G)\,|\, G\in \mathcal{G'}_d(n)\}$ ), where $e(G)$ denotes the number of edges in $G$ . In this paper, we investigate the bounds of $e_2(n)$ and get the exact asymptotic value. i.e., $\displaystyle \lim_{n\rightarrow \infty}\frac{e_2(n)}{n\log_2 n}=1$ . Meanwhile, we obtain $e'_d(n)=n-1$ for $d\geq 2$ , and the equality holds if and only if $G$ is such a graph such that deleting all leaves of $G$ results in a tree of order $d$ .

preprint2011arXiv

Note on the oriented diameter of graphs with diameter 3

In 1978, Chvátal and Thomassen showed that every bridgeless graph with diameter 2 has an orientation with diameter at most 6. They also gave general bounds on the smallest value $f(d)$ such that every bridgeless graph $G$ with diameter $d$ has an orientation with diameter at most $f(d)$ . For $d=3$ , they proved that $8\leq f(d)\leq 24$ . Until recently, Kwok, Liu and West improved the above bounds by proving $9\leq f(3)\leq 11$ in [P.K. Kwok, Q. Liu and D.B. West, Oriented diameter of graphs with diameter 3, J. Combin. Theory Ser.B 100(2010), 265-274]. In this paper, we determine the oriented diameter among the bridgeless graphs with diameter 3 that have minimum number of edges.

preprint2011arXiv

Oriented diameter and rainbow connection number of a graph

The oriented diameter of a bridgeless graph $G$ is $\min\{diam(H)\ | H\ is\ an orientation\ of\ G\}$ . A path in an edge-colored graph $G$ , where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the smallest integer $k$ for which there exists a $k$ -edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. In this paper, we obtain upper bounds for the oriented diameter and the rainbow connection number of a graph in terms of $rad(G)$ and $η(G)$ , where $rad(G)$ is the radius of $G$ and $η(G)$ is the smallest integer number such that every edge of $G$ is contained in a cycle of length at most $η(G)$ . We also obtain constant bounds of the oriented diameter and the rainbow connection number for a (bipartite) graph $G$ in terms of the minimum degree of $G$ .

preprint2011arXiv

Rainbow connection of graphs with diameter 2

A path in an edge-colored graph $G$ , where adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the minimum integer $i$ for which there exists an $i$ -edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. It is known that for a graph $G$ with diameter 2, to determine $rc(G)$ is NP-hard. So, it is interesting to know the best upper bound of $rc(G)$ for such a graph $G$ . In this paper, we show that $rc(G)\leq 5$ if $G$ is a bridgeless graph with diameter 2, and that $rc(G)\leq k+2$ if $G$ is a connected graph of diameter 2 with $k$ bridges, where $k\geq 1$ .

preprint2011arXiv

The generalized 3-connectivity of Cartesian product graphs

The generalized connectivity of a graph, which was introduced recently by Chartrand et al., is a generalization of the concept of vertex connectivity. Let $S$ be a nonempty set of vertices of $G$ , a collection $\{T_1,T_2,...,T_r\}$ of trees in $G$ is said to be internally disjoint trees connecting $S$ if $E(T_i)\cap E(T_j)=\emptyset$ and $V(T_i)\cap V(T_j)=S$ for any pair of distinct integers $i,j$ , where $1\leq i,j\leq r$ . For an integer $k$ with $2\leq k\leq n$ , the $k$ -connectivity $κ_k(G)$ of $G$ is the greatest positive integer $r$ for which $G$ contains at least $r$ internally disjoint trees connecting $S$ for any set $S$ of $k$ vertices of $G$ . Obviously, $κ_2(G)=κ(G)$ is the connectivity of $G$ . Sabidussi showed that $κ(G\Box H) \geq κ(G)+κ(H)$ for any two connected graphs $G$ and $H$ . In this paper, we first study the 3-connectivity of the Cartesian product of a graph $G$ and a tree $T$ , and show that $(i)$ if $κ_3(G)=κ(G)\geq 1$ , then $κ_3(G\Box T)\geq κ_3(G)$ ; $(ii)$ if $1\leq κ_3(G)< κ(G)$ , then $κ_3(G\Box T)\geq κ_3(G)+1$ . Furthermore, for any two connected graphs $G$ and $H$ with $κ_3(G)\geqκ_3(H)$ , if $κ(G)>κ_3(G)$ , then $κ_3(G\Box H)\geq κ_3(G)+κ_3(H)$ ; if $κ(G)=κ_3(G)$ , then $κ_3(G\Box H)\geq κ_3(G)+κ_3(H)-1$ . Our result could be seen as a generalization of Sabidussi's result. Moreover, all the bounds are sharp.

preprint2011arXiv

Upper bound for the rainbow connection number of bridgeless graphs with diameter 3

A path in an edge-colored graph $G$ , where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the smallest integer $k$ for which there exists a $k$ -edge-coloring of $G$ such that every pair of distinct vertices of $G$ is connected by a rainbow path. It is known that for every integer $k\geq 2$ deciding if a graph $G$ has $rc(G)\leq k$ is NP-Hard, and a graph $G$ with $rc(G)\leq k$ has diameter $diam(G)\leq k$ . In foregoing papers, we showed that a bridgeless graph with diameter 2 has rainbow connection number at most 5. In this paper, we prove that a bridgeless graph with diameter 3 has rainbow connection number at most 9. We also prove that for any bridgeless graph $G$ with radius $r$ , if every edge of $G$ is contained in a triangle, then $rc(G)\leq 3r$ . As an application, we get that for any graph $G$ with minimum degree at least 3, $rc(L(G))\leq 3 rad(L(G))\leq 3 (rad(G)+1)$ .

preprint2010arXiv

The (strong) rainbow connection numbers of Cayley graphs of Abelian groups

A path in an edge-colored graph $G$ , where adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the minimum integer $i$ for which there exists an $i$ -edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. The strong rainbow connection number $src(G)$ of $G$ is the minimum integer $i$ for which there exists an $i$ -edge-coloring of $G$ such that every two distinct vertices $u$ and $v$ of $G$ are connected by a rainbow path of length $d(u,v)$ . In this paper, we give upper and lower bounds of the (strong) rainbow connection Cayley graphs of Abelian groups. Moreover, we determine the (strong) rainbow connection numbers of some special cases.

Hengzhe Li

Research overview

Is this your work?

12 publications

Algorithm on rainbow connection for maximal outerplanar graphs

Lower bounds for the spanning tree numbers of two graph products

On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

Graphs with large generalized 3-connectivity

Note on minimally $k$ -rainbow connected graphs

Asymptotic value of the minimal size of a graph with rainbow connection number 2

Note on the oriented diameter of graphs with diameter 3

Oriented diameter and rainbow connection number of a graph

Rainbow connection of graphs with diameter 2

The generalized 3-connectivity of Cartesian product graphs

Upper bound for the rainbow connection number of bridgeless graphs with diameter 3

The (strong) rainbow connection numbers of Cayley graphs of Abelian groups

See the researcher in context

Building this map preview

Hengzhe Li

Research overview

Is this your work?

12 publications

Algorithm on rainbow connection for maximal outerplanar graphs

Lower bounds for the spanning tree numbers of two graph products

On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

Graphs with large generalized 3-connectivity

Note on minimally kkk-rainbow connected graphs

Asymptotic value of the minimal size of a graph with rainbow connection number 2

Note on the oriented diameter of graphs with diameter 3

Oriented diameter and rainbow connection number of a graph

Rainbow connection of graphs with diameter 2

The generalized 3-connectivity of Cartesian product graphs

Upper bound for the rainbow connection number of bridgeless graphs with diameter 3

The (strong) rainbow connection numbers of Cayley graphs of Abelian groups

See the researcher in context

Building this map preview

Note on minimally $k$ -rainbow connected graphs