Source author record

Sujuan Liu

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

6works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2012arXiv

A sharp upper bound for the rainbow 2-connection number of 2-connected graphs

A path in an edge-colored graph is called {\em rainbow} if no two edges of it are colored the same. For an $\ell$ -connected graph $G$ and an integer $k$ with $1\leq k\leq \ell$ , the {\em rainbow $k$ -connection number} $rc_k(G)$ of $G$ is defined to be the minimum number of colors required to color the edges of $G$ such that every two distinct vertices of $G$ are connected by at least $k$ internally disjoint rainbow paths. Fujita et. al. proposed a problem that what is the minimum constant $α>0$ such that for all 2-connected graphs $G$ on $n$ vertices, we have $rc_2(G)\leq αn$ . In this paper, we prove that $α=1$ and $rc_2(G)=n$ if and only if $G$ is a cycle of order $n$ , settling down this problem.

preprint2012arXiv

Rainbow connection number and the number of blocks

An edge-colored graph $G$ is rainbow connected if every pair of vertices of $G$ are connected by a path whose edges have distinct colors. The rainbow connection number $rc(G)$ of $G$ is defined to be the minimum integer $t$ such that there exists an edge-coloring of $G$ with $t$ colors that makes $G$ rainbow connected. For a graph $G$ without any cut vertex, i.e., a 2-connected graph, of order $n$ , it was proved that $rc(G)\leq \lceil\frac n 2 \rceil$ and the bound is tight. In this paper, we prove that for a connected graph $G$ of order $n$ with cut vertices, $rc(G) \leq\frac{n+r-1} 2$ , where $r$ is the number of blocks of $G$ with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound for a bridgeless graph, i.e., a 2-edge-connected graph.

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

Rainbow vertex-connection number of 2-connected graphs

The {\em rainbow vertex-connection number}, $rvc(G)$ , of a connected graph $G$ is the minimum number of colors needed to color its vertices such that every pair of vertices is connected by at least one path whose internal vertices have distinct colors. In this paper we first determine the rainbow vertex-connection number of cycle $C_n$ of order $n\geq 3$ , and then, based on it, prove that for any 2-connected graph $G$ , $rvc(G)\leq rvc(C_n)$ , giving a tight upper bound for the rainbow vertex-connection. As a consequence, we show that for a connected graph $G$ with a block decomposition $B_1, B_2, ..., B_k$ and $t$ cut vertices, $rvc(G)\leq rvc(B_1)+rvc(B_2)+ ... +rvc(B_k)+t$ .

preprint2011arXiv

Sharp upper bound for the rainbow connection numbers of 2-connected graphs

An edge-colored graph $G$ , where adjacent edges may be colored the same, is rainbow connected if any two vertices of $G$ are connected by a path whose edges have distinct colors. The rainbow connection number $rc(G)$ of a connected graph $G$ is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper, we give a sharp upper bound that $rc(G)\leq\lceil\frac{n}{2}\rceil$ for any 2-connected graph $G$ of order $n$ , which improves the results of Caro et al. to best possible.

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.

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.

Sujuan Liu

Research overview

Is this your work?

6 publications

A sharp upper bound for the rainbow 2-connection number of 2-connected graphs

Rainbow connection number and the number of blocks

Rainbow connection of graphs with diameter 2

Rainbow vertex-connection number of 2-connected graphs

Sharp upper bound for the rainbow connection numbers of 2-connected graphs

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

See the researcher in context

Building this map preview