Search

In 1980, Akiyama, Exoo, and Harary conjectured that any graph $G$ can be decomposed into at most $\lceil(\Delta(G)+1)/2\rceil$ linear forests. We confirm the conjecture for sufficiently large graphs with large minimum degree. Precisely, we show that for any given $0<\varepsilon <1$, there exists $n_0 \in \mathbb{N}$ for which the following statement holds: If $G$ is a graph on $n\ge n_0$ vertices of minimum degree at least $(1+\varepsilon )n/2$, then $G$ can be decomposed into at most $\lceil(\Delta(G)+1)/2\rceil$ linear forests., Comment: 17pages

Chv\'atal in 1973 introduced the concept of graph toughness and initiated the study of sufficient toughness conditions for the existence of hamiltonian cycles in graphs. Over the years, numerous results related to graph toughness have been proved. Notably, Enomoto, Jackson, Katerinis, and Saito (1985) established a renowned theorem stating that for every integer $k\ge 1$, any $k$-tough graph $G$ possesses a $k$-factor if $k |V(G)|$ is even and $|V(G)|\ge k+1$. In this paper, we initiate the study of toughness conditions for the existence of substructures in hypergraphs. Specifically, we extend the aforementioned result concerning $k$-factors in graphs to Berge-$k$-factors in hypergraphs. The proof of this extension presents a unique challenge due to the inherent non-uniformity of hypergraphs compared to graphs, and our proof techniques are of independent interest for similar investigations., Comment: 13pages

A graph is $P_8$-free if it contains no induced subgraph isomorphic to the path $P_8$ on eight vertices. In 1995, Erd\H{o}s and Gy\'{a}rf\'{a}s conjectured that every graph of minimum degree at least three contains a cycle whose length is a power of two. In this paper, we confirm the conjecture for $P_8$-free graphs by showing that there exists a cycle of length four or eight in every $P_8$-free graph with minimum degree at least three., Comment: 10pages

The toughness of a noncomplete graph $G$ is the maximum real number $t$ such that the ratio of $|S|$ to the number of components of $G-S$ is at least $t$ for every cutset $S$ of $G$, and the toughness of a complete graph is defined to be $\infty$. Determining the toughness for a given graph is NP-hard. Chv\'{a}tal's toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3\cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3\cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chv\'{a}tal's toughness conjecture for $(P_3\cup 2P_1)$-free graphs by showing that every 7-tough $(P_3\cup 2P_1)$-free graph on at least three vertices is hamiltonian., Comment: 12 pages;1 figure

Phase noise of the frequency synthesizer is one of the main limitations to the short-term stability of microwave atomic clocks. In this work, we demonstrated a low-noise, simple-architecture microwave frequency synthesizer for a coherent population trapping (CPT) clock. The synthesizer is mainly composed of a 100 MHz oven controlled crystal oscillator (OCXO), a microwave comb generator and a direct digital synthesizer (DDS). The absolute phase noises of 3.417 GHz signal are measured to be -55 dBc/Hz, -81 dBc/Hz, -111 dBc/Hz and -134 dBc/Hz, respectively, for 1 Hz, 10 Hz, 100 Hz and 1 kHz offset frequencies, which shows only 1 dB deterioration at the second harmonic of the modulation frequency of the atomic clock. The estimated frequency stability of intermodulation effect is 4.7*10^{-14} at 1s averaging time, which is about half order of magnitude lower than that of the state-of-the-art CPT Rb clock. Our work offers an alternative microwave synthesizer for high-performance CPT Rb atomic clock., Comment: 3 pages, 5 figures, 1 table

The coherent population trapping (CPT) atomic clock is very promising for use in next-generation spaceborne applications owing to its compactness and high performance. In this paper, we propose and implement a CPT atomic clock based on the direct modulation of a large-modulation-bandwidth and narrow-linewidth distributed Bragg reflector laser, which replaces the usually used external bulk modulator in the high-performance CPT clock. Our method retains the high performance while significantly reducing the size. Using this highly compact bichromatic light source and simplest CPT configuration, in which a circularly polarized bichromatic laser interrogates the ^{87}Rb atom system, a CPT signal of clock transition with a narrow linewidth and high contrast is observed. We then lock the local oscillator frequency to the CPT error signal and demonstrate a short-term frequency stability of 3.6 \times 10^{-13} {\tau}^{-1/2} (4 s \le {\tau} \le 200 s). We attribute it to the ultralow laser frequency and intensity noise as well as to the high-quality-factor CPT signal. This study can pave the way for the development of compact high-performance CPT clocks based on our scheme., Comment: 6 pages, 11 figures, 1 table

Let $m\ge 1$ be an integer and $G$ be a graph with $m$ edges. We say that $G$ has an antimagic orientation if $G$ has an orientation $D$ and a bijection $\tau:A(D)\rightarrow \{1,2,\cdots,m\}$ such that no two vertices in $D$ have the same vertex-sum under $\tau$, where the vertex-sum of a vertex $u$ in $D$ under $\tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. Hefetz, M\"{u}tze and Schwartz [J. Graph Theory, 64: 219-232, 2010] conjectured that every connected graph admits an antimagic orientation. The conjecture was confirmed for certain classes of graphs such as dense graphs, regular graphs, and trees including caterpillars and $k$-ary trees. In this note, we prove that every lobster admits an antimagic orientation., Comment: 1figure

We report pulsar timing observations carried out in L-band with NTSC's 40-meter Haoping Radio Telescope (HRT), which was constructed in 2014. The observations were carried out using the pulsar machine we developed. Timing observations toward millisecond pulsar J0437-4715 obtains a timing residual (r.m.s) of 397ns in the time span of 284 days. And our observations successfully detected Crab pulsar's glitch that happened on July 23rd, 2019., Comment: 10 pages, 8 figures, accepted for publication in RAA (Res. Astron. Astrophys.)

In 1965, Vizing proved that every planar graph $G$ with maximum degree $\Delta\geq 8$ is edge $\Delta$-colorable. It is also proved that every planar graph $G$ with maximum degree $\Delta=7$ is edge $\Delta$-colorable by Sanders and Zhao, independently by Zhang. In this paper, we extend the above results by showing that every $K_5$-minor free graph with maximum degree $\Delta$ at least seven is edge $\Delta$-colorable., Comment: 14 pages, 1 figure

In 1966, Gallai asked whether all longest paths in a connected graph have a nonempty intersection. The answer to this question is not true in general and various counterexamples have been found. However, there is a positive solution to Gallai's question for many well-known classes of graphs such as split graphs, series parallel graphs, and $2K_2$-free graphs. Among all the graph classes that support Gallai's question, almost all of them were shown to be Hamiltonian under certain conditions. This observation motivates us to investigate Gallai's question in graphs that are "close" to Hamiltonicity properties. Let $\{R,S\}$ be a pair of connected graphs. In particular, in this paper, we show that Gallai's question is affirmative for all connected $\{R,S\}$-free graphs such that every 2-connected $\{R,S\}$-free graph is Hamiltonian. These pairs $\{R,S\}$ were completely characterized in 1990s., Comment: 13 pages,7 figures

The cluster of a crossing in a graph drawing in the plane is the set of the four end-vertices of its two crossed edges. Two crossings are independent if their clusters do not intersect. In this paper, we prove that every plane graph with independent crossings has an equitable partition into $m$ induced forests for any $m\geq 8$. Moreover, we decrease this lower bound 8 for $m$ to 6, 5, 4 and 3 if we additionally assume that the girth of the considering graph is at least 4, 5, 6 and 26, respectively., Comment: 15 Pages

Given a graph $G$ possibly with multiple edges but no loops, denote by $\Delta$ the {\it maximum degree}, $\mu$ the {\it multiplicity}, $\chi'$ the {\it chromatic index} and $\chi_f'$ the {\it fractional chromatic index} of $G$, respectively. It is known that $\Delta\le \chi_f' \le \chi' \le \Delta + \mu$, where the upper bound is a classic result of Vizing. While deciding the exact value of $\chi'$ is a classic NP-complete problem, the computing of $\chi_f'$ is in polynomial time. In fact, it is shown that if $\chi_f' > \Delta$ then $\chi_f'= \max \frac{|E(H)|}{\lfloor |V(H)|/2\rfloor}$, where the maximality is over all induced subgraphs $H$ of $G$. Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) conjectured that $\chi'=\lceil\chi_f'\rceil$ if $\chi'\ge \Delta+2$, which is commonly referred as Goldberg's conjecture. In this paper, we show that if $\chi' >\Delta+\sqrt[3]{\Delta/2}$ then $\chi'=\lceil\chi_f'\rceil$. The previous best known result is for graphs with $\chi'> \Delta +\sqrt{\Delta/2}$ obtained by Scheide, and by Chen, Yu and Zang, independently. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: {\it For any positive integer $m$ with $m\ge 3$, every graph $G$ with $\chi'>\frac{m}{m-1}\Delta+\frac{m-3}{m-1}$ satisfies $\chi'=\lceil\chi_f'\rceil$.} Jakobsen's conjecture has been verified for $m$ up to 15 by various researchers in the last four decades. We show that it is true for $m\le 23$. Moreover, we show that Goldberg's conjecture holds for graphs $G$ with $\Delta\leq 23$ or $|V(G)|\leq 23$., Comment: 21pages