Primitivity is hereditary for 2-structures

DOI10.1016/0304-3975(90)90131-ZMaRDI QIDQ913824zbMATH OpenOpenAlexFDO

Authors Andrzej Ehrenfeucht, Grzegorz Rozenberg

Publication date 1990

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(90)90131-z

zbMATH Keywords

2-structuresclanedge-labeled graph

Mathematics Subject Classification ID

Graph theory (05C99)

Recommendations

• Primitive 2-structures with the (n-2)-property
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• scientific article; zbMATH DE number 591000
• A k-structure generalization of the theory of 2-structures
• Critically twin primitive 2-structures

Cites work

• Complement reducible graphs
• On a property of the class of n-colorable graphs
• Parallel concepts in graph theory
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families

Cited in

(69)

• Critical support of an indecomposable graph
• Critically indecomposable graphs
• The recognition of the class of indecomposable digraphs under low hemimorphy
• Indecomposability graph and critical vertices of an indecomposable graph
• Angular 2-structures
• Modular decomposition and transitive orientation
• Primitive 2-structures with the (n-2)-property
• A k-structure generalization of the theory of 2-structures
• Indecomposable graphs
• Minimal indecomposable graphs
• The \(C_{3}\)-structure of the tournaments.
• Sur la répartition des diamants dans un tournoi. (On the repartition of diamonds in a tournament).
• Reconstructing gene trees from Fitch's xenology relation
• Critical and infinite tournaments
• Finite orders which are reconstructible up to duality by their comparability graphs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Making a tournament indecomposable by one subtournament-reversal operation
• Editing to prime graphs
• Prime 3-uniform hypergraphs
• From modular decomposition trees to rooted median graphs
• Tournaments with maximal decomposability
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Ultracritical and hypercritical binary structures
• Critical and infinite directed graphs
• Decomposability index of tournaments
• Indecomposability graph and indecomposability recognition
• Morphology of the \((-1)\)-critical tournaments
• Partially critical tournaments
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• Fully dynamic recognition algorithm and certificate for directed cographs
• Triangle-free graphs which are minimal for some nonstable 4-vertex subset
• Indecomposable tournaments and their indecomposable subtournaments with six vertices
• Convex circuit-free coloration of an oriented graph
• Finite tournaments with a nonempty diamonds' support
• Decomposability and co-modular indices of tournaments
• Structure theorem for \(U_{5}\)-free tournaments
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• Miscellaneous digraph classes
• Cut-primitive directed graphs versus clan-primitive directed graphs
• 3-minimal triangle-free graphs
• Subtournaments isomorphic to W₅ in a indecomposable tournament
• scientific article; zbMATH DE number 591000 (Why is no real title available?)
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• A survey of the algorithmic aspects of modular decomposition
• A tight lower bound for primitivity in k-structures
• Theory of 2-structures
• Recognizing indecomposability for tournaments
• 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?)
• Partially pair-critical digraphs
• Two {4,n-3}-isomorphic n-vertex digraphs are hereditarily isomorphic
• Generalized tournament matrices with the same principal minors
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Nesting of prime substructures in k-ary relations
• Primality, criticality and minimality problems in trees
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Decomposition of infinite labeled 2-structures
• Irreducible pairings and indecomposable tournaments
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• T-structures, T-functions, and texts
• The critically duo-free infinite tournaments
• Description of the digraphs \(\{-1\}\)-hypomorphic to a reducible digraph
• Prime and critical digraphs
• The half-isomorphy and the finite strongly connected tournaments
• Indecomposable tournaments with minimum Slater index
• Skew-symmetric matrices and their principal minors
• Indecomposable tournaments and their indecomposable subtournaments on 5 vertices
• Theory of 2-structures. II: Representation through labeled tree families

This page was built for publication: Primitivity is hereditary for 2-structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q913824)