𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Upper bounds on the sum of powers of the degrees of a simple planar graph

✍ Scribed by Jochen Harant; Stanislav Jendrol; Tomáš Madaras

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
131 KB
Volume
67
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

New upper bounds on the decomposability
New upper bounds on the decomposability of planar graphs
✍ Fedor V. Fomin; Dimitrios M. Thilikos 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB 👁 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for th

On some simple degree conditions that gu
On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
✍ Vu, Van H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-menti

The Order Upper Bound on Parity Embeddin
The Order Upper Bound on Parity Embedding of a Graph
✍ Thomas Zaslavsky 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 398 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is the Euler characteristic) over all surfaces S in which 1 can be parity embedde

A New Upper Bound on the Cheeger Number
A New Upper Bound on the Cheeger Number of a Graph
✍ Sorin Dragomir; Elisabetta Barletta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Using a technique developed by A. Nilli (1991, Discrete Math. 91, 207 210), we estimate from above the Cheeger number of a finite connected graph G of small degree (2(G) 5) admitting sufficiently distant edges. ## 2001 Academic Press Let G=(V(G), E(G)) be a finite connected graph. The Cheeger numb