Bounds for isoperimetric constants of infinite plane graphs

DOI10.1016/S0166-218X(00)00287-0MaRDI QIDQ5951965zbMATH OpenOpenAlexWikidataFDO

Authors Serge Lawrencenko, Michael D. Plummer, Xiaoya Zha

Publication date 3 June 2002

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(00)00287-0

zbMATH Keywords

isoperimetric numberplanar graphtessellation

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Isoperimetric problems for polytopes (52B60) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Review text

If \(G\) is an infinite planar graph with minimum degree \(d\geq 7\), then \(G\) behaves like a manifold with constant negative curvature. This implies that the discrete analogue of the Cheeger constant, called the isoperimetric number, is positive for such a graph. This fact was first observed by \textit{J. Dodziuk} [Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Am. Math. Soc. 284, 787-794 (1984; Zbl 0512.39001)] and was later treated by several other authors (see a recent paper by the reviewer [Light structures in infinite planar graphs without the strong isoperimetric property, Trans. Am. Math. Soc. 354, 3059-3074 (2002)]). In the present paper, an improved lower bound for the isoperimetric number of infinite planar graphs with one end is derived.

Recommendations

• Isoperimetric constants of infinite plane graphs
• Light structures in infinite planar graphs without the strong isoperimetric property
• Isoperimetric Constants of (d,f)-Regular Planar Graphs
• scientific article; zbMATH DE number 97634
• Infinite Planar Graphs with Non-negative Combinatorial Curvature

Cites work

• A Survey on Spectra of infinite Graphs
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Edge-transitive planar graphs
• Embeddings of infinite graphs
• Genus bounds for embeddings with large minimum degree and representativity
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 97634 (Why is no real title available?)
• scientific article; zbMATH DE number 691164 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• Isoperimetric constants and the first eigenvalue of a compact riemannian manifold
• Isoperimetric inequalities, growth, and the spectrum of graphs
• Isoperimetric numbers of graphs
• L 2 -Cohomology of Noncompact Surfaces
• The Spectral Radius of infinite Graphs

Cited in

(12)

• Asymptotic connectivity of infinite graphs
• Isoperimetric inequalities, growth, and the spectrum of graphs
• Isoperimetric constants of infinite plane graphs
• Separating cycles and isoperimetric inequalities in the uniform infinite planar quadrangulation
• The isoperimetric and Kazhdan constants associated to a Paley graph
• Isoperimetric Constants of (d,f)-Regular Planar Graphs
• Growth and isoperimetric profile of planar graphs
• Strong isoperimetric inequalities and combinatorial curvatures on multiply connected planar graphs
• scientific article; zbMATH DE number 97634 (Why is no real title available?)
• Light structures in infinite planar graphs without the strong isoperimetric property
• Geodesics in non-positively curved plane tessellations
• Asymptotic connectivity of hyperbolic planar graphs

This page was built for publication: Bounds for isoperimetric constants of infinite plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951965)