Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9662369 | Computers & Mathematics with Applications | 2005 | 6 Pages |
Abstract
The outerthickness of a graph is the minimum number of outerplanar subgraphs into which the graph can be decomposed. We give lower and upper bounds for outerthickness in the terms of the minimum and maximum degree of a graph. Let δ be the minimum degree and Î the maximum degree of a graph G. We show that the following bounds hold for outerthickness: [δ/4] ⤠Îo(G) ⤠[Î/2]. We also discuss the possibility of determining the upper bound for outerthickness using the number of edges of a given graph.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
T. Poranen, E. Mäkinen,