Ramsey Numbers of Trails

被引：2

作者：

Osumi, Masatoshi ^{[1
]}

机构：

[1] Univ Electrocommun, Chofu, Tokyo 1828585, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2022年 / E105A卷 / 09期

关键词：

Ramsey theory; trails; Eulerian graphs; semi-Eulerian graphs;

D O I：

10.1587/transfun.2021DMP0003

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We initiate the study of Ramsey numbers of trails. Let k >= 2 be a positive integer. The Ramsey number of trails with k vertices is defined as the the smallest number n such that for every graph H with n vertices, H or the complete (H) over bar contains a trail with k vertices. We prove that the Ramsey number of trails with k vertices is at most k and at least 2 root k + (Theta)1 degrees. This improves the trivial upper bound of [3 k/2] - 1.

引用

页码：1235 / 1240

页数：6