Characterizing the Difference Between Graph Classes Defined by Forbidden Pairs Including the Claw
Characterizing the Difference Between Graph Classes Defined by Forbidden Pairs Including the Claw
复制标题
DOI：
10.1007/s00373-019-02108-0
复制
发表时间：
2019-10
影响因子：
0.7
通讯作者：
Guantao Chen;M. Furuya;Songling Shan;Shoichi Tsuchiya;Ping Yang
中科院分区：
文献类型：
--
作者：
Guantao Chen;M. Furuya;Songling Shan;Shoichi Tsuchiya;Ping Yang
对于两个图A和B，如果G既不包含A也不包含B作为导出子图，则称G是自由图。让我们来表示有序的路径。对于非负整数k，m，设为从和三条顶点不相交的路得到的图，通过用其中一条路的一个端点标识的每一个顶点。勒当Bedrossian刻画了所有连通图对，使得每个2-连通自由图都是Hamilton图。出现在人物刻画中的所有对都涉及爪（）和其中之一，和。在本文中，我们刻画了连通图是（i）-自由但不自由，（ii）-自由但不自由，或（iii）-自由但不自由。第三个结果与贝德罗西安的人物塑造密切相关。此外，我们将我们的特征应用到一些禁止对问题。
For two graphsAandB, a graphGis called-free ifGcontains neitherAnorBas an induced subgraph. Letdenote the path of ordern. For nonnegative integersk,andm, letbe the graph obtained fromand three vertex-disjoint paths,,by identifying each of the vertices ofwith one endvertex of one of the paths. Letand. Bedrossian characterized all pairsof connected graphs such that every 2-connected-free graph is Hamiltonian. All pairs appearing in the characterization involve the claw () and one of,and. In this paper, we characterize connected graphs that are (i)-free but not-free, (ii)-free but not-free, or (iii)-free but not-free. The third result is closely related to Bedrossian’s characterization. Furthermore, we apply our characterizations to some forbidden pair problems.