\documentclass[12pt]{article}
\usepackage{e-jc}
\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{ 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}}
\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 \\
\small P.O. Box 314, 306 14 Pilsen, Czech Republic\\
\small \tt holubpre@kma.zcu.cz \\
}
\date{\dateline{Jan 30, 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