Conditionally critical indecomposable graphs

Chandan K. Dubey, Shashank K. Mehta, Jitender S. Deogun

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations

Abstract

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}, G[V -{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 (a1, b1), . . . , (ak, bk) such that induced subgraphs on subset V - {aj1, bj1, . . . , ajs, bjs} are also X-critical for any collection of pairs {(a j1, bj1), . . . ,(ajs, bjs)}.

Original languageEnglish (US)
Pages (from-to)690-700
Number of pages11
JournalLecture Notes in Computer Science
Volume3595
DOIs
StatePublished - 2005
Event11th Annual International Conference on Computing and Combinatorics, COCOON 2005 - Kunming, China
Duration: Aug 16 2005Aug 29 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Conditionally critical indecomposable graphs'. Together they form a unique fingerprint.

Cite this