Open AccessOn Ramsey (P 3, C 6)-minimal graphs for certain order
Author(s) -
Firsti Khalisatin Nisa,
Desi Rahmadani,
Purwanto Purwanto,
Hery Susanto
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1538/1/012011
Subject(s) - combinatorics , mathematics , induced subgraph , graph , induced path , ramsey's theorem , induced subgraph isomorphism problem , discrete mathematics , chordal graph , longest path problem , line graph , voltage graph , vertex (graph theory)
Let F, G and H be graphs. Notation F → ( G, H ) means that there is any two-coloring, say red and blue, of all edges of F which contains red subgraph isomorphic to G or blue subgraph isomorphic to H. The graph F is Ramsey ( G, H )-minimal graph if F → ( G, H ) but F − e ↛ ( G, H ) for any e ∈ E ( F ). The class of all Ramsey ( G, H )-minimal graphs will be denoted by R ( G, H ). In this paper, we proved that there are only two graphs with six vertices that belong to Ramsey minimal graphs for certain pair of path and cycle ( P 3 , C 6 ) and we also determined some graphs with eight vertices in R ( P 3 , C 6 ).