Source author record

Jun-Lin Guo

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms math.GR

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Set Representations of Linegraphs

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$ . A family $\mathcal{S}$ of nonempty sets $\{S_1,\ldots,S_n\}$ is a set representation of $G$ if there exists a one-to-one correspondence between the vertices $v_1, \ldots, v_n$ in $V(G)$ and the sets in $\mathcal{S}$ such that $v_iv_j \in E(G)$ if and only if $S_i\cap S_j\neq \es$. A set representation $\mathcal{S}$ is a distinct (respectively, antichain, uniform and simple) set representation if any two sets $S_i$ and $S_j$ in $\mathcal{S}$ have the property $S_i\neq S_j$ (respectively, $S_i\nsubseteq S_j$ , $|S_i|=|S_j|$ and $|S_i\cap S_j|\leqslant 1$ ). Let $U(\mathcal{S})=\bigcup_{i=1}^n S_i$ . Two set representations $\mathcal{S}$ and $\mathcal{S}'$ are isomorphic if $\mathcal{S}'$ can be obtained from $\mathcal{S}$ by a bijection from $U(\mathcal{S})$ to $U(\mathcal{S}')$ . Let $F$ denote a class of set representations of a graph $G$ . The type of $F$ is the number of equivalence classes under the isomorphism relation. In this paper, we investigate types of set representations for linegraphs. We determine the types for the following categories of set representations: simple-distinct, simple-antichain, simple-uniform and simple-distinct-uniform.

preprint2013arXiv

The Domination Number of Generalized Petersen Graphs with a Faulty Vertex

In this paper, we investigate the domination number of generalized Petersen graphs P(n, 2) when there is a faulty vertex. Denote by $γ(P(n,2))$ the domination number of P(n,2) and $γ(P_f(n,2))$ the domination number of P(n,2) with a faulty vertex $u_f$ . We show that $γ(P_f(n,2))=γ(P(n,2))-1$ when $n=5k+1$ or $5k+2$ and $γ(P_f(n,2))=γ(P(n,2))$ for the other cases.

preprint2012arXiv

A linear time algorithm for the next-to-shortest path problem on undirected graphs with nonnegative edge lengths

For two vertices $s$ and $t$ in a graph $G=(V,E)$ , the next-to-shortest path is an $st$ -path which length is minimum amongst all $st$ -paths strictly longer than the shortest path length. In this paper we show that, when the graph is undirected and all edge lengths are nonnegative, the problem can be solved in linear time if the distances from $s$ and $t$ to all other vertices are given. This result generalizes the previous work (DOI 10.1007/s00453-011-9601-7) to allowing zero-length edges.

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.