Indecomposable graphs
From MaRDI portal
Let \(G= (V,E)\) be a finite directed graph. A subset \(X\) of \(V\) is an interval of \(G\) if for \(a,b\in X\) and \(x\in V-X\), we have \(ax\in E\) (resp. \(xa\in E\)) if and only if \(bx\in E\) (resp. \(xb\in E\)). So \(\varnothing\), \(V\) and every singleton are intervals of \(G\) (called trivial intervals). The graph \(G\) is said to be indecomposable if every interval of \(G\) is trivial. Let \(G\) be an indecomposable graph, let \(X\) be a subset of \(V\) such that \(|X|\geq 3\) and \(|V-X|\geq 6\), and let \(G(X)\) be indecomposable. This paper proves that there is a subset \(Y\) of \(V\) such that \(X\subseteq Y\), \(|V-Y|=2\), and \(G(Y)\) is indecomposable.
Recommendations
Cites work
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- scientific article; zbMATH DE number 3916273 (Why is no real title available?)
- scientific article; zbMATH DE number 4066888 (Why is no real title available?)
- scientific article; zbMATH DE number 4087702 (Why is no real title available?)
- Primitive 2-structures with the (n-2)-property
- Primitivity is hereditary for 2-structures
- Theory of 2-structures. II: Representation through labeled tree families
- Transitiv orientierbare Graphen
Cited in
(55)- Critical support of an indecomposable graph
- Critically indecomposable graphs
- Graphs critically without duo
- The recognition of the class of indecomposable digraphs under low hemimorphy
- Indecomposability graph and critical vertices of an indecomposable graph
- Minimal indecomposable graphs
- The \(C_{3}\)-structure of the tournaments.
- Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
- What is reconstruction for ordered sets?
- Making a tournament indecomposable by one subtournament-reversal operation
- Prime 3-uniform hypergraphs
- Critical 3-hypergraphs
- Tournaments with maximal decomposability
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Decomposing simple permutations, with enumerative consequences
- Critical and infinite directed graphs
- Decomposability index of tournaments
- Indecomposability graph and indecomposability recognition
- Recognition of prime graphs from a prime subgraph
- Morphology of the \((-1)\)-critical tournaments
- Indecomposable Laplacian integral graphs
- The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
- Indecomposable tournaments and their indecomposable subtournaments with six vertices
- Convex circuit-free coloration of an oriented graph
- Tournaments without acyclic interval.
- Finite tournaments with a nonempty diamonds' support
- Decomposability and co-modular indices of tournaments
- Simple extensions of combinatorial structures
- Decomposition tree and indecomposable coverings
- A characterization of the indecomposable and infinite graphs
- Some Algorithms on Conditionally Critical Indecomposable Graphs
- Partially critical indecomposable graphs
- The indecomposable tournaments T with \(|W_5(T)|=|T|-2\)
- Subtournaments isomorphic to W₅ in a indecomposable tournament
- scientific article; zbMATH DE number 599133 (Why is no real title available?)
- scientific article; zbMATH DE number 1953084 (Why is no real title available?)
- Graphs whose indecomposability graph is 2-covered
- Criticality of switching classes of reversible 2-structures labeled by an abelian group
- The simplicity index of tournaments
- scientific article; zbMATH DE number 7297127 (Why is no real title available?)
- Aggregation of Markov flows I: theory
- INDECOMPOSABILITY GRAPHS OF RINGS
- scientific article; zbMATH DE number 2222767 (Why is no real title available?)
- Computing and Combinatorics
- Partially pair-critical digraphs
- A proof of a conjecture of Sabidussi on graphs idempotent under the lexicographic product
- Primality, criticality and minimality problems in trees
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- The primality graph of critical 3-hypergraphs
- Well-quasi-ordering and Embeddability of Relational Structures
- Irreducible pairings and indecomposable tournaments
- The critically duo-free infinite tournaments
- Prime and critical digraphs
- Indecomposable tournaments with minimum Slater index
- Indecomposable tournaments and their indecomposable subtournaments on 5 vertices
This page was built for publication: Indecomposable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1367028)
