Source author record

Jiaojiao Wu

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

ResearcherUnclaimed source record

Discrete Mathematics Computational Complexity Data Structures and Algorithms math.CO Social and Information Networks

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2012arXiv

The Incidence Chromatic Number of Toroidal Grids

An incidence in a graph $G$ is a pair $(v,e)$ with $v \in V(G)$ and $e \in E(G)$ , such that $v$ and $e$ are incident. Two incidences $(v,e)$ and $(w,f)$ are adjacent if $v=w$ , or $e=f$ , or the edge $vw$ equals $e$ or $f$ . The incidence chromatic number of $G$ is the smallest $k$ for which there exists a mapping from the set of incidences of $G$ to a set of $k$ colors that assigns distinct colors to adjacent incidences. In this paper, we prove that the incidence chromatic number of the toroidal grid $T_{m,n}=C_m\Box C_n$ equals 5 when $m,n \equiv 0 \pmod 5$ and 6 otherwise.

preprint2011arXiv

Some Results on the Target Set Selection Problem

In this paper we consider a fundamental problem in the area of viral marketing, called T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if $G$ is a block-cactus graph, then the T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem can be solved in linear time, which generalizes Chen's result \cite{chen2009} for trees, and the time complexity is much better than the algorithm in \cite{treewidth} (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph $G$ is a chordal graph with thresholds $θ(v)\leq 2$ for each vertex $v$ in $G$ , then the problem can be solved in linear time. For a Hamming graph $G$ having thresholds $θ(v)=2$ for each vertex $v$ of $G$ , we precisely determine an optimal target set $S$ for $(G,θ)$ . These results partially answer an open problem raised by Dreyer and Roberts \cite{Dreyer2009}.

preprint2010arXiv

Coloring the square of the Cartesian product of two cycles

The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ in such a way that distinct vertices with distance at most two in $G$ are joined by an edge. We study the chromatic number of the square of the Cartesian product $C_m\Box C_n$ of two cycles and show that the value of this parameter is at most 7 except when $m=n=3$ , in which case the value is 9, and when $m=n=4$ or $m=3$ and $n=5$ , in which case the value is 8. Moreover, we conjecture that whenever $G=C_m\Box C_n$ , the chromatic number of $G^2$ equals $\lceil mn/α(G^2) \rceil$ , where $α(G^2)$ denotes the size of a maximal independent set in $G^2$ .

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.