\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