𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edge-isoperimetric problems for cartesian powers of regular graphs

✍ Scribed by Sergei L. Bezrukov; Robert Elsässer

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
437 KB
Volume
307
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We consider an edge-isoperimetric problem (EIP) on the cartesian powers of graphs. One of our objectives is to extend the list of graphs for whose cartesian powers the lexicographic order provides nested solutions for the EIP. We present several new classes of such graphs that include as special cases all presently known graphs with this property. Our new results are applied to derive best possible edge-isoperimetric inequalities for the cartesian powers of arbitrary regular, resp. regular bipartite, graphs with a high density.

📜 SIMILAR VOLUMES

Lower bound of cyclic edge connectivity
Lower bound of cyclic edge connectivity for n-extendability of regular graphs
✍ Dingjun Lou; D.A. Holton 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 701 KB

A cyclically m-edge-connected n-connected k-regular graph is called an (m.n.k) graph. It is proved that for any m > 0 and k 2 3, there is an (m, k, k) bipartite graph. A graph G is n-extendable if every matching of size n in G lies in a perfect matching of G. We prove the existence of a (k2-1, k + 1

On the edge-coloring problem for a class
On the edge-coloring problem for a class of 4-regular maps
✍ F. Jaeger; H. Shank 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 1 views

## Abstract A (plane) 4‐regular map __G__ is called __C__‐simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (__G__) is the smallest integer __k__ such that the curves of __G__ can be colored with __k__ colors in such a way that no two curves

Erratum: On the edge-coloring problem fo
Erratum: On the edge-coloring problem for a class of 4-regular maps
✍ F. Jaeger; H. Shank 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 37 KB 👁 1 views

On p. 272 of the above article, paragraph # 3 is incomplete. It should read as the following: Hence to prove Proposition 4 it is enough to show that the edges of Q 4 can be colored with 4 colors in such a way that each square has one edge of each color. Such a coloring is displayed on the following