 |
HAL-LIRMM - Open Archive |  |
Journal articles
Edge Maximal Graphs of Branchwidth k: The k-Branches
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.
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371208
Contributor : Christophe Paul <>
Submitted on : Thursday, March 26, 2009 - 9:53:30 PM
Last modification on : Tuesday, June 30, 2020 - 3:34:02 PM
Contributor : Christophe Paul <>
Submitted on : Thursday, March 26, 2009 - 9:53:30 PM
Last modification on : Tuesday, June 30, 2020 - 3:34:02 PM