Graphs Whose Indecomposability Graph is 2-Covered
Rim Ben Hamadou and Imed Boudabbous
Given a graph G = (V, E), a subset X of V is an interval of G provided that for any a, b ∈ X and x ∈ V \ X, {a, x} ∈ E if and only if {b, x} ∈ E. For example, ∅, {x}(x ∈ V) and V are intervals of G, called trivial intervals. A graph whose intervals are trivial is indecomposable; otherwise, it is decomposable. According to Ille, the indecomposability graph of an undirected indecomposable graph G is the graph II(G) whose vertices are those of G and edges are the unordered pairs of distinct vertices {x, y} such that the induced subgraph G[V \ {x, y}] is indecomposable. We characterize the indecomposable graphs G whose II(G) admits a vertex cover of size 2.
Keywords: Graphs, indecomposable, interval, indecomposability graph, partially critical.