Algorithmic Generation of Graphs of Branch-width ≤ k - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2006

Algorithmic Generation of Graphs of Branch-width ≤ k


Branchwidth is a connectivity parameter of graphs closely related to treewidth. Graphs of treewidth at most k can be generated algorithmically as the subgraphs of k-trees. In this paper, we investigate the family of edge-maximal graphs of branchwidth k, that we call k-branches. The k-branches are, just as the k-trees, a subclass of the chordal graphs where all minimal separators have size k. However, a striking difference arises when considering subgraph-minimal members of the family. Whereas K_{k+1} is the only subgraph-minimal k-tree, we show that for any k ≤ 7 a minimal k-branch having q maximal cliques exists for any value of q different than 3 and 5, except for k=8,q=2. We characterize subgraph-minimal k-branches for all values of k. Our investigation leads to a generation algorithm, that adds one or two new maximal cliques in each step, producing exactly the k-branches.
Fichier principal
Vignette du fichier
rr05-047.pdf (223.41 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00324551 , version 1 (08-03-2024)



Christophe Paul, Andrzej Proskurowski, Jan Arne Telle. Algorithmic Generation of Graphs of Branch-width ≤ k. WG 2006 - 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2006, Bergen, Norway. pp.206-216, ⟨10.1007/11917496_19⟩. ⟨lirmm-00324551⟩
127 View
3 Download



Gmail Facebook X LinkedIn More