Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871792 | Discrete Applied Mathematics | 2017 | 15 Pages |
Abstract
Using the characteristic property of chordal graphs that they are the intersection graphs of subtrees of a tree, Erich Prisner showed that every chordal graph admits an eccentricity 2-approximating spanning tree. That is, every chordal graph G has a spanning tree T such that eccT(v)âeccG(v)â¤2 for every vertex v, where eccG(v) (eccT(v)) is the eccentricity of a vertex v in G (in T, respectively). Using only metric properties of graphs, we extend that result to a much larger family of graphs containing among others chordal graphs, the underlying graphs of 7-systolic complexes and plane triangulations with inner vertices of degree at least 7. Furthermore, based on our approach, we propose two heuristics for constructing eccentricity k-approximating trees with small values of k for general unweighted graphs. We validate those heuristics on a set of real-world networks and demonstrate that all those networks have very good eccentricity approximating trees.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Feodor F. Dragan, Ekkehard Köhler, Hend Alrasheed,