On Factorable Extensions and Subgraphs of Prime Graphs

DOI10.1137/0402017MaRDI QIDQ4710541zbMATH OpenOpenAlexFDO

Authors Joan Feigenbaum, Ramsey W. Haddad

Publication date 25 June 1992

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0402017

zbMATH Keywords

dynamic programming algorithmNP- completenessproduct graphstight bounds

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3916315
• scientific article; zbMATH DE number 279572
• scientific article; zbMATH DE number 5371977
• scientific article; zbMATH DE number 1011078
• On uniqueness of prime bipartite factors of graphs
• On (g,f)-factorizations of graphs
• scientific article; zbMATH DE number 867710
• On some factor theorems of graphs
• Prime factorization and domination in the hierarchical product of graphs
• A generalization of prime graphs of finite groups

Cited in

(15)

• Approximate graph products
• Equipartitions of graphs
• Strong products of \(\chi\)-critical graphs
• On the complexity of the embedding problem for hypercube related graphs
• On subgraphs of Cartesian product graphs and S-primeness
• On the weak reconstruction of Cartesian-product graphs
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Junction trees of general graphs
• Weak k-reconstruction of cartesian product graphs
• The set of prime extensions of a graph: the finite and the infinite case
• scientific article; zbMATH DE number 867710 (Why is no real title available?)
• A local prime factor decomposition algorithm
• Robust Factorizations and Colorings of Tensor Graphs
• On optimizing edge connectivity of product graphs
• Recognizing graph products and bundles

This page was built for publication: On Factorable Extensions and Subgraphs of Prime Graphs

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