Source author record

Lily Chen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

10works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Further hardness results on the generalized connectivity of graphs

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984, which is a nice generalization of the classical connectivity. Recently, as a natural counterpart, Li et al. proposed the concept of generalized edge-connectivity for a graph. In this paper, we determine the computational complexity of the generalized connectivity and generalized edge-connectivity of a graph. Two conjectures are also proved to be true.

preprint2013arXiv

The 3-rainbow index of a graph

Let $G$ be a nontrivial connected graph with an edge-coloring $c: E(G)\rightarrow \{1,2,...,q\},$ $q \in \mathbb{N}$ , where adjacent edges may be colored the same. A tree $T$ in $G$ is a $rainbow tree$ if no two edges of $T$ receive the same color. For a vertex subset $S\subseteq V(G)$ , a tree that connects $S$ in $G$ is called an $S$ -tree. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow $S$ -tree for each $k$ -subset $S$ of $V(G)$ is called $k$ -rainbow index, denoted by $rx_k(G)$ . In this paper, we first determine the graphs whose 3-rainbow index equals 2, $m,$ $m-1$ , $m-2$ , respectively. We also obtain the exact values of $rx_3(G)$ for regular complete bipartite and multipartite graphs and wheel graphs. Finally, we give a sharp upper bound for $rx_3(G)$ of 2-connected graphs and 2-edge connected graphs, and graphs whose $rx_3(G)$ attains the upper bound are characterized.

preprint2013arXiv

Tricyclic graphs with maximal revised Szeged index

The revised Szeged index of a graph $G$ is defined as $Sz^*(G)=\sum_{e=uv \in E}(n_u(e)+ n_0(e)/2)(n_v(e)+ n_0(e)/2),$ where $n_u(e)$ and $n_v(e)$ are, respectively, the number of vertices of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of vertices of $G$ lying closer to vertex $v$ than to vertex $u$ , and $n_0(e)$ is the number of vertices equidistant to $u$ and $v$ . In this paper, we give an upper bound of the revised Szeged index for a connected tricyclic graph, and also characterize those graphs that achieve the upper bound.

preprint2012arXiv

A quantum algorithm for solving the 3-SAT problem

The method in this paper is wrong.

preprint2012arXiv

On a relation between the Szeged index and the Wiener index for bipartite graphs

{\small The Wiener index $W(G)$ of a graph $G$ is the sum of the distances between all pairs of vertices in the graph. The Szeged index $Sz(G)$ of a graph $G$ is defined as $Sz(G)=\sum_{e=uv \in E}n_u(e)n_v(e)$ where $n_u(e)$ and $n_v(e)$ are, respectively, the number of vertices of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of vertices of $G$ lying closer to vertex $v$ than to vertex $u$ . Hansen used the computer programm AutoGraphiX and made the following conjecture about the Szeged index and the Wiener index for a bipartite connected graph $G$ with $n \geq 4$ vertices and $m \geq n$ edges: $Sz(G)-W(G) \geq 4n-8.$ Moreover the bound is best possible as shown by the graph composed of a cycle on 4 vertices $C_4$ and a tree $T$ on $n-3$ vertices sharing a single vertex. This paper is to give a confirmative proof to this conjecture.

preprint2012arXiv

The (revised) Szeged index and the Wiener index of a nonbipartite graph

Hansen et. al. used the computer programm AutoGraphiX to study the differences between the Szeged index $Sz(G)$ and the Wiener index $W(G)$ , and between the revised Szeged index $Sz^*(G)$ and the Wiener index for a connected graph $G$ . They conjectured that for a connected nonbipartite graph $G$ with $n \geq 5$ vertices and girth $g \geq 5,$ $Sz(G)-W(G) \geq 2n-5.$ Moreover, the bound is best possible as shown by the graph composed of a cycle on 5 vertices, $C_5$ , and a tree $T$ on $n-4$ vertices sharing a single vertex. They also conjectured that for a connected nonbipartite graph $G$ with $n \geq 4$ vertices, $Sz^*(G)-W(G) \geq \frac{n^2+4n-6}{4}.$ Moreover, the bound is best possible as shown by the graph composed of a cycle on 3 vertices, $C_3$ , and a tree $T$ on $n-3$ vertices sharing a single vertex. In this paper, we not only give confirmative proofs to these two conjectures but also characterize those graphs that achieve the two lower bounds.

preprint2011arXiv

Further hardness results on the rainbow vertex-connection number of graphs

A vertex-colored graph $G$ is {\it rainbow vertex-connected} if any pair of vertices in $G$ are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The {\it rainbow vertex-connection number} of a connected graph $G$ , denoted by $rvc(G)$ , is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. In a previous paper we showed that it is NP-Complete to decide whether a given graph $G$ has $rvc(G)=2$ . In this paper we show that for every integer $k\geq 2$ , deciding whether $rvc(G)\leq k$ is NP-Hard. We also show that for any fixed integer $k\geq 2$ , this problem belongs to NP-class, and so it becomes NP-Complete.

preprint2011arXiv

Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph

A vertex-colored graph $G$ is rainbow vertex-connected if any pair of distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of $G$ , denoted by $rvc(G)$ , is the minimum number of colors that are needed to make $G$ rainbow vertex-connected. In this paper we give a Nordhaus-Gaddum-type result of the rainbow vertex-connection number. We prove that when $G$ and $\bar{G}$ are both connected, then $2\leq rvc(G)+rvc(\bar{G})\leq n-1$ . Examples are given to show that both the upper bound and the lower bound are best possible for all $n\geq 5$ .

preprint2011arXiv

The complexity of determining the rainbow vertex-connection of graphs

A vertex-colored graph is {\it rainbow vertex-connected} if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The {\it rainbow vertex-connection} of a connected graph $G$ , denoted by $rvc(G)$ , is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. In this paper, we study the computational complexity of vertex-rainbow connection of graphs and prove that computing $rvc(G)$ is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether $rvc(G)=2$ . We also prove that the following problem is NP-Complete: given a vertex-colored graph $G$ , check whether the given coloring makes $G$ rainbow vertex-connected.

preprint2010arXiv

Nordhaus-Gaddum-type theorem for rainbow connection number of graphs

An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of $G$ , denoted $rc(G)$ , is the minimum number of colors that are used to make $G$ rainbow connected. In this paper we give a Nordhaus-Gaddum-type result for the rainbow connection number. We prove that if $G$ and $\bar{G}$ are both connected, then $4\leq rc(G)+rc(\bar{G})\leq n+2$ . Examples are given to show that the upper bound is sharp for all $n\geq 4$ , and the lower bound is sharp for all $n\geq 8$ . For the rest small $n=4,5,6,7,$ we also give the sharp bounds.

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.

Lily Chen

Research overview

Is this your work?

10 publications

Further hardness results on the generalized connectivity of graphs

The 3-rainbow index of a graph

Tricyclic graphs with maximal revised Szeged index

A quantum algorithm for solving the 3-SAT problem

On a relation between the Szeged index and the Wiener index for bipartite graphs

The (revised) Szeged index and the Wiener index of a nonbipartite graph

Further hardness results on the rainbow vertex-connection number of graphs

Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph

The complexity of determining the rainbow vertex-connection of graphs

Nordhaus-Gaddum-type theorem for rainbow connection number of graphs

See the researcher in context

Building this map preview