图在……中的细分

Subdivision of graphs in .

作者信息

Wijaya Kristiana, Baskoro Edy Tri, Assiyatun Hilda, Suprijanto Djoko

机构信息

Graph, Combinatorics, and Algebra Research Group, Department of Mathematics, FMIPA, Universitas Jember, Jalan Kalimantan 37 Jember 68121, Indonesia.

Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung 40132, Indonesia.

出版信息

Heliyon. 2020 Jun 12;6(6):e03843. doi: 10.1016/j.heliyon.2020.e03843. eCollection 2020 Jun.

DOI:10.1016/j.heliyon.2020.e03843

PMID:32637673

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC7325471/

Abstract

For any graphs , and , the notation means that any red-blue coloring of all edges of will contain either a red copy of or a blue copy of . The set consists of all Ramsey -minimal graphs, namely all graphs satisfying but for each , . In this paper, we propose a simple construction for creating new Ramsey minimal graphs from the previous known Ramsey minimal graphs (by subdivision operation). In particular, suppose and let be an edge contained in a cycle of , we construct a new Ramsey minimal graph in from graph by subdividing the edge four times.

摘要

对于任意的图(G)、(H)和(K)，记号(G\rightarrow (H,K))表示对(G)的所有边进行红 - 蓝着色时，要么包含(H)的红色副本，要么包含(K)的蓝色副本。集合(\mathcal{R}(H,K))由所有拉姆齐((H,K)) - 极小图组成，即所有满足(G\rightarrow (H,K))但对于每个(e\in E(G))，(G - e\nrightarrow (H,K))的图(G)。在本文中，我们提出了一种通过细分操作从先前已知的拉姆齐极小图创建新的拉姆齐极小图的简单构造方法。特别地，假设(G\in\mathcal{R}(H,K))且设(e)是(G)中包含在一个圈中的边，我们通过将边(e)细分四次从图(G)构造出(\mathcal{R}(H,K))中的一个新的拉姆齐极小图。