×
Bacher, Roland; de la Harpe, Pierre; Nagnibeda, Tatiana

The lattice of integral flows and the lattice of integral cuts on a finite graph. (English) Zbl 0891.05062

Bull. Soc. Math. Fr. 125, No. 2, 167-198 (1997).
Authors’ abstract: The set of integral flows on a finite graph \(\Gamma\) is naturally an integral lattice \(\Lambda^1 (\Gamma)\) in the Euclidean space \(\text{Ker} (\Delta_1)\) of harmonic real-valued functions on the edge set of \(\Gamma\). Various properties of \(\Gamma\) (bipartite character, girth, complexity, separability) are shown to correspond to properties of \(\Lambda^1 (\Gamma)\) (parity, minimal norm, determinant, decomposability). The dual lattice of \(\Lambda^1 (\Gamma)\) is identified to the integral cohomology \(H^1(\Gamma, \mathbb{Z})\) in \(\text{Ker} (\Delta_1)\). Analogous characterizations are shown to hold for the lattice of integral cuts and appropriate properties of the graph (Eulerian character, edge connectivity, complexity, separability). These lattices have a determinant group which plays for graphs the same role as Jacobians for closed Riemann surfaces. It is then harmonic functions on a graph (with values in an abelian group) which take place of holomorphic mappings.
Reviewer: Ian Anderson (Glasgow)

Cited in 3 Reviews
Cited in 80 Documents

MSC:

05C99 Graph theory
11E39 Bilinear and Hermitian forms

Keywords:

integral flows; integral lattice; Jacobians
PDF BibTeX XML Cite
\textit{R. Bacher} et al., Bull. Soc. Math. Fr. 125, No. 2, 167--198 (1997; Zbl 0891.05062)
Full Text: DOI Numdam EuDML Link

References:

[1] BERMAN (K.A.) . - Bicycles and Spanning Trees , SIAM J. Alg. Disc. Meth., t. 7, 1986 , p. 1-12. MR 87d:05103 | Zbl 0588.05016 · Zbl 0588.05016
[2] BIGGS (N.) . - Algebraic Graph Theory . - Cambridge University Press, 1974 (Second Edition 1993). MR 50 #151 | Zbl 0284.05101 · Zbl 0284.05101
[3] BIGGS (N.) . - Homological Coverings of Graphs , J. London Math. Soc (2), t. 30, 1984 , p. 1-14. MR 86e:05050 | Zbl 0518.05038 · Zbl 0518.05038
[4] BIGGS (N.) . - The Potential of Potential Theory , Preprint, London School of Economics, 1994 , Preprint to appear in the volume ”The Future of Graph Theory”.
[5] BIGGS (N.) . - Algebraic Potential Theory on Graphs , Bull. London Math. Soc., to appear. Zbl 0892.05033 · Zbl 0892.05033
[6] BOLLOBAS (B.) . - Extremal Graph Theory . - Academic Press, 1978 . MR 80a:05120 | Zbl 0419.05031 · Zbl 0419.05031
[7] BOREL (A.) . - Cohomologie de certains groupes discrets et laplacien p-adique , Séminaire Bourbaki, t. 437, 1973 / 1974 . Numdam | Zbl 0376.22009 · Zbl 0376.22009
[8] BOURBAKI (N.) . - Algèbre, chapitres 4 à 7 . - Masson, 1981 . Zbl 0498.12001 · Zbl 0498.12001
[9] BROUWER (A.E.) , COHEN (A.M.) and NEUMAIER (A.) . - Distance Regular Graphs . - Springer-Verlag, 1989 . MR 90e:05001 | Zbl 0747.05073 · Zbl 0747.05073
[10] BROUWER (A.E.) and VAN EIJL (C.A.) . - On the p-rank of the adjacency matrices of strongly regular graphs , J. Alg. Combinatorics, t. 1, 1992 , p. 329-346. MR 94b:05217 | Zbl 0780.05039 · Zbl 0780.05039
[11] BRUALDI (R.) and RYSER (H.J.) . - Combinatorial Matrix Theory . - Cambridge Univ. Press, 1991 . MR 93a:05087 | Zbl 0746.05002 · Zbl 0746.05002
[12] BRYLAWSKI (T.) and J. Oxley . - The Tutte Polynomial and its Applications , in ”Matroid Applications”, N. White Ed., Cambridge University Press, 1992 , p. 123-225. MR 93k:05060 | Zbl 0769.05026 · Zbl 0769.05026
[13] CONWAY (J.H.) and N.J.A. Sloane . - Sphere Packings, Lattices and Groups . - Springer-Verlag, 1991 . · Zbl 0737.11017
[14] CVETKOVIC (D.M.) , DOOB (M.) and SACHS (H.) . - Spectra of Graphs . - Academic Press, 1980 . MR 81i:05054
[15] DIXMIER (J.) . - Les C*-algèbres et leurs représentations , 2e édition. - Gauthier-Villars, 1969 . Zbl 0174.18601 · Zbl 0174.18601
[16] ECKMANN (B.) . - Harmonische Funktionen und Radwertaufgaben in einem Komplex , Comment. Math. Helv., t. 17, 1944 / 1945 , p. 240-255. MR 7,138f | Zbl 0061.41106 · Zbl 0061.41106
[17] KERVAIRE (M.) . - Unimodular Lattices with a Complete Root System , L’Enseignement mathématique, t. 40, 1994 , p. 59-104. MR 95g:11063 | Zbl 0808.11024 · Zbl 0808.11024
[18] MARGOLIN (R.S.) . - Representations of M12 , J. Algebra, t. 156, 1993 , p. 362-369. MR 94c:20029 | Zbl 0791.20009 · Zbl 0791.20009
[19] NARASIMHAN (R.) . - Compact Riemann Surfaces . - Birkhäuser, 1992 . MR 93j:30049 | Zbl 0758.30002 · Zbl 0758.30002
[20] ODA (T.) , SESHADRI (C.S.) . - Compactification of the Generalized Jacobian Variety , Trans. AMS, t. 253, 1979 , p. 1-90. MR 82e:14054 | Zbl 0418.14019 · Zbl 0418.14019
[21] OXLEY (J.G.) . - Matroid Theory . - Oxford University Press, 1992 . MR 94d:05033 | Zbl 0784.05002 · Zbl 0784.05002
[22] ROTMAN (J.J.) . - An Introduction to Algebraic Topology . - Springer, 1988 . MR 90e:55001 | Zbl 0661.55001 · Zbl 0661.55001
[23] SCHARLAU (W.) . - Quadratic and Hermitian Forms . - Springer-Verlag, 1985 . MR 86k:11022 | Zbl 0584.10010 · Zbl 0584.10010
[24] SERRE (J.-P.) . - Arbres, amalgames , SL2. - Astérique, t. 46, Soc. Math. France, 1977 . Zbl 0369.20013 · Zbl 0369.20013
[25] VAN LINT (J.H.) and WILSON (R.M.) . - A Course in Combinatorics . - Cambridge University Press, 1992 . Zbl 0769.05001 · Zbl 0769.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.