Abstract | ||
---|---|---|
Let G = ( V , E ) be a graph, a subset X of V is an interval of G whenever for a, b ∈ X and x ∈ V − X , ( a , x ) ∈ E (resp. ( x , a ) ∈ E ) if and only if ( b , x ) ∈ E (resp. ( x , b ) ∈ E ). For instance, 0, x , where x ∈ V , and V are intervals of G , called trivial intervals. A graph G is then said to be indecomposable when all of its intervals are trivial. In the opposite case, we will say that G is decomposable. We now introduce the minimal indecomposable graphs in the following way. Given an indecomposable graph G = ( V , E ) and vertices x 1 , …, x k of G , G is said to be minimal for x 1 , …, x k whenever for every proper subset W of V , if x 1 , …, x k ∈ W and if | W | ⩾ 3, then the induced subgraph G ( W ) of G is decomposable. In this paper, we characterize the minimal indecomposable graphs for one or two vertices and we describe in a more precise manner the minimal indecomposable symmetric graphs, posets and tournaments. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1016/S0012-365X(97)00077-0 | Discrete Mathematics |
Keywords | Field | DocType |
minimal indecomposable graph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Induced subgraph,Indecomposable module,Mathematics | Journal |
Volume | Issue | ISSN |
183 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
12 | 0.93 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alain Cournier | 1 | 281 | 22.07 |
Pierre Ille | 2 | 58 | 11.97 |