Modulus on graphs as a generalization of standard graph theoretic quantities
Authors:
Nathan Albin, Megan Brunner, Roberto Perez, Pietro Poggi-Corradini and Natalie Wiens
Journal:
Conform. Geom. Dyn. 19 (2015), 298-317
MSC (2010):
Primary 90C35
DOI:
https://doi.org/10.1090/ecgd/287
Published electronically:
December 4, 2015
MathSciNet review:
3430866
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: This paper presents new results for the modulus of families of walks on a graph—a discrete analog of the modulus of curve families due to Beurling and Ahlfors. Particular attention is paid to the dependence of the modulus on its parameters. Modulus is shown to generalize (and interpolate among) three important quantities in graph theory: shortest path, effective resistance, and max-flow or min-cut.
- Lars Valerian Ahlfors, Collected papers. Vol. 1, Contemporary Mathematicians, Birkhäuser, Boston, Mass., 1982. 1929–1955; Edited with the assistance of Rae Michael Shortt. MR 688648
- N. Albin and P. Poggi-Corradini, The dual method for $p$-modulus on graphs. Preprint.
- N. Albin and P. Poggi-Corradini, F. Darabi Sahneh, and M. Goering, Modulus of families of walks on graphs. arXiv:1401.7640 (http://arxiv.org/abs/1403.5750).
- Arne Beurling, The collected works of Arne Beurling. Vol. 1, Contemporary Mathematicians, Birkhäuser Boston, Inc., Boston, MA, 1989. Complex analysis; Edited by L. Carleson, P. Malliavin, J. Neuberger and J. Wermer. MR 1057613
- James A. Clarkson, Uniformly convex spaces, Trans. Amer. Math. Soc. 40 (1936), no. 3, 396–414. MR 1501880, DOI https://doi.org/10.1090/S0002-9947-1936-1501880-4
- R. J. Duffin, The extremal length of a network, J. Math. Anal. Appl. 5 (1962), 200–215. MR 143468, DOI https://doi.org/10.1016/S0022-247X%2862%2980004-3
- Josh Ericson, Pietro Poggi-Corradini, and Hainan Zhang, Effective resistance on graphs and the epidemic quasimetric, Involve 7 (2014), no. 1, 97–124. MR 3127324, DOI https://doi.org/10.2140/involve.2014.7.97
- L. R. Ford Jr. and D. R. Fulkerson, Maximal flow through a network, Canadian J. Math. 8 (1956), 399–404. MR 79251, DOI https://doi.org/10.4153/CJM-1956-045-5
- Arpita Ghosh, Stephen Boyd, and Amin Saberi, Minimizing effective resistance of a graph, SIAM Rev. 50 (2008), no. 1, 37–66. MR 2403057, DOI https://doi.org/10.1137/050645452
- Peter Haïssinsky, Empilements de cercles et modules combinatoires, Ann. Inst. Fourier (Grenoble) 59 (2009), no. 6, 2175–2222 (French, with English and French summaries). MR 2640918
- Juha Heinonen, Lectures on analysis on metric spaces, Universitext, Springer-Verlag, New York, 2001. MR 1800917
- D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1-4, 81–95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991). MR 1219566, DOI https://doi.org/10.1007/BF01164627
- R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
- Oded Schramm, Square tilings with prescribed combinatorics, Israel J. Math. 84 (1993), no. 1-2, 97–118. MR 1244661, DOI https://doi.org/10.1007/BF02761693
- H. Shakeri, P. Poggi-Corradini, C. Scoglio, and N. Albin, Generalized network measures based on modulus of families of walks. Preprint.
- G. F. Young, L. Scardovi, and N. E. Leonard, A new notion of effective resistance for directed graphs-Part I: Definition and properties. http://arxiv.org/abs/1310.5163.
Retrieve articles in Conformal Geometry and Dynamics of the American Mathematical Society with MSC (2010): 90C35
Retrieve articles in all journals with MSC (2010): 90C35
Additional Information
Nathan Albin
Affiliation:
Department of Mathematics, Kansas State University, 138 Cardwell Hall, Manhattan, Kansas 66506
Email:
albin@math.ksu.edu; pietro@math.ksu.edu
Keywords:
Modulus of families of walks,
effective resistance,
shortest path,
max-flow,
min-cut
Received by editor(s):
June 1, 2015
Received by editor(s) in revised form:
October 30, 2015
Published electronically:
December 4, 2015
Additional Notes:
This material is based upon work supported by the National Science Foundation under Grant No. 126287 (Albin, Brunner, Perez, Wiens), through Kansas State University’s 2014 Summer Undergraduate Mathematics Research program, and under Grant Nos. 1201427 (Poggi-Corradini) and 1515810 (Albin)
Article copyright:
© Copyright 2015
American Mathematical Society
