Proceedings of the International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021)

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.

Download article (PDF)

Volume Title
Proceedings of the International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021)
Series
Advances in Computer Science Research
Publication Date
8 February 2022
ISBN
10.2991/acsr.k.220202.003
ISSN
2352-538X
DOI
10.2991/acsr.k.220202.003How to use a DOI?
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  -