Graph decompositions for cartesian products

DOI10.1016/J.ENDM.2005.06.073MaRDI QIDQ3439368zbMATH OpenOpenAlexFDO

Authors Selma Djelloul

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2005.06.073

zbMATH Keywords

algorithmic complexitygraph grammarsgraph logicpath-decompositiontree-decomposition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Treewidth and logical definability of graph products
• Cartesian products of graphs and metric spaces
• Decomposition of product graphs into paths and stars with three edges
• Factoring cartesian‐product graphs
• Grammars and clique-width bounds from split decompositions

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Basic notions of universal algebra for language theory and graph grammars
• Graph expressions and graph rewritings
• Handbook of Graph Grammars and Computing by Graph Transformation
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(8)

• Treewidth and logical definability of graph products
• Decompositions of graphs based on a new graph product
• Decomposition of Cartesian products of regular graphs into isomorphic trees
• Semi-Cartesian product of graphs
• Note on decompositions based on the vertex-removing synchronised graph product
• Cartesian products of graphs as spanning subgraphs of de Bruijn graphs
• Recognizing triangulated Cartesian graph products
• Lower bounds for treewidth of product graphs

This page was built for publication: Graph decompositions for cartesian products

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