Source author record

Qingqiong Cai

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.OC

Catalog footprint

Research overview

9works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Integer Linear Programming Formulations for Double Roman Domination Problem

For a graph $G= (V,E)$ , a double Roman dominating function (DRDF) is a function $f : V \to \{0,1,2,3\}$ having the property that if $f (v) = 0$ , then vertex $v$ must have at least two neighbors assigned $2$ under $f$ or {at least} one neighbor $u$ with $f (u) = 3$ , and if $f (v) = 1$ , then vertex $v$ must have at least one neighbor $u$ with $f (u) \ge 2$ . In this paper, we consider the double Roman domination problem, which is an optimization problem of finding the DRDF $f$ such that $\sum_{v\in V} f (v)$ is minimum. We propose {five integer linear programming (ILP) formulations and one mixed integer linear programming formulation with polynomial number of constraints for this problem. Some additional valid inequalities and bounds are also proposed for some of these formulations.} Further, we prove that {the first four models indeed solve the double Roman domination problem, and the last two models} are equivalent to the others regardless of the variable relaxation or usage of a smaller number of constraints and variables. Additionally, we use one ILP formulation to give an $H(2(Δ+1))$ -approximation algorithm. All proposed formulations and approximation algorithm are evaluated on randomly generated graphs to compare the performance.

preprint2015arXiv

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

A path in a vertex-colored graph is called a \emph{vertex-monochromatic path} if its internal vertices have the same color. A vertex-coloring of a graph is a \emph{monochromatic vertex-connection coloring} (\emph{MVC-coloring} for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph $G$ , the \emph{monochromatic vertex-connection number}, denoted by $mvc(G)$ , is defined to be the maximum number of colors used in an \emph{MVC-coloring} of $G$ . These concepts of vertex-version are natural generalizations of the colorful monochromatic connectivity of edge-version, introduced by Caro and Yuster. In this paper, we mainly investigate the Erdős-Gallai-type problems for the monochromatic vertex-connection number $mvc(G)$ and completely determine the exact value. Moreover, the Nordhaus-Gaddum-type inequality for $mvc(G)$ is also given.

preprint2014arXiv

Erdős-Gallai-type results for colorful monochromatic connectivity of a graph

A path in an edge-colored graph is called a \emph{monochromatic path} if all the edges on the path are colored the same. An edge-coloring of $G$ is a \emph{monochromatic connection coloring} (MC-coloring, for short) if there is a monochromatic path joining any two vertices in $G$ . The \emph{monochromatic connection number}, denoted by $mc(G)$ , is defined to be the maximum number of colors used in an MC-coloring of a graph $G$ . These concepts were introduced by Caro and Yuster, and they got some nice results. In this paper, we will study two kinds of Erdős-Gallai-type problems for $mc(G)$ , and completely solve them.

preprint2014arXiv

Note on the upper bound of the rainbow index of a graph

A path in an edge-colored graph $G$ , where adjacent edges may be colored the same, is a rainbow path if every two edges of it receive distinct colors. The rainbow connection number of a connected graph $G$ , denoted by $rc(G)$ , is the minimum number of colors that are needed to color the edges of $G$ such that there exists a rainbow path connecting every two vertices of $G$ . Similarly, a tree in $G$ is a rainbow~tree if no two edges of it receive the same color. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow tree connecting $S$ for each $k$ -subset $S$ of $V(G)$ is called the $k$ -rainbow index of $G$ , denoted by $rx_k(G)$ , where $k$ is an integer such that $2\leq k\leq n$ . Chakraborty et al. got the following result: For every $ε> 0$ , a connected graph with minimum degree at least $εn$ has bounded rainbow connection, where the bound depends only on $ε$ . Krivelevich and Yuster proved that if $G$ has $n$ vertices and the minimum degree $δ(G)$ then $rc(G)<20n/δ(G)$ . This bound was later improved to $3n/(δ(G)+1)+3$ by Chandran et al. Since $rc(G)=rx_2(G)$ , a natural problem arises: for a general $k$ determining the true behavior of $rx_k(G)$ as a function of the minimum degree $δ(G)$ . In this paper, we give upper bounds of $rx_k(G)$ in terms of the minimum degree $δ(G)$ in different ways, namely, via Szemerédi's Regularity Lemma, connected $2$ -step dominating sets, connected $(k-1)$ -dominating sets and $k$ -dominating sets of $G$ .

preprint2014arXiv

The 3-rainbow index and connected dominating sets

A tree in an edge-colored graph is said to be rainbow if no two edges on the tree share the same color. An edge-coloring of $G$ is called 3-rainbow if for any three vertices in $G$ , there exists a rainbow tree connecting them. The 3-rainbow index $rx_3(G)$ of $G$ is defined as the minimum number of colors that are needed in a 3-rainbow coloring of $G$ . This concept, introduced by Chartrand et al., can be viewed as a generalization of the rainbow connection. In this paper, we study the 3-rainbow index by using connected three-way dominating sets and 3-dominating sets. We shown that for every connected graph $G$ on $n$ vertices with minimum degree at least $δ$ ( $3\leqδ\leq5$ ), $rx_{3}(G)\leq \frac{3n}{δ+1}+4$ , and the bound is tight up to an additive constant; whereas for every connected graph $G$ on $n$ vertices with minimum degree at least $δ$ ( $δ\geq3$ ), we get that $rx_{3}(G)\leq n\frac{ln(δ+1)}{δ+1}(1+o_δ(1))+5$ . In addition, we obtain some tight upper bounds of the 3-rainbow index for some special graph classes, including threshold graphs, chain graphs and interval graphs.

preprint2013arXiv

New skew Laplacian energy of a simple digraph

For a simple digraph $G$ of order $n$ with vertex set $\{v_1,v_2,\ldots, v_n\}$ , let $d_i^+$ and $d_i^-$ denote the out-degree and in-degree of a vertex $v_i$ in $G$ , respectively. Let $D^+(G)=diag(d_1^+,d_2^+,\ldots,d_n^+)$ and $D^-(G)=diag(d_1^-,d_2^-,\ldots,d_n^-)$ . In this paper we introduce $\widetilde{SL}(G)=\widetilde{D}(G)-S(G)$ to be a new kind of skew Laplacian matrix of $G$ , where $\widetilde{D}(G)=D^+(G)-D^-(G)$ and $S(G)$ is the skew-adjacency matrix of $G$ , and from which we define the skew Laplacian energy $SLE(G)$ of $G$ as the sum of the norms of all the eigenvalues of $\widetilde{SL}(G)$ . Some lower and upper bounds of the new skew Laplacian energy are derived and the digraphs attaining these bounds are also determined.

preprint2013arXiv

The $(k,\ell)$ -rainbow index for complete bipartite and multipartite graphs

A tree in an edge-colored graph $G$ is said to be a rainbow tree if no two edges on the tree share the same color. Given two positive integers $k$ , $\ell$ with $k\geq 3$ , the \emph{ $(k,\ell)$ -rainbow index} $rx_{k,\ell}(G)$ of $G$ is the minimum number of colors needed in an edge-coloring of $G$ such that for any set $S$ of $k$ vertices of $G$ , there exist $\ell$ internally disjoint rainbow trees connecting $S$ . This concept was introduced by Chartrand et al., and there have been very few results about it. In this paper, we investigate the $(k,\ell)$ -rainbow index for complete bipartite graphs and complete multipartite graphs. Some asymptotic values of their $(k,\ell)$ -rainbow index are obtained.

preprint2013arXiv

The $(k,\ell)$ -rainbow index of random graphs

A tree in an edge colored graph is said to be a rainbow tree if no two edges on the tree share the same color. Given two positive integers $k$ , $\ell$ with $k\geq 3$ , the \emph{ $(k,\ell)$ -rainbow index} $rx_{k,\ell}(G)$ of $G$ is the minimum number of colors needed in an edge-coloring of $G$ such that for any set $S$ of $k$ vertices of $G$ , there exist $\ell$ internally disjoint rainbow trees connecting $S$ . This concept was introduced by Chartrand et. al., and there have been very few related results about it. In this paper, We establish a sharp threshold function for $rx_{k,\ell}(G_{n,p})\leq k$ and $rx_{k,\ell}(G_{n,M})\leq k,$ respectively, where $G_{n,p}$ and $G_{n,M}$ are the usually defined random graphs.

preprint2012arXiv

Solutions to conjectures on the $(k,\ell)$ -rainbow index of complete graphs

The $(k,\ell)$ -rainbow index $rx_{k, \ell}(G)$ of a graph $G$ was introduced by Chartrand et. al. For the complete graph $K_n$ of order $n\geq 6$ , they showed that $rx_{3,\ell}(K_n)=3$ for $\ell=1,2$ . Furthermore, they conjectured that for every positive integer $\ell$ , there exists a positive integer $N$ such that $rx_{3,\ell}(K_{n})=3$ for every integer $n \geq N$ . More generally, they conjectured that for every pair of positive integers $k$ and $\ell$ with $k\geq 3$ , there exists a positive integer $N$ such that $rx_{k,\ell}(K_{n})=k$ for every integer $n \geq N$ . This paper is to give solutions to these conjectures.

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.

Qingqiong Cai

Research overview

Is this your work?

9 publications

Integer Linear Programming Formulations for Double Roman Domination Problem

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

Erdős-Gallai-type results for colorful monochromatic connectivity of a graph

Note on the upper bound of the rainbow index of a graph

The 3-rainbow index and connected dominating sets

New skew Laplacian energy of a simple digraph

The $(k,\ell)$ -rainbow index for complete bipartite and multipartite graphs

The $(k,\ell)$ -rainbow index of random graphs

Solutions to conjectures on the $(k,\ell)$ -rainbow index of complete graphs

See the researcher in context

Building this map preview

Qingqiong Cai

Research overview

Is this your work?

9 publications

Integer Linear Programming Formulations for Double Roman Domination Problem

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

Erdős-Gallai-type results for colorful monochromatic connectivity of a graph

Note on the upper bound of the rainbow index of a graph

The 3-rainbow index and connected dominating sets

New skew Laplacian energy of a simple digraph

The (k,ℓ)(k,\ell)(k,ℓ)-rainbow index for complete bipartite and multipartite graphs

The (k,ℓ)(k,\ell)(k,ℓ)-rainbow index of random graphs

Solutions to conjectures on the (k,ℓ)(k,\ell)(k,ℓ)-rainbow index of complete graphs

See the researcher in context

Building this map preview

The $(k,\ell)$ -rainbow index for complete bipartite and multipartite graphs

The $(k,\ell)$ -rainbow index of random graphs

Solutions to conjectures on the $(k,\ell)$ -rainbow index of complete graphs