A proof of a conjecture on matching-path connected size Ramsey number

AIMS Mathematics

article

Yixin Zhang¹  Yanbo Zhang¹  Hexuan Zhi¹ 

[1] School of Mathematical Sciences, Hebei Normal University;Hebei International Joint Research Center for Mathematics and Interdisciplinary Science

关键词: size Ramsey number;    connected size Ramsey number;    matching;    path;   

DOI  :  10.3934/math.2023406

学科分类：地球科学(综合)

来源: AIMS Press

【 摘 要 】

For two graphs $ G_1 $ and $ G_2 $, the connected size Ramsey number $ {\hat{r}}_c(G_1, G_2) $ is the smallest number of edges of a connected graph $ G $ such that if each edge of $ G $ is colored red or blue, then $ G $ contains either a red copy of $ G_1 $ or a blue copy of $ G_2 $. Let $ nK_2 $ be a matching with $ n $ edges and $ P_4 $ a path with four vertices. Rahadjeng, Baskoro, and Assiyatun [Procedia Comput. Sci. 74 (2015), 32-37] conjectured that $ \hat{r}_{c}(nK_2, P_4) = 3n-1 $ if $ n $ is even, and $ \hat{r}_{c}(nK_2, P_4) = 3n $ otherwise. We verify the conjecture in this short paper.

【 授权许可】

CC BY