Source author record

Jun-Yi 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 Information Theory math.IT

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Beyond Hamiltonicity of Prime Difference Graphs

A graph is Hamiltonian if it contains a cycle which visits every vertex of the graph exactly once. In this paper, we consider the problem of Hamiltonicity of a graph $G_n$ , which will be called the prime difference graph of order $n$ , with vertex set $\{1,2,\cdots, n\}$ and edge set $\{uv: |u-v|$ is a prime number $\}$ . A recent result, conjectured by Sun and later proved by Chen, asserts that $G_n$ is Hamiltonian for $n\geq 5$ . This paper extends their result in three directions. First, we prove that for any two integers $a$ and $b$ with $1\leq a<b\leq n$ , there is a Hamilton path in $G_n$ from $a$ to $b$ except some cases of small $n$ . This result implies robustness of the Hamiltonicity property of the prime difference graph in a sense that for any edge $e$ in $G_n$ there exists a Hamilton cycle containing $e$ . Second, we show that the prime difference graph contains considerably more about the cycle structure than Hamiltonicity; precisely, for any integer $n\geq 7$ , the prime difference graph $G_n$ contains any 2-factor of the complete graph of order $n$ as a subgraph. Finally, we find that $G_n$ may contain more edge-disjoint Hamilton cycles. In particular, these Hamilton cycles are generated by two prime differences.

preprint2016arXiv

Families of Subsets Without a Given Poset in the Interval Chains

For two posets $P$ and $Q$ , we say $Q$ is $P$ -free if there does not exist any order-preserving injection from $P$ to $Q$ . The speical case for $Q$ being the Boolean lattice $B_n$ is well-studied, and the optiamal value is denoted as $\lanp$. Let us define $\La(Q,P)$ to be the largest size of any $P$ -free subposet of $Q$ . In this paper, we give an upper bound for $\La(Q,P)$ when $Q$ is a double chain and $P$ is any graded poset, which is better than the previous known upper bound, by means of finding the indpendence number of an auxiliary graph related to $P$ . For the auxiliary graph, we can find its independence number in polynomial time. In addition, we give methods to construct the posets satisfying the Griggs-Lu conjecture.

preprint2014arXiv

Multi-Group Testing for Items with Real-Valued Status under Standard Arithmetic

This paper proposes a novel generalization of group testing, called multi-group testing, which relaxes the notion of "testing subset" in group testing to "testing multi-set". The generalization aims to learn more information of each item to be tested rather than identify only defectives as was done in conventional group testing. This paper provides efficient nonadaptive strategies for the multi-group testing problem. The major tool is a new structure, $q$ -ary additive $(w,d)$ -disjunct matrix, which is a generalization of the well-known binary disjunct matrix introduced by Kautz and Singleton in 1964.

preprint2014arXiv

On-Line Choice Number of Complete Multipartite Graphs: an Algorithmic Approach

This paper studies the on-line choice number on complete multipartite graphs with independence number $m$ . We give a unified strategy for every prescribed $m$ . Our main result leads to several interesting consequences comparable to known results. (1) If $k_1-\sum_{p=2}^m(\frac{p^2}{2}-\frac{3p}{2}+1)k_p\geq 0$ , where $k_p$ denotes the number of parts of cardinality $p$ , then $G$ is on-line chromatic-choosable. (2) If $|V(G)|\leq\frac{m^2-m+2}{m^2-3m+4}χ(G)$ , then $G$ is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs $K_{m\star k}$ is at most $(m+\frac{1}{2}-\sqrt{2m-2})k$ for $m\geq 3$ .

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.