✦ LIBER ✦

Graphs with Branchwidth at Most Three

✍ Scribed by Hans L Bodlaender; Dimitrios M Thilikos

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 257 KB
Volume: 32
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1011

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition.

📜 SIMILAR VOLUMES

Generating cycles in graphs with at most

Generating cycles in graphs with at most one end

✍ Henning Bruhn 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB 👁 1 views

## Abstract Answering a question of Halin, we prove that in a 3‐connected graph with at most one end the cycle space is generated by induced non‐separating cycles. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 342–349, 2003

Cubic graphs with most automorphisms

✍ Rev. Michael A. van Opstall; Răzvan Veliche 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 262 KB

## Abstract We give a sharp bound for the order of the automorphism group of a connected simple cubic graph on a given number of vertices. For each number of vertices we construct a graph, unique in special cases, attaining the bound. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 99–115, 2010

Maximal independent sets in graphs with

Maximal independent sets in graphs with at most r cycles

✍ Goh Chee Ying; Koh Khee Meng; Bruce E. Sagan; Vincent R. Vatter 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

## Abstract We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with __n__ vertices and at most __r__ cycles. The second family is all graphs of the first family which are connected and satisfy __n__ ≥ 3__r__. © 2006 Wiley Period

Labelled graphs with vertices of degree

Labelled graphs with vertices of degree at least three

✍ I. P. Goulden; D. M. Jackson 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 463 KB 👁 1 views

The generating function for labelled graphs in which each vertex has degree at least three is obtained by the Principle of Inclusion and Exclusion. Asymptotic and explicit values for the coefficients are calculated in the connected case. The results are extended to bipartite graphs.

The chromaticity of complete bipartite g

The chromaticity of complete bipartite graphs with at most one edge deleted

✍ C. P. Teo; K. M. Koh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB 👁 1 views

## Abstract Let __K(p, q), p ≤ q__, denote the complete bipartite graph in which the two partite sets consist of __p__ and __q__ vertices, respectively. In this paper, we prove that (1) the graph __K(p, q)__ is chromatically unique if __p__ ≥ 2; and (2) the graph __K(p, q)__ ‐ __e__ obtained by del

Maximal and maximum independent sets in

Maximal and maximum independent sets in graphs with at most r cycles

✍ Bruce E. Sagan; Vincent R. Vatter 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB 👁 2 views

## Abstract Let __m__(__G__) denote the number of maximal independent sets of vertices in a graph __G__ and let __c__(__n__,__r__) be the maximum value of __m__(__G__) over all connected graphs with __n__ vertices and at most __r__ cycles. A theorem of Griggs, Grinstead, and Guichard gives a formul