Source author record

Junqing 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

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Ore-type condition for antidirected Hamilton cycles in oriented graphs

An antidirected cycle in a digraph $G$ is a subdigraph whose underlying graph is a cycle, and in which no two consecutive edges form a directed path in $G$ . Let $σ_{+-}(G)$ be the minimum value of $d^+(x)+d^-(y)$ over all pairs of vertices $x, y$ such that there is no edge from $x$ to $y$ , that is, $σ_{+-}(G)=\min\{d^+(x)+d^-(y): \{x,y\}\subseteq V(G), xy\notin E(G)\}.$ In 1972, Woodall extended Ore's theorem to digraphs by showing that every digraph $G$ on $n$ vertices with $σ_{+-}(G)\geqslant n$ contains a directed Hamilton cycle. Very recently, this result was generalized to oriented graphs under the condition $σ_{+-}(G)\geqslant(3n-3)/4$ . In this paper, we give the exact Ore-type degree threshold for the existence of antidirected Hamilton cycles in oriented graphs. More precisely, we prove that for sufficiently large even integer $n$ , every oriented graph $G$ on $n$ vertices with $σ_{+-}(G)\geqslant(3n+2)/4$ contains an antidirected Hamilton cycle. Moreover, we show that this degree condition is best possible.

preprint2020arXiv

On graphs with some normalized Laplacian eigenvalue of extremal multiplicity

Let $G$ be a connected simple graph on $n$ vertices. Let $\mathcal{L}(G)$ be the normalized Laplacian matrix of $G$ and $ρ_{n-1}(G)$ be the second least eigenvalue of $\mathcal{L}(G)$ . Denote by $ν(G)$ the independence number of $G$ . Recently, the paper [Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity $n-3$ , arXiv:1912.13227] discussed the graphs with some normalized Laplacian eigenvalue of multiplicity $n-3$ . However, there is one remaining case (graphs with $ρ_{n-1}(G)\neq 1$ and $ν(G)= 2$ ) not considered. In this paper, we focus on cographs and graphs with diameter 3 to investigate the graphs with some normalized Laplacian eigenvalue of multiplicity $n-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.