𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Volume entropy, weighted girths and stable balls on graphs

✍ Scribed by Florent Balacheff

Book ID
102345537
Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
174 KB
Volume
55
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove new isoperimetric inequalities on graphs involving quantities linked with concepts from differential geometry. First, we bound from above the product of the volume entropy (defined as the log of the exponential growth rate of the universal cover) and the girth of weighted graphs in terms of their cyclomatic number. In a second part, we study a natural polyhedron associated to a weighted graph: the stable ball. In particular, we relate the volume of this polyhedron, the weight of the graph and its cyclomatic number. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 291–305, 2007

📜 SIMILAR VOLUMES

Maximum Weight Stable Set on graphs with
Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time
✍ Andreas Brandstädt; Suhail Mahfud 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 112 KB

Minty has shown that the Maximum Weight Stable Set (MWS) Problem can be solved in polynomial time when restricted to claw-free graphs. We show that the structure of graphs being both claw-free and co-claw-free is very simple which implies bounded clique width for this graph class. It is known that f