Linear layouts measuring neighbourhoods in graphs
Autor: | Frank Gurski |
---|---|
Rok vydání: | 2006 |
Předmět: |
Discrete mathematics
Neighbourhoods in graphs Graph Layout Voltage graph Linear clique-width Distance-regular graph Planar graph law.invention Theoretical Computer Science Combinatorics symbols.namesake Graph bandwidth Cut-width law Graph layout Line graph symbols Discrete Mathematics and Combinatorics Complement graph Mathematics Universal graph Linear NLC-width |
Zdroj: | Discrete Mathematics. 306(15):1637-1650 |
ISSN: | 0012-365X |
DOI: | 10.1016/j.disc.2006.03.048 |
Popis: | In this paper we introduce the graph layout parameter neighbourhood-width as a variation of the well-known cut-width. The cut-width of a graph G=(V,E) is the smallest integer k, such that there is a linear layout ϕ:V→{1,…,|V|}, such that for every 1⩽ii. The neighbourhood-width of a graph is the smallest integer k, such that there is a linear layout ϕ, such that for every 1⩽ii.We show that the neighbourhood-width of a graph differs from its linear clique-width or linear NLC-width at most by one. This relation is used to show that the minimization problem for neighbourhood-width is NP-complete.Furthermore, we prove that simple modifications of neighbourhood-width imply equivalent layout characterizations for linear clique-width and linear NLC-width.We also show that every graph of path-width k or cut-width k has neighbourhood-width at most k+2 and we give several conditions such that graphs of bounded neighbourhood-width have bounded path-width or bounded cut-width. |
Databáze: | OpenAIRE |
Externí odkaz: |