Indecomposable graphs. (English) Zbl 0882.05108
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.
Reviewer: Ma Zhongfan (Beijing)
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Bonizzoni, P., Primitive 2-structures with the \((n\) − 2)-property, Theoret. Comput. Sci., 132, 151-178 (1994) · Zbl 0822.68078 |
| [2] | Buer, H.; Möhring, R. H., A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res., 8, 170-184 (1983) · Zbl 0517.05057 |
| [3] | Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, Parts I and II, Theoret. Comput. Sci., 70, 305-342 (1990) · Zbl 0701.05052 |
| [4] | Ehrenfeucht, A.; Rozenberg, G., Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., 70, 343-358 (1990) · Zbl 0701.05053 |
| [5] | Fraïssé, R., L’intervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture d’une relation, (Pouzet, M.; Richard, D., Orders, Description and Roles (1984), North-Holland: North-Holland Amsterdam), 313-342 · Zbl 0574.04001 |
| [6] | Gallaï, T., Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66 (1967) · Zbl 0153.26002 |
| [7] | Gnanvo, C.; Ille, P., La reconstructibilité des tournois, C.R. Acad. Sci. Paris Série I Math., 306, 577-580 (1988) · Zbl 0665.05034 |
| [8] | Harju, T.; Rozenberg, G., Decomposition of infinite labeled 2-structures, (Lecture Notes in Computer Science, vol. 812 (1994), Springer: Springer Berlin), 145-158 · Zbl 1529.68211 |
| [9] | Ille, P., L’intervalle relationnel et ses généralisations, C.R. Acad. Sci. Paris Série I Math., 306, 1-4 (1988) · Zbl 0654.04001 |
| [10] | Schmerl, J. H.; Trotter, W. T., Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., 113, 191-205 (1993) · Zbl 0776.06002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
