Source author record

Bo Ning

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

ResearcherUnclaimed source record

math.CO hep-th cond-mat.str-el math.NT quant-ph gr-qc math.CA physics.optics

Catalog footprint

Research overview

40works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A revisit to Bang-Jensen-Gutin conjecture and Yeo's theorem

A path (cycle) is properly-colored if consecutive edges are of distinct colors. In 1997, Bang-Jensen and Gutin conjectured a necessary and sufficient condition for the existence of a Hamilton path in an edge-colored complete graph. This conjecture, confirmed by Feng, Giesen, Guo, Gutin, Jensen and Rafley in 2006, was laterly playing an important role in Lo's asymptotical proof of Bollobás-Erdős' conjecture on properly-colored Hamilton cycles. In 1997, Yeo obtained a structural characterization of edge-colored graphs that containing no properly colored cycles. This result is a fundamental tool in the study of edge-colored graphs. In this paper, we first give a much shorter proof of the Bang-Jensen-Gutin Conjecture by two novel absorbing lemmas. We also prove a new sufficient condition for the existence of a properly-colored cycle and then deduce Yeo's theorem from this result and a closure concept in edge-colored graphs.

preprint2021arXiv

A Complete Solution to the Cvetković-Rowlinson Conjecture

In 1990, Cvetković and Rowlinson [The largest eigenvalue of a graph: a survey, Linear Multilinear Algebra 28(1-2) (1990), 3--33] conjectured that among all outerplanar graphs on $n$ vertices, $K_1\vee P_{n-1}$ attains the maximum spectral radius. In 2017, Tait and Tobin [Three conjectures in extremal spectral graph theory, J. Combin. Theory, Ser. B 126 (2017) 137-161] confirmed the conjecture for sufficiently large values of $n$ . In this article, we show the conjecture is true for all $n\geq2$ except for $n=6$ .

preprint2021arXiv

Constraints on low-energy effective theories from weak cosmic censorship

We examine the weak cosmic censorship conjecture (WCCC) for the extremal charged black hole in possible generalizations of Einstein-Maxwell theory due to the higher order corrections, up to fourth-derivative terms. Our derivation is based on Wald's gedanken experiment to destroy an extremal black hole. We find that, provided the null energy condition for the falling matter, the WCCC is preserved for all possible generalizations. Thus, the WCCC cannot serve as a constraint to the higher order effective theories. We also show that up to first order variations of black hole mass and charge, WCCC is preserved for non-rotating extremal black holes in all $n$ -dimensional diffeomorphism-covariant theories of gravity and $U(1)$ gauge field.

preprint2021arXiv

Extremal problems of Erdős, Faudree, Schelp and Simonovits on paths and cycles

For positive integers $n>d\geq k$ , let $ϕ(n,d,k)$ denote the least integer $ϕ$ such that every $n$ -vertex graph with at least $ϕ$ vertices of degree at least $d$ contains a path on $k+1$ vertices. Many years ago, Erdős, Faudree, Schelp and Simonovits proposed the study of the function $ϕ(n,d,k)$ , and conjectured that for any positive integers $n>d\geq k$ , it holds that $ϕ(n,d,k)\leq \lfloor\frac{k-1}{2}\rfloor\lfloor\frac{n}{d+1}\rfloor+ε$ , where $ε=1$ if $k$ is odd and $ε=2$ otherwise. In this paper we determine the values of the function $ϕ(n,d,k)$ exactly. This confirms the above conjecture of Erdős et al. for all positive integers $k\neq 4$ and in a corrected form for the case $k=4$ . Our proof utilizes, among others, a lemma of Erdős et al. \cite{EFSS89}, a theorem of Jackson \cite{J81}, and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin \cite{KLZ}, where the latter two results concern maximum cycles in bipartite graphs. Moreover, we construct examples to provide answers to two closely related questions raised by Erdős et al.

preprint2021arXiv

The stability method, eigenvalues and cycles of consecutive lengths

Woodall proved that for a graph $G$ of order $n\geq 2k+3$ where $k\geq 0$ is an integer, if $e(G)\geq \binom{n-k-1}{2}+\binom{k+2}{2}+1$ then $G$ contains a $C_{\ell}$ for each $\ell\in [3,n-k]$ . In this article, we prove a stability result of this theorem. As a byproduct, we give complete solutions to two problems in \cite{GN19}. Our second part is devoted to an open problem by Nikiforov: what is the maximum $C$ such that for all positive $\varepsilon<C$ and sufficiently large $n$ , every graph $G$ of order $n$ with spectral radius $ρ(G)>\sqrt{\lfloor\frac{n^2}{4}\rfloor}$ contains a cycle of length $\ell$ for every $\ell\leq (C-\varepsilon)n$ . We prove that $C\geq\frac{1}{4}$ by a method different from previous ones, improving the existing bounds. We also derive an Erdős-Gallai type edge number condition for even cycles, which may be of independent interest.

preprint2020arXiv

A Strengthening of Erdős-Gallai Theorem and Proof of Woodall's Conjecture

For a 2-connected graph $G$ on $n$ vertices and two vertices $x,y\in V(G)$ , we prove that there is an $(x,y)$ -path of length at least $k$ if there are at least $\frac{n-1}{2}$ vertices in $V(G)\backslash \{x,y\}$ of degree at least $k$ . This strengthens a well-known theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with $n$ vertices contains a cycle of length at least $2k$ if it has at least $\frac{n}{2}+k$ vertices of degree at least $k$ . This confirms a 1975 conjecture made by Woodall. As another applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and of a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond.

preprint2020arXiv

An Ore-type Condition for Large $k$ -factor and Disjoint Perfect Matchings

Win [\emph{J. Graph Theory} {\bf 6}(1982), 489--492] conjectured that a graph $G$ on $n$ vertices contains $k$ disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least $n+k-2$ , where $n$ is even and $n\geq k+2$ . In this paper, we prove that Win's conjecture is true for $k\geq n/2$ , where $n$ is sufficiently large. To show this result, we prove a theorem on $k$ -factor in a graph under some Ore-type condition. Our main tools include Tutte's $k$ -factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization, and the solution to the longstanding 1-factor decomposition conjecture.

preprint2020arXiv

Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations

The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum\limits_{i=1}^n(-1)^{n-i}a_{i}x^i$ , where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $ε(G)=\sum\limits_{i=1}^n (n-i)a_i/\sum\limits_{i=1}^n a_i$ is the mean size of a broken-cycle-free spanning subgraph of $G$ . In this article, we confirm and strengthen a conjecture proposed by Lundow and Markström in 2006 that $ε(T_n)< ε(G)<ε(K_n)$ holds for any connected graph $G$ of order $n$ which is neither the complete graph $K_n$ nor a tree $T_n$ of order $n$ . The most crucial step of our proof is to obtain the interpretation of all $a_i$ 's by the number of acyclic orientations of $G$ .

preprint2020arXiv

The formula for Turán number of spanning linear forests

Let $\mathcal{F}$ be a family of graphs. The Turán number $ex(n;\mathcal{F})$ is defined to be the maximum number of edges in a graph of order $n$ that is $\mathcal{F}$ -free. In 1959, Erdős and Gallai determined the Turán number of $M_{k+1}$ (a matching of size $k+1$ ) as follows: $ex(n;M_{k+1})= \max\left\{\binom{2k+1}{2},\binom{n}{2}-\binom{n-k}{2}\right\}.$ Since then, there has been a lot of research on Turán number of linear forests. A linear forest is a graph whose connected components are all paths or isolated vertices. Let $\mathcal{L}_{n,k}$ be the family of all linear forests of order $n$ with $k$ edges. In this paper, we prove that $ex(n;\mathcal{L}_{n,k})= \max \left\{\binom{k}{2},\binom{n}{2}-\binom{n-\left\lfloor \frac{k-1}{2}\right \rfloor}{2}+ c \right\},$ where $c=0$ if $k$ is odd and $c=1$ otherwise. This determines the maximum number of edges in a non-Hamiltonian graph with given Hamiltonian completion number and also solves two open problems in \cite{WY} as special cases. Moreover, we show that our main theorem implies Erdős-Gallai Theorem and also gives a short new proof for it by the closure and counting techniques. Finally, we generalize our theorem to a conjecture which implies the famous Erdős Matching Conjecture.

preprint2019arXiv

Exact bipartite Turán numbers of large even cycles

Let the bipartite Turán number $ex(m,n,H)$ of a graph $H$ be the maximum number of edges in an $H$ -free bipartite graph with two parts of sizes $m$ and $n$ , respectively. In this paper, we prove that $ex(m,n,C_{2t})=(t-1)n+m-t+1$ for any positive integers $m,n,t$ with $n\geq m\geq t\geq \frac{m}{2}+1$ . This confirms the rest of a conjecture of Györi \cite{G97} (in a stronger form), and improves the upper bound of $ex(m,n,C_{2t})$ obtained by Jiang and Ma \cite{JM18} for this range. We also prove a tight edge condition for consecutive even cycles in bipartite graphs, which settles a conjecture in \cite{A09}. As a main tool, for a longest cycle $C$ in a bipartite graph, we obtain an estimate on the upper bound of the number of edges which are incident to at most one vertex in $C$ . Our two results generalize or sharpen a classical theorem due to Jackson \cite{J85} in different ways.

preprint2019arXiv

Stability results on the circumference of a graph

In this paper, we extend and refine previous Turán-type results on graphs with a given circumference. Let $W_{n,k,c}$ be the graph obtained from a clique $K_{c-k+1}$ by adding $n-(c-k+1)$ isolated vertices each joined to the same $k$ vertices of the clique, and let $f(n,k,c)=e(W_{n,k,c})$ . Improving a celebrated theorem of Erdős and Gallai, Kopylov proved that for $c<n$ , any 2-connected graph $G$ on $n$ vertices with circumference $c$ has at most $\max{f(n,2,c),f(n,\lfloor\frac{c}{2}\rfloor,c)}$ edges. Recently, Füredi et al. proved a stability version of Kopylov's theorem. Their main result states that if $G$ is a 2-connected graph on $n$ vertices with circumference $c$ such that $10\leq c<n$ and $e(G)>\max{f(n,3,c),f(n,\lfloor\frac{c}{2}\rfloor-1,c)}$ , then either $G$ is a subgraph of $W_{n,2,c}$ or $W_{n,\lfloor\frac{c}{2}\rfloor,c}$ , or $c$ is odd and $G$ is a subgraph of a member of two well-characterized families which we define as $\mathcal{X}_{n,c}$ and $\mathcal{Y}_{n,c}$ . We prove that if $G$ is a 2-connected graph on $n$ vertices with minimum degree at least $k$ and circumference $c$ such that $10\leq c<n$ and $e(G)>\max{f(n,k+1,c),f(n,\lfloor\frac{c}{2}\rfloor-1,c)}$ , then one of the following holds: (i) $G$ is a subgraph of $W_{n,k,c}$ or $W_{n,\lfloor\frac{c}{2}\rfloor,c}$ , (ii) $k=2$ , $c$ is odd, and $G$ is a subgraph of a member of $\mathcal{X}_{n,c}\cup \mathcal{Y}_{n,c}$ , or (iii) $k\geq 3$ and $G$ is a subgraph of the union of a clique $K_{c-k+1}$ and some cliques $K_{k+1}$ 's, where any two cliques share the same two vertices. This provides a unified generalization of the above result of Füredi et al. as well as a recent result of Li et al. and independently, of Füredi et al. on non-Hamiltonian graphs. Moreover, we prove a stability result on a classical theorem of Bondy on the circumference.

preprint2018arXiv

Extensions of Erdős-Gallai Theorem and Luo's Theorem with Applications

The famous Erdős-Gallai Theorem on the Turán number of paths states that every graph with $n$ vertices and $m$ edges contains a path with at least $\frac{2m}{n}$ edges. In this note, we first establish a simple but novel extension of the Erdős-Gallai Theorem by proving that every graph $G$ contains a path with at least $\frac{(s+1)N_{s+1}(G)}{N_{s}(G)}+s-1$ edges, where $N_j(G)$ denotes the number of $j$ -cliques in $G$ for $1\leq j\leqω(G)$ . We also construct a family of graphs which shows our extension improves the estimate given by Erdős-Gallai Theorem. Among applications, we show, for example, that the main results of \cite{L17}, which are on the maximum possible number of $s$ -cliques in an $n$ -vertex graph without a path with $l$ vertices (and without cycles of length at least $c$ ), can be easily deduced from this extension. Indeed, to prove these results, Luo \cite{L17} generalized a classical theorem of Kopylov and established a tight upper bound on the number of $s$ -cliques in an $n$ -vertex 2-connected graph with circumference less than $c$ . We prove a similar result for an $n$ -vertex 2-connected graph with circumference less than $c$ and large minimum degree. We conclude this paper with an application of our results to a problem from spectral extremal graph theory on consecutive lengths of cycles in graphs.

preprint2016arXiv

Cyclability of $id$ -cycles in graphs

Let $G$ be a graph on $n$ vertices and $C'=v_0v_1\cdots v_{p-1}v_0$ a vertex sequence of $G$ with $p\geq 3$ ( $v_i\neq v_j$ for all $i,j=0,1,\ldots,p-1$ , $i\neq j$ ). If for any successive vertices $v_i$ , $v_{i+1}$ on $C'$ , either $v_iv_{i+1}\in E(G)$ or both of the first implicit-degrees of $v_i$ and $v_{i+1}$ are at least $n/2$ (indices are taken modulo $p$ ), then $C'$ is called an $id$ -cycle of $G$ . In this paper, we prove that for every $id$ -cycle $C'$ , there exists a cycle $C$ in $G$ with $V(C')\subseteq V(C)$ . This generalizes several early results on the Hamiltonicity and cyclability of graphs.

preprint2016arXiv

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called \emph{claw-free} if it contains no induced subgraph isomorphic to $K_{1,3}$ . Matthews and Sumner proved that a 2-connected claw-free graph $G$ is hamiltonian if every vertex of it has degree at least $(|V(G)|-2)/3$ . At the workshop C\&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of $N$ (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of $Z_1$ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs $H$ such that a 2-connected claw-free graph $G$ is hamiltonian if each end-vertex of every induced copy of $H$ in $G$ has degree at least $|V(G)|/3+1$ . This gives an affirmative solution of the conjecture of Broersma up to an additive constant.

preprint2016arXiv

On a conjecture of Chen-Guo-Wang

Towards confirming Sun's conjecture on the strict log-concavity of combinatorial sequence involving the n $th$ Bernoulli number, Chen, Guo and Wang proposed a conjecture about the log-concavity of the function $θ(x)=\sqrt[x]{2ζ(x)Γ(x+1)}$ for $x\in (6,\infty)$ , where $ζ(x)$ is the Riemann zeta function and $Γ(x)$ is the Gamma function. In this paper, we first prove this conjecture along the spirit of Zhu's previous work. Second, we extend Chen et al.'s conjecture in the sense of almost infinite log-monotonicity of combinatorial sequences, which was also introduced by Chen et al. Furthermore, by using an analogue criterion to the one of Chen, Guo and Wang, we deduce the almost infinite log-monotonicity of the sequences $\frac{1}{\sqrt[n]{|B_{2n}|}}$ , $T_n$ and $\frac{1}{\sqrt[n]{T_n}}$ , where $B_{2n}$ and $T_{n}$ are the $2n$ th Bernoulli number and the $n$ th tangent number, respectively. These results can be seen as extensions of some solved conjectures of Sun.

preprint2016arXiv

Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles

In 1962, Erdős gave a sufficient condition for Hamilton cycles in terms of the vertex number, edge number, and minimum degree of graphs which generalized Ore's theorem. One year later, Moon and Moser gave an analogous result for Hamilton cycles in balanced bipartite graphs. In this paper we present the spectral analogues of Erdős' theorem and Moon-Moser's theorem, respectively. Let $\mathcal{G}_n^k$ be the class of non-Hamiltonian graphs of order $n$ and minimum degree at least $k$ . We determine the maximum (signless Laplacian) spectral radius of graphs in $\mathcal{G}_n^k$ (for large enough $n$ ), and the minimum (signless Laplacian) spectral radius of the complements of graphs in $\mathcal{G}_n^k$ . All extremal graphs with the maximum (signless Laplacian) spectral radius and with the minimum (signless Laplacian) spectral radius of the complements are determined, respectively. We also solve similar problems for balanced bipartite graphs and the quasi-complements.

preprint2016arXiv

Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs

In 1962, Erdős proved a theorem on the existence of Hamilton cycles in graphs with given minimum degree and number of edges. Significantly strengthening in case of balanced bipartite graphs, Moon and Moser proved a corresponding theorem in 1963. In this paper we establish several spectral analogues of Moon and Moser's theorem on Hamilton paths in balanced bipartite graphs and nearly balanced bipartite graphs. One main ingredient of our proofs is a structural result of its own interest, involving Hamilton paths in balanced bipartite graphs with given minimum degree and number of edges.

preprint2015arXiv

Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions

A graph $G$ is called \emph{claw-o-heavy} if every induced claw ( $K_{1,3}$ ) of $G$ has two end-vertices with degree sum at least $|V(G)|$ in $G$ . For a given graph $R$ , $G$ is called \emph{ $R$ -f-heavy} if for every induced subgraph $H$ of $G$ isomorphic to $R$ and every pair of vertices $u,v\in V(H)$ with $d_H(u,v)=2$ , there holds $\max\{d(u),d(v)\}\geq |V(G)|/2$ . In this paper, we prove that every 2-connected claw-\emph{o}-heavy and $Z_3$ -\emph{f}-heavy graph is hamiltonian (with two exceptional graphs), where $Z_3$ is the graph obtained from identifying one end-vertex of $P_4$ (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed in [B. Ning, S. Zhang, Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs, Discrete Math. 313 (2013) 1715--1725], and also implies two previous theorems of Faudree et al. and Chen et al., respectively.

preprint2015arXiv

Spectral radius and Hamiltonian properties of graphs

Let $G$ be a graph with minimum degree $δ$ . The spectral radius of $G$ , denoted by $ρ(G)$ , is the largest eigenvalue of the adjacency matrix of $G$ . In this note we mainly prove the following two results. (1) Let $G$ be a graph on $n\geq 4$ vertices with $δ\geq 1$ . If $ρ(G)> n-3$ , then $G$ contains a Hamilton path unless $G\in\{K_1\vee (K_{n-3}+2K_1),K_2\vee 4K_1,K_1\vee (K_{1,3}+K_1)\}$ . (2) Let $G$ be a graph on $n\geq 14$ vertices with $δ\geq 2$ . If $ρ(G)\geq ρ(K_2\vee (K_{n-4}+2K_1))$ , then $G$ contains a Hamilton cycle unless $G= K_2\vee (K_{n-4}+2K_1)$ . As corollaries of our first result, two previous theorems due to Fiedler and Nikiforov and Lu et al. are obtained, respectively. Our second result refines another previous theorem of Fiedler and Nikiforov.

preprint2015arXiv

Spectral radius and traceability of connected claw-free graphs

Let $G$ be a connected claw-free graph on $n$ vertices and $\overline{G}$ be its complement graph. Let $μ(G)$ be the spectral radius of $G$ . Denote by $N_{n-3,3}$ the graph consisting of $K_{n-3}$ and three disjoint pendent edges. In this note we prove that: (1) If $μ(G)\geq n-4$ , then $G$ is traceable unless $G=N_{n-3,3}$ . (2) If $μ(\overline{G})\leq μ(\overline{N_{n-3,3}})$ and $n\geq 24$ , then $G$ is traceable unless $G=N_{n-3,3}$ . Our works are counterparts on claw-free graphs of previous theorems due to Lu et al., and Fiedler and Nikiforov, respectively.

preprint2014arXiv

A note on nowhere-zero 3-flow and Z_3-connectivity

There are many major open problems in integer flow theory, such as Tutte's 3-flow conjecture that every 4-edge-connected graph admits a nowhere-zero 3-flow, Jaeger et al.'s conjecture that every 5-edge-connected graph is $Z_3$ -connected and Kochol's conjecture that every bridgeless graph with at most three 3-edge-cuts admits a nowhere-zero 3-flow (an equivalent version of 3-flow conjecture). Thomassen proved that every 8-edge-connected graph is $Z_3$ -connected and therefore admits a nowhere-zero 3-flow. Furthermore, Lov $\acute{a}$ sz, Thomassen, Wu and Zhang improved Thomassen's result to 6-edge-connected graphs. In this paper, we prove that: (1) Every 4-edge-connected graph with at most seven 5-edge-cuts admits a nowhere-zero 3-flow. (2) Every bridgeless graph containing no 5-edge-cuts but at most three 3-edge-cuts admits a nowhere-zero 3-flow. (3) Every 5-edge-connected graph with at most five 5-edge-cuts is $Z_3$ -connected. Our main theorems are partial results to Tutte's 3-flow conjecture, Kochol's conjecture and Jaeger et al.'s conjecture, respectively.

preprint2014arXiv

Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

Let claw be the graph $K_{1,3}$ . A graph $G$ on $n\geq 3$ vertices is called \emph{o}-heavy if each induced claw of $G$ has a pair of end-vertices with degree sum at least $n$ , and 1-heavy if at least one end-vertex of each induced claw of $G$ has degree at least $n/2$ . In this note, we show that every 2-connected $o$ -heavy or 3-connected 1-heavy graph is Hamiltonian if we restrict Fan-type degree condition or neighborhood intersection condition to certain pairs of vertices in some small induced subgraphs of the graph. Our results improve or extend previous results of Broersma et al., Chen et al., Fan, Goodman & Hedetniemi, Gould & Jacobson, and Shi on the existence of Hamilton cycles in graphs.

preprint2014arXiv

Long-term Stabilization of Fiber Laser Using Phase-locking Technique with Ultra-low Phase Noise and Phase Drift

We review the conventional phase-locking technique in the long-term stabilization of the mode-locked fiber laser and investigate the phase noise limitation of the conventional technique. To break the limitation, we propose an improved phase-locking technique with an optic-microwave phase detector in achieving the ultra-low phase noise and phase drift. The mechanism and the theoretical model of the novel phase-locking technique are also discussed. The long-term stabilization experiments demonstrate that the improved technique can achieve the long-term stabilization for the MLFL with ultra-low phase noise and phase drift. The excellent locking performance of the improved phase-locking technique implies that this technique can be used to stabilize the mode-locked fiber laser with the highly stable H-master or optical clock without stability loss.

preprint2014arXiv

Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs

In 1992, Manoussakis conjectured that a strongly 2-connected digraph $D$ on $n$ vertices is hamiltonian if for every two distinct pairs of independent vertices $x,y$ and $w,z$ we have $d(x)+d(y)+d(w)+d(z)\geq 4n-3$ . In this note we show that $D$ has a Hamilton path, which gives an affirmative evidence supporting this conjecture.

preprint2014arXiv

On path-quasar Ramsey numbers

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$ . Parsons gave a recursive formula to determine the values of $R(P_n,K_{1,m})$ , where $P_n$ is a path on $n$ vertices and $K_{1,m}$ is a star on $m+1$ vertices. In this note, we first give an explicit formula for the path-star Ramsey numbers. Secondly, we study the Ramsey numbers $R(P_n,K_1\vee F_m)$ , where $F_m$ is a linear forest on $m$ vertices. We determine the exact values of $R(P_n,K_1\vee F_m)$ for the cases $m\leq n$ and $m\geq 2n$ , and for the case that $F_m$ has no odd component. Moreover, we give a lower bound and an upper bound for the case $n+1\leq m\leq 2n-1$ and $F_m$ has at least one odd component.

preprint2014arXiv

Quantum Decoherence with Holography

Quantum decoherence is the loss of a system's purity due to its interaction with the surrounding environment. Via the AdS/CFT correspondence, we study how a system decoheres when its environment is a strongly-coupled theory. In the Feynman-Vernon formalism, we compute the influence functional holographically by relating it to the generating function of Schwinger-Keldysh propagators and thereby obtain the dynamics of the system's density matrix. We present two exactly solvable examples: (1) a straight string in a BTZ black hole and (2) a scalar probe in AdS $_5$ . We prepare an initial state that mimics Schrödinger's cat and identify different stages of its decoherence process using the time-scaling behaviors of Rényi entropy. We also relate decoherence to local quantum quenches, and by comparing the time evolution behaviors of the Wigner function and Rényi entropy we demonstrate that the relaxation of local quantum excitations leads to the collapse of its wave-function.

preprint2013arXiv

A long cycle theorem involving Fan-type degree condition and neighborhood intersection

In this short note, we give a new sufficient condition for the existence of long cycles in graphs involving Fan-type degree condition and neighborhood intersection.

preprint2013arXiv

An inductive proof of Straub's q-analogue of Ljunggren's congruence

Recently, Straub gave an interesting $q$ -analogue of a binomial congruence of Ljunggren. In this note we give an inductive proof of his result.

preprint2013arXiv

Notes on q-analogues of a binomial congruence of Glaisher

Andrews once gave $q$ -analogues of a binomial congruence of Glaisher, and he suggested perfect $q$ -analogues. In this note we give ones meeting the demand of Andrews.

preprint2013arXiv

Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs

Bedrossian characterized all pairs of forbidden subgraphs for a 2-connected graph to be Hamiltonian. Instead of forbidding some induced subgraphs, we relax the conditions for graphs to be Hamiltonian by restricting Ore- and Fan-type degree conditions on these induced subgraphs. Let $G$ be a graph on $n$ vertices and $H$ be an induced subgraph of $G$ . $H$ is called \emph{o}-heavy if there are two nonadjacent vertices in $H$ with degree sum at least $n$ , and is called $f$ -heavy if for every two vertices $u,v\in V(H)$ , $d_{H}(u,v)=2$ implies that $\max\{d(u),d(v)\}\geq n/2$ . We say that $G$ is $H$ -\emph{o}-heavy ( $H$ -\emph{f}-heavy) if every induced subgraph of $G$ isomorphic to $H$ is \emph{o}-heavy (\emph{f}-heavy). In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ such that every 2-connected $R$ -\emph{f}-heavy and $S$ -\emph{f}-heavy ( $R$ -\emph{o}-heavy and $S$ -\emph{f}-heavy, $R$ -\emph{f}-heavy and $S$ -free) graph is Hamiltonian. Our results extend several previous theorems on forbidden subgraph conditions and heavy subgraph conditions for Hamiltonicity of 2-connected graphs.

preprint2013arXiv

Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs

A graph $G$ on $n$ vertices is Hamiltonian if it contains a spanning cycle, and pancyclic if it contains cycles of all lengths from 3 to $n$ . In 1984, Fan presented a degree condition involving every pair of vertices at distance two for a 2-connected graph to be Hamiltonian. Motivated by Fan's result, we say that an induced subgraph $H$ of $G$ is $f_1$ -heavy if for every pair of vertices $u,v\in V(H)$ , $d_{H}(u,v)=2$ implies $\max\{d(u),d(v)\}\geq (n+1)/2$ . For a given graph $R$ , $G$ is called $R$ - $f_1$ -heavy if every induced subgraph of $G$ isomorphic to $R$ is $f_1$ -heavy. In this paper we show that for a connected graph $S$ with $S\neq P_3$ and a 2-connected claw- $f_1$ -heavy graph $G$ which is not a cycle, $G$ being $S$ - $f_1$ -heavy implies $G$ is pancyclic if $S=P_4,Z_1$ or $Z_2$ , where claw is $K_{1,3}$ and $Z_i$ is the path $a_1a_2a_3... a_{i+2}a_{i+3}$ plus the edge $a_1a_3$ . Our result partially improves a previous theorem due to Bedrossian on pancyclicity of 2-connected graphs.

preprint2013arXiv

Rainbow triangles in edge-colored graphs

Let $G$ be an edge-colored graph. The color degree of a vertex $v$ of $G$ , is defined as the number of colors of the edges incident to $v$ . The color number of $G$ is defined as the number of colors of the edges in $G$ . A rainbow triangle is one in which every pair of edges have distinct colors. In this paper we give some sufficient conditions for the existence of rainbow triangles in edge-colored graphs in terms of color degree, color number and edge number. As a corollary, a conjecture proposed by Li and Wang (Color degree and heterochromatic cycles in edge-colored graphs, European J. Combin. 33 (2012) 1958--1964) is confirmed.

preprint2013arXiv

Refined Holographic Entanglement Entropy for the AdS Solitons and AdS black Holes

We consider the refinement of the holographic entanglement entropy for the holographic dual theories to the AdS solitons and AdS black holes, including the corrected ones by the Gauss-Bonnet term. The refinement is obtained by extracting the UV-independent piece of the holographic entanglement entropy, the so-called renormalized entanglement entropy which is independent of the choices of UV cutoff. Our main results are (i) the renormalized entanglement entropies of the AdS $_{d+1}$ soliton for $d=4,5$ are neither monotonically decreasing along the RG flow nor positive definite, especially around the deconfinement/confinement phase transition; (ii) there is no topological entanglement entropy for AdS $_5$ soliton even with Gauss-Bonnet correction; (iii) for the AdS black holes, the renormalized entanglement entropy obeys an expected volume law at IR regime, and the transition between UV and IR regimes is a smooth crossover even with Gauss-Bonnet correction; (iv) based on AdS/MERA conjecture, we postulate that the IR fixed-point state for the non-extremal AdS soliton is a trivial product state.

preprint2013arXiv

The Ramsey numbers of paths versus wheels: a complete solution

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$ . We denote by $P_n$ the path on $n$ vertices and $W_m$ the wheel on $m+1$ vertices. Chen et al. and Zhang determined the values of $R(P_n,W_m)$ when $m\leq n+1$ and when $n+2\leq m\leq 2n$ , respectively. In this paper we determine all the values of $R(P_n,W_m)$ for the left case $m\geq 2n+1$ . Together with Chen et al's and Zhang's results, we give a complete solution to the problem of determining the Ramsey numbers of paths versus wheels.

preprint2013arXiv

Two sufficient conditions for the existence of Hamilton cycles in graphs

Let $G$ be a graph on $n\geq 3$ vertices, claw the bipartite graph $K_{1,3}$ , and $Z_i$ the graph obtained from a triangle by attaching a path of length $i$ to its one vertex. $G$ is called 1-heavy if at least one end vertex of each induced claw of $G$ has degree at least $n/2$ , and claw-\emph{o}-heavy if each induced claw of it has a pair of end vertices with degree sum at least $n$ . In this paper we prove two results: (1) Every 2-connected claw- $o$ -heavy graph $G$ is Hamiltonian if every pair of vertices $u,v$ in a subgraph $H\cong Z_1$ contained in an induced subgraph $Z_2$ of $G$ with $d_{H}(u,v)=2$ satisfies one of the following conditions: ( $a$ ) $|N(u)\cap N(v)|\geq 2$ ; ( $b$ ) $\max(d(u),d(v))\geq n/2$ . (2) Every 3-connected 1-heavy graph $G$ is Hamiltonian if every pair of vertices $u,v$ in an induced subgraph $H\cong Z_2$ of $G$ with $d_{H}(u,v)=2$ satisfies one of the following conditions: ( $a$ ) $|N(u)\cap N(v)|\geq 2$ ; ( $b$ ) $\max(d(u),d(v))\geq n/2$ . Our results improve or extend previous theorems of Broersma et al., Chen et al., Fan, Goodman & Hedetniemi, Gould & Jacobson and Shi on the existence of Hamilton cycles in graphs.

preprint2012arXiv

A note on heterochromatic cycles of length 4 in edge-colored graphs

Let $G$ be an edge-colored graph. A heterochromatic cycle of $G$ is one in which every two edges have different colors. For a vertex $v\in V(G)$ , let $CN(v)$ denote the set of colors which are assigned to the edges incident to $v$ . In this note we prove that $G$ contains a heterochromatic cycle of length 4 if $G$ has $n\geq 60$ vertices and $|CN(u)\cup CN(v)|\geq n-1$ for every pair of vertices $u$ and $v$ of $G$ . This extends a result of Broersma et al. on the existence of heterochromatic cycles of length 3 or 4.

preprint2011arXiv

Boundary Conditions for NHEK through Effective Action Approach

We study the asymptotic symmetry group(ASG) of the near horizon geometry of extreme Kerr black hole through the effective action approach developed in 1007.1031. By requiring a finite boundary effective action, we derive a new set of asymptotic Killing vectors and boundary conditions, which are much more relaxed than the ones proposed in 0907.0303, and still allow a copy of conformal group as its ASG. In the covariant formalism, the asymptotic charges are finite, with the corresponding central charge vanishing. By using the quasi-local charge and introducing a plausible cut-off, we find that the higher order terms of the asymptotic Killing vectors, which could not be determined through the effective action approach, contribute to the central charge as well. We also show that the boundary conditions suggested in 0809.4266 lead to a divergent first order boundary effective action.

preprint2011arXiv

Holographic Q-picture of Kerr-Newman-AdS-dS Black Hole

In this article, we show that a four-dimensional Kerr-Newman-AdS-dS black hole could be described by two different holographic two-dimensional conformal field theories. The first description, in view of the angular momentum, has been well discussed in (arXiv:1006.0157). The other alternative dual picture, however, is somehow overlooked. This new description, in view of the charge, provides another holographic correspondence. This picture again is supported not only by the match of the macroscopic entropy with the counting of microscopic degrees of freedom via the Cardy formula and also by the agreement on the real-time correlator in the superradiant scattering.

preprint2011arXiv

Self-Dual Warped AdS $_3$ Black Holes

We study a new class of solutions of three-dimensional topological massive gravity. These solutions can be taken as non-extremal black holes, with their extremal counterparts being discrete quotients of spacelike warped AdS $_3$ along the $U(1)_L$ isometry. We study the thermodynamics of these black holes and show that the first law is satisfied. We also show that for consistent boundary conditions, the asymptotic symmetry generators form only one copy of the Virasoro algebra with central charge $c_L = \frac{4ν\ell}{G(ν^2+3)}$ , with which the Cardy formula reproduces the black hole entropy. We compute the real-time correlators of scalar perturbations and find a perfect match with the dual CFT predictions. Our study provides a novel example of warped AdS/CFT correspondence: the self-dual warped AdS $_3$ black hole is dual to a CFT with nonvanishing left central charge. Moreover our investigation suggests that the quantum topological massive gravity asymptotic to the same spacelike warped AdS $_3$ in different consistent ways may be dual to different 2D CFTs.

preprint2009arXiv

Real-time correlators in warped AdS/CFT correspondence

We study real-time correlators in the warped AdS/CFT correspondence. We apply the prescription used in the usual AdS/CFT correspondence and obtain the retarded Green's functions for the scalar and vector fields in the spacelike warped and the null warped black hole backgrounds. We find that the retarded Green's functions and the cross sections are well consistent with the predictions from dual CFT. Our results not only support strongly the conjectured warped AdS/CFT correspondence, but also show that the usual relativistic AdS/CFT prescription of obtaining the real-time correlators remain effective in more general backgrounds with anisotropic conformal infinity.

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.

Bo Ning

Research overview

Is this your work?

40 publications

A revisit to Bang-Jensen-Gutin conjecture and Yeo's theorem

A Complete Solution to the Cvetković-Rowlinson Conjecture

Constraints on low-energy effective theories from weak cosmic censorship

Extremal problems of Erdős, Faudree, Schelp and Simonovits on paths and cycles

The stability method, eigenvalues and cycles of consecutive lengths

A Strengthening of Erdős-Gallai Theorem and Proof of Woodall's Conjecture

An Ore-type Condition for Large kkk-factor and Disjoint Perfect Matchings

Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations

The formula for Turán number of spanning linear forests

Exact bipartite Turán numbers of large even cycles

Stability results on the circumference of a graph

Extensions of Erdős-Gallai Theorem and Luo's Theorem with Applications

Cyclability of ididid-cycles in graphs

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

On a conjecture of Chen-Guo-Wang

Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles

Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs

Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions

Spectral radius and Hamiltonian properties of graphs

Spectral radius and traceability of connected claw-free graphs

A note on nowhere-zero 3-flow and Z_3-connectivity

Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

Long-term Stabilization of Fiber Laser Using Phase-locking Technique with Ultra-low Phase Noise and Phase Drift

Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs

On path-quasar Ramsey numbers

Quantum Decoherence with Holography

A long cycle theorem involving Fan-type degree condition and neighborhood intersection

An inductive proof of Straub's q-analogue of Ljunggren's congruence

Notes on q-analogues of a binomial congruence of Glaisher

Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs

Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs

Rainbow triangles in edge-colored graphs

Refined Holographic Entanglement Entropy for the AdS Solitons and AdS black Holes

The Ramsey numbers of paths versus wheels: a complete solution

Two sufficient conditions for the existence of Hamilton cycles in graphs

A note on heterochromatic cycles of length 4 in edge-colored graphs

Boundary Conditions for NHEK through Effective Action Approach

Holographic Q-picture of Kerr-Newman-AdS-dS Black Hole

Self-Dual Warped AdS3_33​ Black Holes

Real-time correlators in warped AdS/CFT correspondence

See the researcher in context

Building this map preview

An Ore-type Condition for Large $k$ -factor and Disjoint Perfect Matchings

Cyclability of $id$ -cycles in graphs

Self-Dual Warped AdS $_3$ Black Holes