Search

We say that a graph $G$ on $n$ vertices is $\{H,F\}$-$o$-heavy if every induced subgraph of $G$ isomorphic to $H$ or $F$ contains two nonadjacent vertices with degree sum at least $n$. Generalizing earlier sufficient forbidden subgraph conditions for hamiltonicity, in 2012, Li, Ryj\'a\v{c}ek, Wang and Zhang determined all connected graphs $R$ and $S$ of order at least 3 other than $P_3$ such that every 2-connected $\{R,S\}$-$o$-heavy graph is hamiltonian. In particular, they showed that, up to symmetry, $R$ must be a claw and $S\in\{P_4,P_5,C_3,Z_1,Z_2,B,N,W\}$. In 2008, \v{C}ada extended Ryj\'a\v{c}ek's closure concept for claw-free graphs by introducing what we call the $c$-closure for claw-$o$-heavy graphs. We apply it here to characterize the structure of the $c$-closure of 2-connected $\{R,S\}$-$o$-heavy graphs, where $R$ and $S$ are as above. Our main results extend or generalize several earlier results on hamiltonicity involving forbidden or $o$-heavy subgraphs.

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. Let $G$ and $H$ be two graphs. The anti-Ramsey number $\ar(G, H)$ is the maximum number of colors of an edge-coloring of $G$ that does not contain a rainbow copy of $H$. In this paper, we study the anti-Ramsey numbers of $K_k$ in complete multi-partite graphs. We determine the values of the anti-Ramsey numbers of $K_k$ in complete $k$-partite graphs and in balanced complete $r$-partite graphs for $r\geq k$.

Bollob\'as proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs $\ell$ and $k$. In this work we precisely determine the maximum number of edges in a graph containing no cycle of length $0 \bmod 4$.

Chung and Graham considered the problem of minimizing the number of edges in an $n$-vertex graph containing all $n$-vertex trees as a subgraph. They showed that such a graph has at least $\frac{1}{2}n \log{n}$ edges. In this note, we improve this lower estimate to $n \log{n}$., Comment: corrected typos

Bondy and Vince showed that every graph with minimum degree at least three contains two cycles of lengths differing by one or two.We prove the following average degree counterpart that every $n$-vertex graph $G$ with at least $\frac52(n-1)$ edges, unless $4|(n-1)$ and every block of $G$ is a clique $K_5$, contains two cycles of consecutive even lengths. Our proof is mainly based on structural analysis, and a crucial step which may be of independent interest shows that the same conclusion holds for every 3-connected graph with at least 6 vertices. This solves a special case of a conjecture of Verstra\"ete. The quantitative bound is tight and also provides the optimal extremal number for cycles of length two modulo four.

An edge-colored graph is called rainbow if all the colors on its edges are distinct. Given a positive integer n and a graph G, the anti-Ramsey number ar(n,G) is the maximum number of colors in an edge-coloring of K_{n} with no rainbow copy of G. Denote by kC_{3} the union of k vertex-disjoint copies of C_{3}. In this paper, we determine the anti-Ramsey number ar(n,kC_{3}) for n=3k and n\geq2k^{2}-k+2, respectively. When 3k\leq n\leq 2k^{2}-k+2, we give lower and upper bounds for ar(n, kC_{3}).

As the counterpart of classical theorems on cycles of consecutive lengths due to Bondy and Bollob\'as in spectral graph theory, Nikiforov proposed the following open problem in 2008: What is the maximum $C$ such that for all positive $\varepsilon\sqrt{\lfloor\frac{n^2}{4}\rfloor}$ contains a cycle of length $\ell$ for each integer $\ell\in[3,(C-\varepsilon)n]$. We prove that $C\geq\frac{1}{4}$ by a novel method, improving the existing bounds. Besides several novel ideas, our proof technique is partly inspirited by the recent research on Ramsey numbers of star versus large even cycles due to Allen, {\L}uczak, Polcyn and Zhang, and with aid of a powerful spectral inequality. We also derive an Erd\H{o}s-Gallai-type edge number condition for even cycles, which may be of independent interest., Comment: 6 pages, to appear in Journal of Graph Theory(2023). arXiv admin note: substantial text overlap with arXiv:2102.03855

We characterise the pairs of graphs $\{ X, Y \}$ such that all $\{ X, Y \}$-free graphs (distinct from $C_5$) are perfect. Similarly, we characterise pairs $\{ X, Y \}$ such that all $\{ X, Y \}$-free graphs (distinct from $C_5$) are $\omega$-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs $\{ X, Y \}$ for perfectness and $\omega$-colourability of all connected $\{ X, Y \}$-free graphs which are of independence at least $3$, distinct from an odd cycle, and of order at least $n_0$, and similar characterisations subject to each subset of these additional constraints. (The classes are non-hereditary and the characterisations for perfectness and $\omega$-colourability are different.) We build on recent results of Brause et al. on $\{ K_{1,3}, Y \}$-free graphs, and we use Ramsey's Theorem and the Strong Perfect Graph Theorem as main tools. We relate the present characterisations to known results on forbidden pairs for $\chi$-boundedness and deciding $k$-colourability in polynomial time.

Let $\overrightarrow{P_k}$ and $\overrightarrow{C_k}$ denote the directed path and the directed cycle of order $k$, respectively. In this paper, we determine the precise maximum size of $\overrightarrow{P_k}$-free digraphs of order $n$ as well as the extremal digraphs attaining the maximum size for large $n$. For all $n$, we also determine the precise maximum size of $\overrightarrow{C_k}$-free digraphs of order $n$ as well as the extremal digraphs attaining the maximum size. In addition, Huang and Lyu [\textit{Discrete Math. 343(5) 2020}] characterized the extremal digraphs avoiding an orientation of $C_4$. For all other orientations of $C_4$, we also study the maximum size and the extremal digraphs avoiding them., Comment: 20 pages, 10 figures

For positive integers $n>d\geq k$, let $\phi(n,d,k)$ denote the least integer $\phi$ such that every $n$-vertex graph with at least $\phi$ vertices of degree at least $d$ contains a path on $k+1$ vertices. Many years ago, Erd\H{o}s, Faudree, Schelp and Simonovits proposed the study of the function $\phi(n,d,k)$, and conjectured that for any positive integers $n>d\geq k$, it holds that $\phi(n,d,k)\leq \lfloor\frac{k-1}{2}\rfloor\lfloor\frac{n}{d+1}\rfloor+\epsilon$, where $\epsilon=1$ if $k$ is odd and $\epsilon=2$ otherwise. In this paper we determine the values of the function $\phi(n,d,k)$ exactly. This confirms the above conjecture of Erd\H{o}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\H{o}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\H{o}s et al., Comment: 13 pages

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\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\H{o}s-Gallai type edge number condition for even cycles, which may be of independent interest., Comment: 13 pages

A subgraph of an edge-colored graph is rainbow, if all of its edges have different colors. For a graph $G$ and a family $\mathcal{H}$ of graphs, the anti-Ramsey number $ar(G, \mathcal{H})$ is the maximum number $k$ such that there exists an edge-coloring of $G$ with exactly $k$ colors without rainbow copy of any graph in $\mathcal{H}$. In this paper, we study the anti-Ramsey number of $C_{3}$ and $C_{4}$ in the complete $r$-partite graphs. For $r\ge 3$ and $n_{1}\ge n_{2}\ge \cdots\ge n_{r}\ge 1$, we determine $ ar(K_{n_{1}, n_{2}, \ldots, n_{r}},\{C_{3}, C_{4}\}), ar(K_{n_{1}, n_{2}, \ldots, n_{r}}, C_{3})$ and $ar(K_{n_{1}, n_{2}, \ldots, n_{r}}, C_{4})$., Comment: 12 pages

Web-scale applications can ship code on a daily to weekly cadence. These applications rely on online metrics to monitor the health of new releases. Regressions in metric values need to be detected and diagnosed as early as possible to reduce the disruption to users and product owners. Regressions in metrics can surface due to a variety of reasons: genuine product regressions, changes in user population, and bias due to telemetry loss (or processing) are among the common causes. Diagnosing the cause of these metric regressions is costly for engineering teams as they need to invest time in finding the root cause of the issue as soon as possible. We present Lumos, a Python library built using the principles of AB testing to systematically diagnose metric regressions to automate such analysis. Lumos has been deployed across the component teams in Microsoft's Real-Time Communication applications Skype and Microsoft Teams. It has enabled engineering teams to detect 100s of real changes in metrics and reject 1000s of false alarms detected by anomaly detectors. The application of Lumos has resulted in freeing up as much as 95% of the time allocated to metric-based investigations. In this work, we open source Lumos and present our results from applying it to two different components within the RTC group over millions of sessions. This general library can be coupled with any production system to manage the volume of alerting efficiently.

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\H{o}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\H{o}s-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Koml\'{o}s-S\'{o}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., Comment: 16 pages, to appear in Journal of Combinatorial Theory, Series B

For a graph $G$, the $t$-th power $G^t$ is the graph on $V(G)$ such that two vertices are adjacent if and only if they have distance at most $t$ in $G$; and the $t$-th bi-power $G_B^t$ is the graph on $V(G)$ such that two vertices are adjacent if and only if their distance in $G$ is odd at most $t$. Fleischner's theorem states that the square of every 2-connected finite graph has a Hamiltonian cycle. Georgakopoulos prove that the square of every 2-connected infinite locally finite graph has a Hamiltonian circle. In this paper, we consider the Hamiltonicity of the bi-power of bipartite graphs. We show that for every connected finite bipartite graph $G$ with a perfect matching, $G_B^3$ has a Hamiltonian cycle. We also show that if $G$ is a connected infinite locally finite bipartite graph with a perfect matching, then $G_B^3$ has a Hamiltonian circle., Comment: 11 pages

A circle of an infinite locally finite graph $G$ is the imagine of a homeomorphic mapping of the unit circle $S^1$ in $|G|$, the Freudenthal compactification of $G$. A circle of $G$ is Hamiltonian if it meets every vertex (and then every end) of $G$. In this paper, we study a method for finding Hamiltonian circles of graphs. We illustrate this by extending several results on finite graphs to Hamiltonian circles in infinite graphs. For example, we prove that the prism of every 3-connected cubic graph has a Hamiltonian circle, extending the result of the finite case by Paulraja., Comment: 22 pages

Let the bipartite Tur\'an 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\"{o}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., Comment: Revised version; 16 pages

Let $\mathcal{F}$ be a family of subsets of $[n]=\{1,\ldots,n\}$ and let $L$ be a set of nonnegative integers. The family $\mathcal{F}$ is \emph{$L$-intersecting} if $|F\cap F'|\in L$ for every two distinct members $F,F'\in\mathcal{F}$; and $\mathcal{F}$ is $k$-uniform if all its members have the same size $k$. A large variety of problems and results in extremal set theory concern on $k$-uniform $L$-intersecting families. Many attentions are paid to finding the maximum size of a family among all $k$-uniform $L$-intersecting families with prescribed $n,k$ and $L$. In this paper, from another point of view, we propose and investigate the problem of estimating the maximum size of a member in a family among all uniform $L$-intersecting families with size $m$, here $n,m$ and $L$ are prescribed. Our results aim to find out more precise relations of $n,m,k$ and $L$., Comment: 18 pages

Let $k,l$ be two positive integers. An $S_{k,l}$ is a graph obtained from disjoint $K_{1,k}$ and $K_{1,l}$ by adding an edge between the $k$-degree vertex in $K_{1,k}$ and the $l$-degree vertex in $K_{1,l}$. An {\em $S_{k,l}$-free} graph is a graph containing no induced subgraph isomorphic to $S_{k,l}$. In this note, we show that, for any positive integers $k,l$ with $2\leqslant k\leqslant l$, there exists a constant $c=c(k,l)$ such that every connected balanced $S_{k,l}$-free bipartite graph with minimum degree at least $c$ contains a connected $k$-factor.

For an arc-colored digraph $D$, define its {\em kernel by rainbow paths} to be a set $S$ of vertices such that (i) no two vertices of $S$ are connected by a rainbow path in $D$, and (ii) every vertex outside $S$ can reach $S$ by a rainbow path in $D$. In this paper, we show that it is NP-complete to decide whether an arc-colored tournament has a kernel by rainbow paths, where a {\em tournament} is an orientation of a complete graph. In addition, we show that every arc-colored $n$-vertex tournament with all its strongly connected $k$-vertex subtournaments, $3\leq k\leq n$, colored with at least $k-1$ colors has a kernel by rainbow paths, and the number of colors required cannot be reduced.

In 1962, Erd\H{o}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., Comment: 14 pages, 2 figures, Version 2 differs from Version 1 in improved presentation, to appear in Linear Algebra and Its Applications

Understanding how the cycles of a graph or digraph behave in general has always been an important point of graph theory. In this paper, we study the question of finding a set of $k$ vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every $k \geq 1$, every graph with minimum degree at least $\frac{k^2+5k-2}{2}$ has $k$ vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider stronger situations, and exhibit degree bounds (some of which are best possible) when e.g. the graph is triangle-free, or the $k$ cycles are requested to have different lengths congruent to some values modulo some $r$. In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have $k$ vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for regular digraphs and digraphs of small order.

Broersma and Veldman proved that every 2-connected claw-free and $P_6$-free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and $P_6$-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and $P_6$-\emph{o}-heavy but not hamiltonian. In this paper we further give some Ore-type degree conditions restricting to induced $P_6$'s of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results., Comment: 12 pages, 3 figures

Let $G$ be a graph. Adopting the terminology of Broersma et al. and \v{C}ada, respectively, we say that $G$ is 2-heavy if every induced claw ($K_{1,3}$) of $G$ contains two end-vertices each one has degree at least $|V(G)|/2$; and $G$ is o-heavy if every induced claw of $G$ contains two end-vertices with degree sum at least $|V(G)|$ in $G$. In this paper, we introduce a new concept, and say that $G$ is \emph{$S$-c-heavy} if for a given graph $S$ and every induced subgraph $G'$ of $G$ isomorphic to $S$ and every maximal clique $C$ of $G'$, every non-trivial component of $G'-C$ contains a vertex of degree at least $|V(G)|/2$ in $G$. In terms of this concept, our original motivation that a theorem of Hu in 1999 can be stated as every 2-connected 2-heavy and $N$-c-heavy graph is hamiltonian, where $N$ is the graph obtained from a triangle by adding three disjoint pendant edges. In this paper, we will characterize all connected graphs $S$ such that every 2-connected o-heavy and $S$-c-heavy graph is hamiltonian. Our work results in a different proof of a stronger version of Hu's theorem. Furthermore, our main result improves or extends several previous results., Comment: 21 pages, 6 figures, finial version for publication in Discussiones Mathematicae Graph Theory

In 1962, Erd\H{o}s proved that if a graph $G$ with $n$ vertices satisfies $$ e(G)>\max\left\{\binom{n-k}{2}+k^2,\binom{\lceil(n+1)/2\rceil}{2}+\left\lfloor \frac{n-1}{2}\right\rfloor^2\right\}, $$ where the minimum degree $\delta(G)\geq k$ and $1\leq k\leq(n-1)/2$, then it is Hamiltonian. For $n \geq 2k+1$, let $E^k_n=K_{k}\vee (kK_1+K_{n-2k})$, where "$\vee$" is the "join" operation. One can observe $e(E^k_n)=\binom{n-k}{2}+k^2$ and $E^k_n$ is not Hamiltonian. As $E^k_n$ contains induced claws for $k\geq 2$, a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erd\H{o}s' theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryj\'a\v{c}ek's claw-free closure theory and Brousek's characterization of minimal 2-connected claw-free non-Hamiltonian graphs., Comment: 22 pages, 8 figures, to appear in Discrete Mathematics

In 1962, Erd\H{o}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\H{o}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., Comment: 21 pages; 3 figures; to appear in Linear and Multilinear Algebra

For two given graphs $G_1$ and $G_2$, 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 $\bar{G}$ contains a $G_2$. In this note, we determined the Ramsey number $R(K_{1,n},W_m)$ for even $m$ with $n+2\leq m\leq 2n-2$, where $W_m$ is the wheel on $m+1$ vertices, i.e., the graph obtained from a cycle $C_m$ by adding a vertex $v$ adjacent to all vertices of the $C_m$., Comment: 8 pages

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., Comment: 11 pages, 2 figures, to appear in Acta Math. Sin. (Engl. Ser.)

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., Comment: 12 pages, Accepted version for publication in Graphs and Combinatorics. arXiv admin note: text overlap with arXiv:1506.02795

Let $G$ be a connected claw-free graph on $n$ vertices and $\overline{G}$ be its complement graph. Let $\mu(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 $\mu(G)\geq n-4$, then $G$ is traceable unless $G=N_{n-3,3}$. (2) If $\mu(\overline{G})\leq \mu(\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., Comment: 12 pages,3 figures,to appear in FLOMAT

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., Comment: 7 pages

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., Comment: 32 pages, 1 table

A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all its vertices. Let $G$ be a graph on $n$ vertices. $G$ is called claw-$o_{-1}$-heavy if every induced claw ($K_{1,3}$) of $G$ has a pair of nonadjacent vertices with degree sum at least $n-1$ in $G$. In this paper we show that a claw-$o_{-1}$-heavy graph $G$ is traceable if we impose certain additional conditions on $G$ involving forbidden induced subgraphs., Comment: 12 pages, 2 figures

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., Comment: Title slightly changed. 13 pages, to appear in European J. Combin

A weighted graph is a graph in which every edge is assigned a non-negative real number. In a weighted graph, the weight of a path is the sum of the weights of its edges, and the weighed degree of a vertex is the sum of the weights of the edges incident with it. In this paper we give three weighted degree conditions for the existence of heavy or Hamilton paths with one or two given end-vertices in 2-connected weighted graphs.

Let $G$ be a graph on $n$ vertices. A vertex of $G$ with degree at least $n/2$ is called a heavy vertex, and a cycle of $G$ which contains all the heavy vertices of $G$ is called a heavy cycle. In this paper, we characterize the graphs which contain no heavy cycles. For a given graph $H$, we say that $G$ is $H$-\emph{heavy} if every induced subgraph of $G$ isomorphic to $H$ contains two nonadjacent vertices with degree sum at least $n$. We find all the connected graphs $S$ such that a 2-connected graph $G$ being $S$-heavy implies any longest cycle of $G$ is a heavy cycle.

A weighted digraph is a digraph such that every arc is assigned a nonnegative number, called the weight of the arc. The weighted outdegree of a vertex $v$ in a weighted digraph $D$ is the sum of the weights of the arcs with $v$ as their tail, and the weight of a directed cycle $C$ in $D$ is the sum of the weights of the arcs of $C$. In this note we prove that if every vertex of a weighted digraph $D$ with order $n$ has weighted outdegree at least 1, then there exists a directed cycle in $D$ with weight at least $1/\log_2 n$. This proves a conjecture of Bollob\'{a}s and Scott up to a constant factor.

For nonnegative integers $k$ and $l$, let $\mathscr{D}(k,l)$ denote the family of digraphs in which every vertex has either indegree at most $k$ or outdegree at most $l$. In this paper we prove that the edges of every digraph in $\mathscr{D}(3,3)$ and $\mathscr{D}(4,4)$ can be covered by at most five directed cuts and present an example in $\mathscr{D}(3,3)$ showing that this result is best possible.

Let $G$ be a $k$-connected graph with $k\geq 2$. In this paper we first prove that: For two distinct vertices $x$ and $z$ in $G$, it contains a path passing through its any $k-2$ {specified} vertices with length at least the average degree of the vertices other than $x$ and $z$. Further, with this result, we prove that: If $G$ has $n$ vertices and $m$ edges, then it contains a cycle of length at least $2m/(n-1)$ passing through its any $k-1$ specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erd\"os and Gallai on the existence of long cycles under the average degree condition.

Let $G$ be a graph on $n$ vertices. An induced subgraph $H$ of $G$ is called heavy if there exist two nonadjacent vertices in $H$ with degree sum at least $n$ in $G$. We say that $G$ is $H$-heavy if every induced subgraph of $G$ isomorphic to $H$ is heavy. For a family $\mathcal{H}$ of graphs, $G$ is called $\mathcal{H}$-heavy if $G$ is $H$-heavy for every $H\in\mathcal{H}$. In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ (the path on three vertices) such that every 2-connected $\{R,S\}$-heavy graph is Hamiltonian. This extends several previous results on forbidden subgraph conditions for Hamiltonian graphs.