\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.21}{22(3)}{2015}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


\usepackage{graphicx,float,color,fancybox,shapepar,setspace}
\usepackage{amsmath, amsfonts, amssymb, amsthm}
\usepackage{subfigure,pdfsync}
\usepackage{fancyhdr}
%\oddsidemargin 25pt \evensidemargin 0pt
%\textheight 21.5 true cm \textwidth 14.5 true cm
%\voffset -1.5cm
\newcommand {\ora}{\overrightarrow}
\newcommand {\ola}{\overleftarrow}
\newcommand {\no}{\noindent}
\def \ss{\subseteq}
\newcommand {\ol}{\overline}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


%\parskip 0.3 cm
%\def\baselinestretch{1.1}




\title{\bf Closing the gap on path-kipas Ramsey numbers \\
{\it\small We dedicate this paper to the memory of Ralph Faudree,\\
one of the exponents of Ramsey theory who died on January 13, 2015\\[-1ex]}}


\author{Binlong Li\thanks{The first author is partly supported by the
Doctorate Foundation of Northwestern Polytechnical University (No.
cx201202) and  by the project NEXLIZ-CZ.1.07/2.3.00/30.0038, which is co-financed by the European Social Fund and the state budget of the Czech Republic.}\\
\small $ \begin{array}{cc} \mbox{Department of Mathematics} \qquad & \quad \mbox{Department of Applied Mathematics} \\   
\mbox{University of West Bohemia} \qquad & \quad \mbox{Northwestern Polytechnical University} \\   
\mbox{European Centre of Excellence NTIS -} \qquad & \quad \mbox{Xi'an, Shaanxi 710072, P.R.~China} \\   
\mbox{New Technologies for the Inf. Society} \qquad &  \\ 
\mbox{306 14 Pilsen, Czech Rep.} & \\ 
\end{array} $ \\
\small \tt libinlong@mail.nwpu.edu.cn \\
\and 
Yanbo Zhang \\
\small $ \begin{array}{cc} \mbox{Faculty of Electrical Engineering}  \qquad & \quad  \mbox{Department of Mathematics} \\  
\mbox{University of Twente} \qquad & \quad \mbox{Nanjing University} \\  
\mbox{ 7500 AE Enschede, The Netherlands} \qquad & \quad \mbox{Nanjing 210093, P.R. China} \\  
\end{array} $ \\ 
\small \tt y.zhang@utwente.nl \\
\and 
Halina Bielak \\
\small Institute of Mathematics   \\ [-0.8ex]
\small  Maria Curie-Sklodowska University   \\ [-0.8ex]
\small 20-031 Lublin, Poland \\
\small  \tt hbiel@hektor.umcs.lublin.pl  \\ 
\and 
Hajo Broersma \\
\small Faculty of Electrical Engineering, \\ [-0.8ex] 
\small Mathematics and Computer Science \\ [-0.8ex] 
\small University of Twente \\ [-0.8ex] 
\small P.O. Box 217, 7500 AE Enschede, The Netherlands \\
\small \tt h.j.broersma@utwente.nl \\
\and
P\v remysl Holub \thanks{Research partly supported by project P202/12/G061 of the Czech Science Foundation.} \\
\small Department of Mathematics \\ [-0.8ex] 
\small University of West Bohemia \\ [-0.8ex]
\small P.O. Box 314, 306 14 Pilsen, Czech Republic\\
\small \tt holubpre@kma.zcu.cz \\
}
 
\date{\dateline{Jan 30, 2015}{Jul 26, 2015}{Aug 14, 2015}\\
\small Mathematics Subject Classifications: 05C55, 05D10} 
 
\begin{document}

\maketitle

\begin{abstract}

Given two graphs $G_1$ and $G_2$, the Ramsey number $R(G_1, G_2)$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G_1$ is a subgraph of $G$, or $G_2$ is a subgraph of the complement of $G$. Let $P_n$ denote a path of order $n$ and $\widehat{K}_m$ a kipas of order $m+1$, i.e., the graph obtained from a $P_m$ by adding one new vertex $v$ and edges from $v$ to all vertices of the $P_m$.
%%%%%
We close the gap in existing knowledge on exact values of
the Ramsey numbers $R(P_n,\widehat{K}_m)$ by determining the exact values for
the remaining open cases.
% for all $n,m$. Here we present a considerably shorter proof.

\bigskip
{\bf Keywords:} Ramsey number; path; kipas
\smallskip
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Introduction}

We only consider finite simple graphs. A cycle, a path and a complete graph of order $n$ are denoted by $C_n$, $P_n$ and $K_n$, respectively. A complete $k$-partite graph with classes of cardinalities $n_1,n_2,\ldots,n_k$ is denoted by $K_{n_1,n_2,\ldots,n_k}$. For a nonempty proper subset $S\ss V(G)$, let $G[S]$ and $G-S$ denote the subgraph induced by $S$ and $V(G)-S$, respectively. For a vertex $v\in V(G)$, we let $N_S(v)$ denote the
set of neighbors of $v$ that are contained in $S$. For two vertex-disjoint graphs $H_1,H_2$, we define $H_1+H_2$ to be the graph with vertex set $V(H_1)\cup V(H_2)$ and edge set $E(H_1)\cup E(H_2)\cup \{uv~|~u\in V(H_1)$ and $v\in V(H_2)\}$. For two disjoint vertex sets $X,Y$, $e(X,Y)$ denotes the number of edges with one end in $X$ and one end in $Y$. We use $mG$ to denote $m$ vertex-disjoint copies of $G$. A star $K_{1,n}=K_1+nK_1$, a kipas $\widehat{K}_n=K_1+P_n$ and a wheel $W_n=K_1+C_n$.
%%%%
The term kipas and its notation were adopted from \cite{SB}. Kipas is the Malay word for fan; the motivation for the term kipas is that the graph $K_1+P_n$ looks like a hand fan (especially if the path $P_n$ is drawn as part of a circle) but the term fan was already in use for the graphs $K_1+nK_2$.

We use $\delta(G)$ and $\Delta(G)$ to denote the minimum and maximum degree of $G$, respectively.

Given two graphs $G_1$ and $G_2$, the Ramsey number $R(G_1,G_2)$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G$ contains $G_1$ or $\ol G$ contains $G_2$, where $\ol G$ is the complement of $G$. It is easy to check that $R(G_1,G_2)=R(G_2,G_1)$, and, if $G_1$ is a subgraph of $G_3$, then $R(G_1,G_2)\leq R(G_3,G_2)$. Thus, $R(P_n,K_{1,m})\leq R(P_n,\widehat{K}_m)\leq R(P_n,W_m)$. In \cite{RJ}, an explicit formula for $R(P_n,K_{1,m})$ is given, while in \cite{LN}, the Ramsey numbers $R(P_n,W_m)$ for all $m,n$ have been obtained. It follows from these results that $R(P_n,K_{1,m})=R(P_n,W_m)$ for $m\geq 2n$. Therefore, $R(P_n,\widehat{K}_m)=R(P_n,K_{1,m})=R(P_n,W_m)$ for $m\geq 2n$, and the exact values of these Ramsey numbers can be found in both \cite{LN} and \cite{RJ}.

It is trivial that $R(P_1,\widehat{K}_m)=1$ and $R(P_n,\widehat{K}_1)=n$. Many nontrivial exact values for  $R(P_n,\widehat{K}_m)$ have been obtained by Salman and Broersma in \cite{SB}.
%%%%%
Here we completely solve the case by determining all the remaining path-kipas Ramsey numbers.
%Very recently, all path-kipas Ramsey numbers were determined by Li et al. in \cite{LBH}.
%%%%%
$R(P_n,\widehat{K}_m)$ can easily be determined for $m\geq 2n$ (and follows directly from earlier results, as indicated above).
%most of the content in \cite{LBH} focusses on $R(P_n,\widehat{K}_m)$ for $m\leq 2n-1$ and $m,n\geq 2$.
%%%%%%%
In this note we close the gap by proving
%give a considerably shorter proof of the same result, which is
the following theorem.



%Very recently, all path-kipas Ramsey numbers were determined by Li et al. in \cite{LBH}. Since $R(P_n,\widehat{K}_m)$ can easily be determined for $m\geq 2n$ (and follows directly from earlier results, as indicated above), most of the content in \cite{LBH} focusses on determining $R(P_n,\widehat{K}_m)$ for $m\leq 2n-1$ and $m,n\geq 2$. In the next section we give a considerably shorter proof for the same result, which is the following theorem.

\begin{theorem}\label{main}
$R(P_n,\widehat{K}_m)=\max\{2n-1,\lceil 3m/2\rceil-1,2\lfloor m/2\rfloor+n-2\}$ for $m\leq 2n-1$ and $m,n\geq 2$.
\end{theorem}

%We postpone our proof of this result to the next section.

\section{Proof of Theorem \ref{main}}

We first list the following eight useful results that we will use in our proof of Theorem \ref{main}, as separate lemmas.

\begin{lemma}\label{GG}
(Gerencs\'{e}r and Gy\'{a}rf\'{a}s \cite{GG}). For $m\geq n\geq 2$, $R(P_m,P_n)=m+\lfloor n/2\rfloor-1$.
\end{lemma}

\begin{lemma}\label{FLPS}
(Faudree et al. \cite{FLPS}). For $n\ge 2$ and even $m\geq 4$, $R(C_m,P_n)=\max\{m+\lfloor n/2\rfloor-1,n+m/2-1\}$.
\end{lemma}

\begin{lemma}\label{P}
(Parsons \cite{P}). For $n\geq m\geq 2$, $R(K_{1,m},P_n)=\max\{2m-1,n\}$.
\end{lemma}

\begin{lemma}\label{SB}
(Salman and Broersma \cite{SB}). $R(P_4,\widehat{K}_6)=8$.
\end{lemma}

\begin{lemma}\label{D}
(Dirac \cite{D}). If $G$ is a connected graph, then $G$ contains a path of order at least $\min\{2\delta(G)+1,|V(G)|\}$.
\end{lemma}

\begin{lemma}\label{Bo}
(Bondy \cite{Bo}). If $\delta(G)\geq |V(G)|/2$, then $G$ contains cycles of every length between $3$ and $|V(G)|$, or $r=|V(G)|/2$ and $G=K_{r,r}$.
\end{lemma}

\begin{lemma}\label{ZZC}
(Zhang et al. \cite{ZZC}). Let $C$ be a longest cycle of a graph $G$ and $v_1, v_2\in V(G)-V(C)$. Then $|N_{V(C)}(v_1)\cup N_{V(C)}(v_2)|\leq \lfloor |V(C)|/2\rfloor +1$.
\end{lemma}

\begin{lemma}\label{ourlemma}
Let $G$ be a graph with $|V(G)|\geq 6$ and $\delta (G)\geq 2$. Then $G$ contains two vertex-disjoint paths, one with order three and one with order two.
\end{lemma}

\begin{proof}
If $G$ is connected, by Lemma \ref{D}, $G$ contains a path of order at least $5$. Let $x_1x_2x_3x_4x_5$ be a path in $G$. Then $G$ contains two vertex-disjoint paths $x_1x_2x_3$ and $x_4x_5$. If $G$ is disconnected, then each component of $G$ contains a path of order three. This completes the proof of Lemma~\ref{ourlemma}.
\end{proof}

\noindent
We proceed to prove Theorem \ref{main}. Let $N=\max\{2n-1,\lceil 3m/2\rceil-1,2\lfloor m/2\rfloor+n-2\}$, and let $m\leq 2n-1$ and $m,n\geq 2$. It suffices to show that $R(P_n,\widehat{K}_m)=N$.

If $n=2$, then $m\leq 2n-1$ and $m,n\geq 2$ imply $m=2$ or $m=3$. It is obvious that $R(P_2,\widehat{K}_m)=m+1$, and one easily checks that $m+1=N$ for these values of $m$ and $n$. Next we assume that $n\geq 3$. We first show that $R(P_n,\widehat{K}_m)\geq N$.
For this purpose, we note that it is straightforward to check that any of the graphs $G\in \{K_{n-1,n-1},K_{\lfloor m/2\rfloor,\lceil m/2\rceil-1,\lceil m/2\rceil-1},K_{n-1,\lfloor m/2\rfloor-1,\lfloor m/2\rfloor-1}\}$ contains no $\widehat{K}_m$, whereas $\ol G$ contains no $P_n$. Thus, $R(P_n,\widehat{K}_m)\geq \max\{2n-1,\lceil 3m/2\rceil-1,2\lfloor m/2\rfloor+n-2\}=N$.

It remains to prove $R(P_n,\widehat{K}_m)\leq N$. To the contrary, we assume  there exists a graph $G$ of order $N$ such that neither $G$ contains a $\widehat{K}_m$, nor $\ol G$ contains a $P_n$.

We first claim that $\Delta(G)\geq N-\lfloor n/2\rfloor$. To prove this claim, assume to the contrary that $\Delta(G)\leq N-\lfloor n/2\rfloor-1$. Then $\delta(\ol G)\geq \lfloor n/2\rfloor$. Let $H$ be a largest component of $\ol G$. If $|V(H)|\geq n$, then, since $\delta(H)\geq \lfloor n/2\rfloor$, $H$ contains a $P_n$ by Lemma \ref{D}, a contradiction. Thus, $|V(H)|\leq n-1$ and $|V(G)|-|V(H)|\geq N-n+1$. Since $m\leq 2n-1$, we have $n\geq \lfloor m/2\rfloor$. From the definition of $N$ we get that $N-n+1\geq n$ and $N-n+1\geq 2\lfloor m/2\rfloor-1$, so $N-n+1\geq \max\{2\lfloor m/2\rfloor-1,n\}$. Since $\ol G-V(H)$ contains no $P_n$, by Lemma \ref{P},
%$R(P_n,K_{1,\lfloor m/2\rfloor})=\max\{2\lfloor m/2\rfloor-1,n\}$.then
$G-V(H)$ contains a $K_{1,\lfloor m/2\rfloor}$. If $|V(H)|\geq \lceil m/2\rceil$, since every vertex of $V(H)$ is adjacent to every vertex of $V(G)-V(H)$ in $G$, then $G$ contains a $\widehat{K}_m$, a contradiction. This implies that $|V(H)|\leq \lceil m/2\rceil-1$. Recall that $H$ is a largest component of $\ol G$. Thus $\ol G$ contains at least four components; otherwise $|V(\ol G)|\leq 3(\lceil m/2\rceil-1)<\lceil 3m/2\rceil-1\leq N$, a contradiction. Let $H'$ be a smallest component of $\ol G$. Then $|V(H')|\leq N/4$ and $|V(G)|-|V(H')|\geq 3N/4\geq 3/4(\lceil 3m/2\rceil-1)\geq 9m/8-3/4 > m-3/4$. That is, $|V(G)|-|V(H')|\geq m$. Since every component in $\ol G-V(H')$ is of order at most $\lceil m/2\rceil-1$, then every vertex in $\ol G-V(H')$ is of degree at most $\lceil m/2\rceil-2$. Thus, we have $\delta(G-V(H'))>(|V(G)|-|V(H')|)/2$. By Lemma \ref{Bo}, $G-V(H')$ contains a $P_m$, which together with any vertex of $V(H')$ forms a $\widehat{K}_m$ in $G$, a contradiction. This proves our claim that $\Delta(G)\geq N-\lfloor n/2\rfloor$.

Let $u$ be a vertex of $G$ with $d(u)=d=\Delta(G)$, let $F=G[N(u)]$ and $Z=V(G)-V(F)-\{u\}$. Then $|V(F)|=d\geq N-\lfloor n/2\rfloor=\max\{n+\lceil n/2\rceil-1,\lceil 3m/2\rceil-\lfloor n/2\rfloor-1,2\lfloor m/2\rfloor+\lceil n/2\rceil-2\}$. We claim that $R(P_m,P_n)>d$; otherwise $R(P_m,P_n)\leq d$, and either $F$ contains a $P_m$, which together with $u$ forms a $\widehat{K}_m$, a contradiction; or $\ol F$ contains a $P_n$, also a contradiction. If $m\leq n$, or if $m=n+1$ and $m$ is even, then by Lemma \ref{GG}, $R(P_m,P_n)=\max\{n+\lfloor m/2\rfloor-1,m+\lfloor n/2\rfloor-1\}\leq n+\lceil n/2\rceil-1\leq d$, a contradiction. Therefore, it remains to deal with the cases that $m\geq n+2$, and that $m=n+1$ and $m$ is odd. We first deal with the latter case.

Let $m=n+1$ and $m$ is odd. Then $n$ is even, hence $n\geq 4$. We claim that $|Z|\geq 1$; otherwise $d=N-1=2n-2$, and then $R(P_m,P_n)=m+n/2-1\leq 2n-2=d$ by Lemma \ref{GG}, a contradiction. By Lemma \ref{FLPS}, $R(C_{m-1},P_n)=m-1+n/2-1=n+n/2-1\leq d$. Since $\ol F$ contains no $P_n$, then $F$ contains a $C_{m-1}$. Let $C_{m-1}=x_1x_2\ldots x_{m-1}x_1$, $Y=V(F)-V(C_{m-1})=\{y_1,y_2,\ldots,y_k\}$. Then $k\geq n/2-1$. If $e(V(C_{m-1}),Y)\geq 1$, say $x_1y_1\in E(G)$, then $y_1x_1x_2\ldots x_{m-1}$ is a path in $G$, which together with $u$ forms a $\widehat{K}_m$, a contradiction. Thus, $e(V(C_{m-1}),Y)=0$. If there is an edge in $\ol G[V(C_{m-1})]$, say $x_ix_j\in E(\ol G)$ $(1\leq i<j\leq m-1)$, then $x_ix_jy_1x_1'y_2x_2'\ldots y_{n/2-1}x_{n/2-1}'$ with $\{x'_k: 1\leq k\leq n/2-1\}\ss  V(C_{m-1})-\{x_i,x_j\}$ is a path of order $n$ in $\ol G$, a contradiction. Thus, $G[V(C_{m-1})]$ is a complete graph. Set $z\in Z$. If $e(\{z\},V(C_{m-1}))\geq 1$ in $\ol G$, say $zx_1\in E(\ol G)$, then $uzx_1y_1\ldots x_{n/2-1}y_{n/2-1}$ is a path of order $n$ in $\ol G$, a contradiction. Thus, $e(\{z\},V(C_{m-1}))=0$ in $\ol G$, and $G$ contains a path $ux_1zx_2x_3\ldots x_{m-2}$, which together with $x_{m-1}$ forms a $\widehat{K}_m$, another contradiction. This completes the case that $m=n+1$ and $m$ is odd. We proceed with the case that $n+2\leq m\leq 2n-1$, and first consider the small values of $n$.

For $n=3$ and $m=5$, or $n=4$ and $m=7$, or $n=5$ and $7\leq m\leq 9$, we get that $R(P_m,P_n)=m+\lfloor n/2\rfloor-1\leq \lceil 3m/2\rceil-\lfloor n/2\rfloor-1\leq d$, a contradiction. By Lemma \ref{SB}, $R(P_4,\widehat{K}_6)=8=N$. Hence it remains to consider the case that $m\geq n+2\geq 8$.

We first claim that $|Z|\geq 2$. If not, $|Z|\leq 1$ and $d=N-1-|Z|\geq N-2$. By Lemma \ref{GG}, $R(P_m,P_n)=m+\lfloor n/2\rfloor-1$. If $m\geq n+3$, then $m+\lfloor n/2\rfloor-1\leq \lceil 3m/2\rceil-3\leq N-2\leq d$, a contradiction; if $n\geq 7$ or $(n,m)=(6,8)$, then $m+\lfloor n/2\rfloor-1\leq 2\lfloor m/2\rfloor+n-4\leq N-2\leq d$, also a contradiction. Thus, for $m\geq n+2\geq 8$, we have $|Z|\geq 2$.

Since $m\geq n+2\geq 8$, by Lemma \ref{FLPS}, $R(C_{2\lfloor m/2\rfloor-2},P_n)=\max\{2\lfloor m/2\rfloor+\lfloor n/2\rfloor-3, n+\lfloor m/2\rfloor-2\}<2\lfloor m/2\rfloor+\lceil n/2\rceil-2\leq d$. Since $\ol F$ contains no $P_n$, $F$ contains a $C_{2\lfloor m/2\rfloor-2}$. Let $C$ be a longest cycle in $F$. Then $|V(C)|\geq m-3$. If $|V(C)|\geq m$, then $F$ contains a $P_m$, which together with $u$ forms a $\widehat{K}_m$ in $G$, a contradiction. Thus, $m-3\leq |V(C)|\leq m-1$. We complete the proof by distinguishing the three cases that $|V(C)|=m-1$, $|V(C)|=m-2$ or $|V(C)|=m-3$. In each case, let $C=x_1x_2\ldots x_{|V(C)|}x_1$ and $Y=V(F)-V(C)=\{y_1,y_2,\ldots,y_k\}$.

\medskip\noindent
{\bf Case 1}: $|V(C)|=m-1$.

\noindent
We have $k=d-(m-1)\geq \lceil n/2\rceil-2$. If $e(V(C),Y)\geq 1$, say $x_1y_1\in E(G)$, then $y_1x_1x_2\ldots x_{m-1}$ is a path in $G$, which together with $u$ forms a $\widehat{K}_m$, a contradiction. Thus, $e(V(C),Y)=0$. Let $z_1,z_2\in Z$. If $e(\{z_1\},V(C))\geq 1$ in $\ol G$, say $z_1x_1\in E(\ol G)$, then $z_2uz_1x_1y_1\ldots x_{\lceil n/2\rceil-2}y_{\lceil n/2\rceil-2}x_{\lceil n/2\rceil-1}$ is a path of order at least $n$ in $\ol G$, a contradiction. This implies that $e(\{z_1\},V(C))=0$ in $\ol G$. For the same reason, $e(\{z_2\},V(C))=0$ in $\ol G$.

We claim that $\delta(\ol G[V(C)])\leq 1$. If not, $\delta(\ol G[V(C)])\geq 2$. Since $m\geq 8$, by Lemma \ref{ourlemma}, there are two vertex-disjoint paths in $\ol G[V(C)]$, one with order three and one with order two. Without loss of generality, let $x'_1x'_2x'_3$ and $x'_4x'_5$ be the two paths in $\ol G[V(C)]$. Because $m-1\geq \lceil n/2\rceil+2$, we may assume that $x'_6,\ldots,x'_{\lceil n/2\rceil+2}\in V(C)-\{x'_1,\ldots,x'_5\}$. Then $x'_1x'_2x'_3y_1x'_4x'_5y_2x'_6y_3\ldots x'_{\lceil n/2\rceil+1}y_{\lceil n/2\rceil-2}x'_{\lceil n/2\rceil+2}$ is a path of order at least $n$ in $\ol G$, a contradiction. This proves our claim that $\delta(\ol G[V(C)])\leq 1$. That is, there exists a vertex of $V(C)$ which is adjacent to at least $|V(C)|-2$ vertices of $V(C)$. Without loss of generality, let $x_1$ be a vertex with maximum degree in $G[V(C)]$, and let $x_3$ be the possible vertex that is nonadjacent to $x_1$. Then $ux_2z_1x_4z_2x_5x_6\ldots x_{m-1}$ is a path of order $m$, which together with $x_1$ forms a $\widehat{K}_m$ in $G$, our final contradiction in Case 1.

\medskip\noindent
{\bf Case 2}: $|V(C)|=m-2$.

\noindent
We have $k=d-(m-2)$. Note that $k\geq \lceil n/2\rceil-1$ for odd $m$, and $k\geq \lceil n/2\rceil$ for even $m$. Let $X$ be the set of all vertices of $V(C)$ that are nonadjacent to $Y$ in $G$. For $1\leq i\leq m-2$, either $x_i\in X$, or $x_{i+1}\in X$. Here, $x_{m-1}=x_1$. This is because, if $x_i$ and $x_{i+1}$ have a common neigbor in $Y$, say $y_1$, then by replacing $x_ix_{i+1}$ by $x_iy_1x_{i+1}$ in $C$, we obtain a cycle longer than $C$, a contradiction; if $x_i$ and $x_{i+1}$ are adjacent to different vertices of $Y$, say $x_iy_1,x_{i+1}y_2\in E(G)$, then $y_2x_{i+1}x_{i+2}\ldots x_{m-2}x_1\ldots x_iy_1$ is a path of length $m$, which together with $u$ forms a $\widehat{K}_m$ in $G$, also a contradiction. Thus, at least one end of each edge of $C$ is nonadjacent to $Y$ in $G$. Note that $|X| \geq \lceil n/2\rceil$ and $|Y|\geq \lceil n/2\rceil-1$ for odd $m$ and $|Y|\geq \lceil n/2\rceil$ for even $m$. If $m$ is even or $n$ is odd, then we get a path $P_n$ in $\ol G[X\cup Y]$. This implies it remains to consider the case that $n$ is even and $m$ is odd, with $m\geq n+3$.

If $|V(C)-X|\geq 2$, say $x_i,x_j\not\in X$, then $x_{i+1},x_{j+1}\in X$. Moreover, $x_{i+1}x_{j+1}\not\in E(G)$; otherwise we may obtain either a cycle longer than $C$ in $F$, or a path of length $m$ in $F$, which together with $u$ forms a $\widehat{K}_m$ in $G$, both of which are contradictions. Now let $x'_1,x'_2,\ldots,x'_{|X|-2}\in X-\{x_{i+1},x_{j+1}\}$. Since $|X|-2\geq \lceil |V(C)|/2\rceil-2\geq n/2-1$, let $P=x_{i+1}x_{j+1}y_1x'_1y_2x'_2\ldots y_{n/2-1}x'_{n/2-1}$. Note that $P$ is a path of order $n$ in $\ol G$, a contradiction. Thus, $m-3\leq |X|\leq m-2$ and there exists a vertex in $V(C)$, say $x_1$, such that $e(V(C)-\{x_1\},Y)=0$.

Since $m\geq n+3\geq 9$, we have $m-3\geq \lceil n/2\rceil+2$. If there is an edge in $\ol G[V(C)-\{x_1\}]$, say $x_ix_j\in E(\ol G)$, then $\ol G[X\cup Y]$ contains a path $P_n$, a contradiction. Thus, $G[V(C)-\{x_1\}]$ is a complete graph of order $m-3$.

Let $z_1,z_2\in Z$. We claim that $e(\{z_1\},V(C)-\{x_1\})=0$ in $\ol G$;  otherwise, say for $z_1x_2\in E(\ol G)$, $z_2uz_1x_2y_2x_3y_3\ldots x_{n/2-1}y_{n/2-1}x_{n/2}$ is a path of order $n$ in $\ol G$, a contradiction. For the same reason, $e(\{z_2\},V(C)-\{x_1\})=0$ in $\ol G$.

It is easy to check that $x_1ux_3z_1x_4z_2x_5\ldots x_{m-2}$ is a path of order $m$, which together with $x_2$ forms a $\widehat{K}_m$ in $G$, our final contradiction in Case 2.

\medskip\noindent
{\bf Case 3}: $|V(C)|=m-3$.

\noindent
If $m=n+2\geq 8$, then $m$ and $n$ have the same parity. In that case, $R(C_{2\lfloor (m-1)/2\rfloor},P_n)=2\lfloor (m-1)/2\rfloor+\lfloor n/2\rfloor-1\leq 2\lfloor m/2\rfloor+\lceil n/2\rceil-2\leq d$. Since $\ol F$ contains no $P_n$, $F$ contains a $C_{2\lfloor (m-1)/2\rfloor}$. This contradicts the fact that $C$ with $|V(C)|=m-3$ is a longest cycle in $F$. It remains to consider the case that $m\geq n+3\geq 9$.

We have $k=d-(m-3)\geq \lceil n/2\rceil$. By Lemma \ref{ZZC}, any two vertices of $Y$ have at least $\lceil (m-3)/2\rceil-1\geq \lceil n/2\rceil-1$ common nonadjacent vertices of $V(C)$ in $G$. Since $C$ is a longest cycle in $G$, any vertex of $Y$ has at least $\lceil (m-3)/2\rceil\geq \lceil n/2\rceil$ nonadjacent vertices of $V(C)$ in $G$. By these observations, $y_1$ and $y_2$ have a common nonadjacent vertex in $V(C)$, say $x_1$; for $2\leq i\leq \lceil n/2\rceil-1$, $y_i$ and $y_{i+1}$ have a common nonadjacent vertex in $V(C)-\{x_1, x_2,\ldots,x_{i-1}\}$, say $x_i$; $y_{\lceil n/2\rceil}$ have a nonadjacent vertex in $X-\{x_1, x_2,\ldots,x_{\lceil n/2\rceil-1}\}$, say $x_{\lceil n/2\rceil}$. Then $y_1x_1y_2x_2\ldots y_{\lceil n/2\rceil}x_{\lceil n/2\rceil}$ is a path of order at least $n$ in $\ol G$. This final contradiction  completes the proof of Case 3 and of Theorem \ref{main}. \qed


\begin{thebibliography}{99}
\bibitem{Bo} J.A. Bondy, Pancyclic graphs I,
\emph{Journal of Combinatorial Theory, Series B} 11 (1971), 80--84.

\bibitem{D} G.A. Dirac, Some theorems on abstract graphs,
\emph{Proceedings of the London Mathematical Society} 2 (1952), 69--81.

\bibitem{FLPS} R.J. Faudree, S.L. Lawrence, T.D. Parsons, and R.H. Schelp, Path-cycle Ramsey numbers,
\emph{Discrete Mathematics} 10 (1974), 269--277.

\bibitem{GG} L. Gerencs\'{e}r and A. Gy\'{a}rf\'{a}s, On Ramsey-type problems,
\emph{Annales Universitatis Scientiarum Budapestinensis, E\"{o}tv\"{o}s Sect. Math.} 10 (1967), 167--170.

\bibitem{LN} B. Li and B. Ning, The Ramsey numbers of paths versus wheels: a complete solution,
\emph{The Electronic Journal of Combinatorics} 21 (2014), \#P4.41.

\bibitem{P} T.D. Parsons, Path-star Ramsey numbers,
\emph{Journal of Combinatorial Theory}, Series B 17 (1974), 51--58.

\bibitem{RJ} C.C. Rousseau and J. Sheehan, A class of Ramsey problems involving trees,
\emph{Journal of the London Mathematical Society} 2 (1978), 392--396.

\bibitem{SB} A.N.M. Salman and H.J. Broersma, Path-kipas Ramsey numbers,
\emph{Discrete Applied Mathematics} 155 (2007), 1878--1884.

\bibitem{ZZC} Y.B. Zhang, Y.Q. Zhang, and Y.J. Chen, The Ramsey numbers of wheels versus odd cycles,
\emph{Discrete Mathematics} 323 (2014), 76--80.
\end{thebibliography}
\end{document}


