The Laplacian lattice of a graph under a simplicial distance function

DOI10.1016/J.EJC.2013.01.010MaRDI QIDQ2444735zbMATH OpenOpenAlexFDO

Authors Madhusudan Manjunath

Publication date 11 April 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.7246

zbMATH Keywords

covering densitiesLaplacian lattices of undirected connected multigraphspacking densities

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We provide a complete description of important geometric invariants of the Laplacian lattice of a multigraph under the distance function induced by a regular simplex, namely Voronoi Diagram, Delaunay Triangulation, Delaunay Polytope and its combinatorial structure, Shortest Vectors, Covering and Packing Radius. We use this information to obtain the following results: i. Every multigraph defines a Delaunay triangulation of its Laplacian lattice and this Delaunay triangulation contains complete information of the multigraph up to isomorphism. ii. The number of multigraphs with a given Laplacian lattice is controlled, in particular upper bounded, by the number of different Delaunay triangulations. iii. We obtain formulas for the covering and packing densities of a Laplacian lattice and deduce that in the space of Laplacian lattices of undirected connected multigraphs, the Laplacian lattices of highly connected multigraphs such as Ramanujan multigraphs possess good covering and packing properties.

Recommendations

• Laplacian integral multigraphs
• scientific article; zbMATH DE number 510842
• scientific article; zbMATH DE number 1031379
• On the geometry and Laplacian of a graph
• Laplacian integral multigraphs. II

Cites work

• Applications of dimensionality reduction and exponential sums to graph automorphism
• Expander graphs and their applications
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3987367 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 44906 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• Matrix Analysis
• Monomials, binomials and Riemann-Roch
• Primer for the algebraic geometry of sandpiles
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Riemann-Roch for sub-lattices of the root lattice \(A_n\)
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• Torelli theorem for graphs and tropical curves
• Trees, parking functions, syzygies, and deformations of monomial ideals

Cited in

(8)

• Connes' distance function on one-dimensional lattices
• Laplacian simplices associated to digraphs
• Brill-Noether existence on graphs via \(\mathbb{R}\)-divisors, polytopes and lattices
• On Laplacian monopoles
• Voronoi polytopes for polyhedral norms on lattices
• Tropical medians by transportation
• Asymmetric tropical distances and power diagrams
• Polyhedral combinatorics of bisectors

This page was built for publication: The Laplacian lattice of a graph under a simplicial distance function

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