𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach

✍ Scribed by Arvind, V.; Cheng, Christine T.; Devanur, Nikhil R.

Book ID
118196982
Publisher
Society for Industrial and Applied Mathematics
Year
2008
Tongue
English
Weight
429 KB
Volume
22
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the maximum number of cycles in a pla
On the maximum number of cycles in a planar graph
✍ R. E. L. Aldred; Carsten Thomassen πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__β€‰βˆ’β€‰__p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__β€‰βˆ’β€‰1^ = __o__(2^__r__β€‰βˆ’β€‰1^) cycles. The planar result is best possib