Edge Maximal Graphs of Branchwidth k: The k-Branches

Christophe Paul 1 Jan Arne Telle 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Treewidth and branchwidth are two closely related connectivity parameters of graphs. Graphs of treewidth at most k have well-known alternative characterizations as subgraphs of chordal graphs and as partial k-trees. In this paper we give analogous alternative characterizations for graphs of branchwidth at most k. We first show that they are the subgraphs of chordal graphs where every maximal clique X has three subsets of size at most k each such that any two subsets have union X, with the property that every minimal separator contained in X is contained in one of the three subsets. Secondly, we give a characterization of the edge-maximal graphs of branchwidth k, that we call k-branches.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2009, 309 (6), pp.1467-1475
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371208
Contributeur : Christophe Paul <>
Soumis le : jeudi 26 mars 2009 - 21:53:30
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00371208, version 1

Collections

Citation

Christophe Paul, Jan Arne Telle. Edge Maximal Graphs of Branchwidth k: The k-Branches. Discrete Mathematics, Elsevier, 2009, 309 (6), pp.1467-1475. 〈lirmm-00371208〉

Partager

Métriques

Consultations de la notice

77