直径为3且有割边的已约简图

Reduced Graphs of Diameter Three and Having Cut Edges

摘要: 若图H = (V(H)，E(H)) 的任意一个偶子集 R⊆V(H)，H 有一个生成连通子图H_R，使得O(H_R) = S,则H 是可折叠的，Catlin 证明任意图 G 都有唯一的两两点不交的极大可折叠子图的集合。G 的约简记为 G"，是将 G 中的每一个极大可折叠子图收缩成一个点后得到的图，若G = G"，则 G 是已约简的。在本文中主要刻画直径为3 且有割边的已约简图。若割边是非平凡的，则 G≅S"_n,m; 否则,除 1 度点外其余点都在一个导出i-圈,i ∈{4,5}。

Abstract: A graph H = (V(H)，E(H)) is collapsible if for every subset R⊆V(H) with |R| even, H has a spanning connected sungraph H_R such that O(H_R) = R. Catlin showed that every graph G has unique collection of pairwise vertex-disjoint maximal collapsible subgraphs. The reduction of G, denoted by G", is the graph obtained from G by contracting each maximal collapsible subgraphs into a single vertex. A graph G is reduced if G = G". In this article, we characterize the reduced graphs of diameter three and having cut edges. If the cute edge is nontrival, then G≅S"_n,m, otherwise, all vertices in an induced i-cycle, except 1 degree vertices, i ∈{4,5}.