Edge Maximal Graphs of Branchwidth k: The k-Branches - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2009

Edge Maximal Graphs of Branchwidth k: The k-Branches

Christophe Paul
Jan Arne Telle
  • Fonction : Auteur
  • PersonId : 889063

Résumé

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.

Dates et versions

lirmm-00371208 , version 1 (26-03-2009)

Identifiants

Citer

Christophe Paul, Jan Arne Telle. Edge Maximal Graphs of Branchwidth k: The k-Branches. Discrete Mathematics, 2009, 309 (6), pp.1467-1475. ⟨10.1016/j.disc.2008.02.030⟩. ⟨lirmm-00371208⟩
97 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More