skip to main content

On self-duality of branchwidth in graphs of bounded genus

Sau, Ignasi ; Thilikos, Dimitrios M.

Discrete Applied Mathematics, 2011, Vol.159(17), pp.2184-2186 [Periódico revisado por pares]

Texto completo disponível

Ver todas as versões
Citações Citado por
  • Título:
    On self-duality of branchwidth in graphs of bounded genus
  • Autor: Sau, Ignasi ; Thilikos, Dimitrios M.
  • Assuntos: Graphs on Surfaces ; Branchwidth ; Duality ; Polyhedral Embedding
  • É parte de: Discrete Applied Mathematics, 2011, Vol.159(17), pp.2184-2186
  • Descrição: A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. Self-duality has been examined for several width parameters, such as branchwidth, pathwidth, and treewidth. In this paper, we give a direct proof of the self-duality of branchwidth in graphs embedded in some surface. In this direction, we prove that bw ( G ∗ ) ≤ 6 ⋅ bw ( G ) + 2 g − 4 for any graph G embedded in a surface of Euler genus g . Highlights ► A graph parameter is self-dual in a class of graphs embeddable in a surface if its value does not change in the dual graph by more than a constant factor. ► Self-duality has been examined for several width parameters, such as branchwidth, pathwidth, and treewidth. ► In this paper, we give a direct proof of the self-duality of branchwidth in graphs embedded in some surface. ► Namely, we prove that bw ( G ∗ ) ≤ 6 ⋅ bw ( G ) + 2 g − 4 for any graph G embedded in a surface of Euler genus g .
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.