On the Ramsey numbers for the tree graphs versus certain generalised wheel graphs

被引：2

作者：

Chng, Zhi Yee ^{[1
]}

Tan, Ta Sheng ^{[2
]}

Wong, Kok Bin ^{[2
]}

机构：

[1] UNSW Sydney, Sch Math & Stat, Sydney, NSW 2052, Australia

[2] Univ Malaya, Inst Math Sci, Kuala Lumpur 50603, Malaysia

来源：

DISCRETE MATHEMATICS | 2021年 / 344卷 / 08期

关键词：

Ramsey number; Tree; Generalised wheel graphs; STARS; PATHS; ORDER;

D O I：

10.1016/j.disc.2021.112440

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given two simple graphs G and H, the Ramsey number R(G, H) is the smallest integer n such that for any graph of order n, either it contains G or its complement contains H. Let T-n be a tree graph of order n and W-s,W-m be the generalised wheel graph K-s + C-m. In this paper, we show that for n >= 5, s >= 2, R(T-n, W-s,W- 6) = (s + 1)(n - 1) + 1 and for n >= 5, s >= 1, R(T-n, W-s,W-7) = (s + 2)(n - 1) + 1. We also determine the exact value of R(T-n, W-s,W-m) for large nand s. (C) 2021 Elsevier B.V. All rights reserved.

引用

页数：12

共 13 条

[1]

Bondy J. A., 1971, J. Combin. Theory Ser. B, V11, P80, DOI [10.1016/0095-8956(71)90016-5, DOI 10.1016/0095-8956(71)90016-5]

[2]

Brennan M, 2016, ELECTRON J COMB, V23

[3]

BURR SA, 1981, J LOND MATH SOC, V24, P405

[4] The Ramsey numbers of trees versus W6 or W7 [J].

Chen, YJ ;

Zhang, YQ ;

Zhang, KM .

EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (04) :558-564

[5] The Ramsey numbers of paths versus wheels [J].

Chen, YJ ;

Zhang, YQ ;

Zhang, KM .

DISCRETE MATHEMATICS, 2005, 290 (01) :85-87

[6] The Ramsey numbers of stars versus wheels [J].

Chen, YJ ;

Zhang, YQ ;

Zhang, KM .

EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (07) :1067-1075

[7]

Chvatal V., 1977, J. Graph Theory, V1, P93, DOI [DOI 10.1002/JGT.3190010118, 10.1002/jgt.3190010118]

[8] Ramsey goodness and generalized stars [J].

Lin, Qizhong ;

Li, Yusheng ;

Dong, Lin .

EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (05) :1228-1234

[9] The Ramsey Numbers of Trees Versus Generalized Wheels [J].

Wang, Longqin ;

Chen, Yaojun .

GRAPHS AND COMBINATORICS, 2019, 35 (01) :189-193

[10]

Zhang Y., 2008, Nanjing Daxue Xuebao Shuxue Bannian Kan, V25, P35

← 1 2 →