On Ramsey (mK2, P4)-Minimal Graphs
Authors
Asep Iqbal Taufik1, Denny Riama Silaban1, *, Kristiana Wijaya2
1Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Indonesia, Depok 16424, Indonesia
2Graph, Combinatorics, and Algebra Research Group, Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Jember, Jember 68121, Indonesia
*Corresponding author. Email: denny@sci.ui.ac.id
Corresponding Author
Denny Riama Silaban
Available Online 8 February 2022.
- DOI
- 10.2991/acsr.k.220202.003How to use a DOI?
- Keywords
- Matching; Path; Ramsey minimal graphs; Subdivision
- Abstract
Let F, G, and H be simple graphs. The notation F → (G, H) means that any red-blue coloring of all edges of F will contain either a red copy of G or a blue copy of H. Graph F is a Ramsey (G, H)-minimal if F → (G, H) but for each 𝑒 ∈ E(F), (𝐹 − 𝑒) ↛ (G, H). The set ℛ(G, H) consists of all Ramsey (G, H)-minimal graphs. Let mK2 be matching with m edges and Pn be a path on n vertices. In this paper, we construct all disconnected Ramsey minimal graphs, and found some new connected graphs in ℛ(3K2, P4). Furthermore, we also construct new Ramsey minimal graphs in ℛ((m + 1)K2, P4) from Ramsey minimal graphs in ℛ(mK2, P4) for m ≥ 4, by subdivision operation.
- Copyright
- © 2022 The Authors. Published by Atlantis Press International B.V.
- Open Access
- This is an open access article under the CC BY-NC license.
Cite this article
TY - CONF AU - Asep Iqbal Taufik AU - Denny Riama Silaban AU - Kristiana Wijaya PY - 2022 DA - 2022/02/08 TI - On Ramsey (mK₂, P₄)-Minimal Graphs BT - Proceedings of the International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021) PB - Atlantis Press SP - 11 EP - 16 SN - 2352-538X UR - https://doi.org/10.2991/acsr.k.220202.003 DO - 10.2991/acsr.k.220202.003 ID - Taufik2022 ER -