Strict refinement for graphs and digraphs

DOI10.1016/0095-8956(87)90018-9zbMath0587.05056OpenAlexW2082558966MaRDI QIDQ1072575

James W. Walker

Publication date: 1987

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(87)90018-9

zbMATH Keywords

isometric embeddingCartesian productconnected graphunique factorizationstrict refinement

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20)

Related Items

Groups for which it is easy to detect graphical regular representations, Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time, \(\mathcal{M}\)-coextensive objects and the strict refinement property, Digraphs with small automorphism groups that are Cayley on two nonisomorphic groups, Products of abstract polytopes, Finding the prime factors of strong direct product graphs in polynomial time, Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time, The semigroup of metric measure spaces and its infinitely divisible probability measures

Cites Work

• Factoring a graph in polynomial time
• Automorphisms and products of ordered sets
• Graph multiplication
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
• On direct product desomposition of partially ordered sets
• On Isometric Embeddings of Graphs
• Refinement properties for relational structures
• Unnamed Item
• Unnamed Item
• Unnamed Item