Conditionally Critical Indecomposable Graphs

摘要：

Let X be a subset of vertices of an undirected graph G=(V, E). G is X-critical if it is indecomposable and its induced subgraph on X vertices is also indecomposable, but all induced subgraphs on V-w are decomposable for all w ∈ V-X. We present two results in this paper. The first result states that if G is X-critical, then for every w ∈ V-x, GV-w has a unique non-trivial module and its cardinality is either 2 or |V|-2.The second result is that the vertices of V-X can be paired up as (o1,b1),..., (ak, bk) such that induced subgraphs on subset V-aj, bj1,..., ajs, bjs are also Xcritical for any collection of pairs (aj1,bj1),..., (ajs,bjs).

作者: Chandan K. Dubey Shashank K. Mehta Jitender S. Deogun

作者单位: Indian Institute of Technology, Kanpur - 208016, India University of Nebraska-Lincoln, Lincoln, NE 68588-0115, USA

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 690-700

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）