Connected size Ramsey numbers of matchings versus a small path or cycle

被引:0
作者
Wang, Sha [1 ,2 ]
Song, Ruyu [1 ,2 ]
Zhang, Yixin [1 ,2 ]
Zhang, Yanbo [1 ,2 ]
机构
[1] Hebei Normal Univ, Sch Math Sci, Shijiazhuang 050024, Peoples R China
[2] Hebei Res Ctr Basic Discipline Pure Math, Shijiazhuang 050024, Peoples R China
基金
中国国家自然科学基金;
关键词
Ramsey number; connected size Ramsey number; matching; path; cycle;
D O I
10.5614/ejgta.2025.13.1.11
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given two graphs G1, G2, the connected size Ramsey number rc(G1, G2) is defined to be the minimum number of edges of a connected graph G, such that for any red-blue edge colouring of G, there is either a red copy of G1 or a blue copy of G2. Concentrating on rc(nK2, G2) where nK2 is a matching, we generalise and improve two previous results as follows. Vito, Nabila, Safitri, and Silaban (J. Phys. Conf. Ser., 2021) obtained the exact values of rc(nK2, P3) for n = 2, 3, 4. We determine its exact values for all positive integers n. Rahadjeng, Baskoro, and Assiyatun (Proc. Indian Acad. Sci.: Math. Sci., 2017) proved that rc(nK2, C4) <= 5n - 1 for n >= 4. We improve the upper bound from 5n - 1 to & LeftFloor;(9n - 1)/2 & RightFloor;. In addition, we show a result which has the same flavour and has exact values: rc(nK2, C3) = 4n - 1 for all positive integers n.
引用
收藏
页码:163 / 170
页数:8
相关论文
共 8 条
[1]   The connected size Ramsey number for matchings versus small disconnected graphs [J].
Assiyatun, Hilda ;
Rahadjeng, Budi ;
Baskoro, Edy Tri .
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2019, 7 (01) :113-119
[2]  
Bondy A., 2008, Graph Theory, DOI [DOI 10.1007/978-1-84628-970-5, 10.1007/978-1-84628-970-5]
[3]  
Erdos P., 1978, Periodica Mathematica Hungarica, V9, P145, DOI 10.1007/BF02018930
[4]  
Erdos P., 1984, Finite and Infinite Sets, P247
[5]   Connected size Ramsey number for matchings vs. small stars or cycles [J].
Rahadjeng, Budi ;
Baskoro, Edy Tri ;
Assiyatun, Hilda .
PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 2017, 127 (05) :787-792
[6]   Connected Size Ramsey Numbers for Matchings versus Cycles or Paths [J].
Rahadjeng, Budi ;
Baskoro, Edy Tri ;
Assiyatun, Hilda .
2ND INTERNATIONAL CONFERENCE OF GRAPH THEORY AND INFORMATION SECURITY, 2015, 74 :32-37
[7]  
Vito V., 2021, Journal of Physics: Conference Series, V1725, DOI 10.1088/1742-6596/1725/1/012098
[8]  
West D.B., 2001, Introduction to graph theory, V2