Available in electronic format
Available in print format
Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

Light structures in infinite planar graphs without the strong isoperimetric property

Author(s): Bojan Mohar
Journal: Trans. Amer. Math. Soc. 354 (2002), 3059-3074.
MSC (2000): Primary 05B45, 52B60, 52C20, 60J10
Posted: April 2, 2002
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: It is shown that the discharging method can be successfully applied on infinite planar graphs of subexponential growth and even on those graphs that do not satisfy the strong edge isoperimetric inequality. The general outline of the method is presented and the following applications are given: Planar graphs with only finitely many vertices of degree $\le 5$ and with subexponential growth contain arbitrarily large finite submaps of the tessellation of the plane or of some tessellation of the cylinder by equilateral triangles. Every planar graph with isoperimetric number zero and with essential minimum degree $\ge3$ has infinitely many edges whose degree sum is at most 15. In particular, this holds for all graphs with minimum degree $\ge3$ and with subexponential growth. The cases without infinitely many edges whose degree sum is $\le14$ (or, similarly, $\le13$ or $\le 12$) are also considered. Several further results are obtained.


References:

1.
A. Altshuler, Hamiltonian circuits in some maps on the torus, Discrete Math. 1 (1972) 299-314. MR 45:6651

2.
K. Appel, W. Haken, Every planar map is four colorable. Part I: Discharging, Ill. J. Math. 21 (1977) 429-490. MR 58:27598a

3.
O. Baues, N. Peyerimhoff, Curvature and geometry of tessellating plane graphs, Discrete Comput. Geom. 25 (2001) 141-159. MR 2001k:57004

4.
O. V. Borodin, A generalization of Kotzig's theorem and prescribed edge coloring of planar graphs, Mat. Zametki 48 (1990) no. 6, 22-28; English transl., Math. Notes 48 (1990), 1186-1190. MR 92e:05046

5.
A. Calogero, Strong isoperimetric inequality for the edge graph of a tiling of the plane, Arch. Math. (Basel) 61 (1993) 584-595. MR 94m:52024

6.
J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984) 787-794. MR 85m:58185

7.
I. Fabrici, S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13 (1997) 245-250. MR 98h:05112

8.
P. Gerl, Random walks on graphs with a strong isoperimetric inequality, J. Theoret. Probab. 1 (1988) 171-187. MR 89g:60216

9.
M. Gromov, Hyperbolic manifolds (according to Thurston and Jorgensen), Bourbaki Seminar, Vol. 1979/80, Lecture Notes in Math. 842, Springer, Berlin-New York, 1981, pp. 40-53. MR 84b:53046

10.
M. Gromov, Hyperbolic groups. Essays in group theory, Math. Sci. Res. Inst. Publ. 8, Springer, New York, 1987, pp. 75-263. MR 89e:20070

11.
B. Grünbaum, G. C. Shephard, Analogues for tilings of Kotzig's theorem on minimal weights of edges, in ``Theory and practice of combinatorics,'' North-Holland, Amsterdam-New York, 1982, pp. 129-140. MR 86k:52015

12.
N. Robertson, D. Sanders, P. Seymour, R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997) 2-44. MR 98c:05065

13.
Zh.-X. He, O. Schramm, Hyperbolic and parabolic packings, Discrete Comput. Geom. 14 (1995) 123-149. MR 96h:52017

14.
O. Häggström, J. Jonasson, R. Lyons, Explicit isoperimetric constants, phase transitions in the random-cluster, and Bernoullicity, preprint, 2001.

15.
A. Kotzig, On the theory of Euler polyhedra (in Russian), Mat.-Fyz. Cas. Sloven. Akad. Vied 13 (1963) 20-31. MR 28:5375

16.
R. Lyons, Y. Peres, Probability on trees and networks, book manuscript, 2000.

17.
B. Mohar, Isoperimetric inequalities, growth, and the spectrum of graphs, Linear Algebra Appl. 103 (1988) 119-131. MR 89k:05071

18.
B. Mohar, Some relations between analytic and geometric properties of infinite graphs, Discrete Math. 95 (1991) 193-219. MR 93c:05113

19.
B. Mohar, Isoperimetric numbers and spectral radius of some infinite planar graphs, Math. Slovaca 42 (1992) 411-425. MR 94a:05003

20.
P. M. Soardi, Recurrence and transience of the edge graph of a tiling of the Euclidean plane, Math. Ann. 287 (1990) 613-626. MR 92b:52044

21.
T. Stehling, Über das Kotziggewicht normaler Pflasterungen, Resultate Math. 18 (1990) 347-354. MR 92a:52029

22.
W. Woess, A note on tilings and strong isoperimetric inequality, Math. Proc. Cambridge Philos. Soc. 124 (1998) 385-393. MR 99f:52026

23.
A. Zuk, On the norms of the random walks on planar graphs, Ann. Inst. Fourier (Grenoble) 47 (1997) 1463-1490. MR 99g:60127


Similar Articles:

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05B45, 52B60, 52C20, 60J10

Retrieve articles in all Journals with MSC (2000): 05B45, 52B60, 52C20, 60J10


Additional Information:

Bojan Mohar
Affiliation: Department of Mathematics, University of Ljubljana, 1111 Ljubljana, Slovenia
Email: bojan.mohar@uni-lj.si

DOI: 10.1090/S0002-9947-02-03004-0
PII: S 0002-9947(02)03004-0
Received by editor(s): March 19, 2001
Posted: April 2, 2002
Additional Notes: Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1--0502--0101--00.
Copyright of article: Copyright 2002, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google