String decompositions of graphs

MaRDI QIDQ2713617zbMATH OpenFDO

Authors Atsushi Kaneko, Mamoru Watanabe

Publication date 10 June 2001

Published in Ars Combinatoria (Search for Journal in Brave)

zbMATH Keywords

2-connected graphblockedge partitionwalk

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The authors prove, among other results, that a 2-connected graph \(G=(V,E)\) has a string decomposition (SD) iff \(G\) is not a cycle. An SD is a partition \(P\) of \(E\) into strings, which are defined to be the walks in \(G\) in which inner vertices do not repeat and the two distinct endvertices repeat each at most twice (a cycle is not a string), such that every vertex of \(G\) of degree at least 2 is the inner vertex of a unique string of \(P\). In path decompositions (PD) every string is in addition required to be a path. It is proved that every 3-connected graph has a PD. Necessary and sufficient conditions are given, in terms of end-blocks, for a graph with cut vertices to have an SD or a PD. The paper is at some places hard to understand because of its bad English.

Recommendations

• Tree-decompositions of graphs. I
• Decomposition of 3-connected graphs
• Tree decomposition
• scientific article; zbMATH DE number 3865323
• scientific article; zbMATH DE number 554067

Cited in

(7)

• Decidability of string graphs
• String shuffle: circuits and graphs
• A sharp threshold phenomenon in string graphs
• On well-connected sets of strings
• Minimal change list for Lucas strings and some graph theoretic consequences
• scientific article; zbMATH DE number 1936578 (Why is no real title available?)
• String graphs and incomparability graphs

This page was built for publication: String decompositions of graphs

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