Eccentricity function in distance-hereditary graphs

DOI10.1016/J.TCS.2020.05.004MaRDI QIDQ784475zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Heather M. Guarnera

Publication date 3 August 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

diametercenterradiuslinear-time algorithmdistance-hereditary grapheccentricity function

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12)

Abstract: A graph $G=(V,E)$ is distance hereditary if every induced path of $G$ is a shortest path. In this paper, we show that the eccentricity function $e(v)=maxd(v,u):uinV$ in any distance-hereditary graph $G$ is almost unimodal, that is, every vertex $v$ with $e(v)>rad(G)+1$ has a neighbor with smaller eccentricity. Here, $rad(G)=mine(v):vinV$ is the radius of graph $G$. Moreover, we use this result to fully characterize the centers of distance-hereditary graphs. Several bounds on the eccentricity of a vertex with respect to its distance to the center of $G$ or to the ends of a diametral path are established. Finally, we propose a new linear time algorithm to compute all eccentricities in a distance-hereditary graph.

Recommendations

• Centers and medians of distance-hereditary graphs
• scientific article; zbMATH DE number 841632
• Dominating cliques in distance-hereditary graphs
• Minimum eccentricity shortest paths in some structured graph classes
• A linear-time algorithm for solving the center problem on weighted cactus graphs

Cites work

• scientific article; zbMATH DE number 23019 (Why is no real title available?)
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
• Centers and medians of distance-hereditary graphs
• Centers of 2–Trees
• Centers of maximal outerplanar graphs
• Centers of triangulated graphs
• Convexity and HHD-Free Graphs
• Distance approximating spanning trees
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• Eccentricity approximating trees
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Eccentricity-approximating trees in chordal graphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Network Analysis

Cited in

(8)

• The axiomatic characterization of the interval function of distance hereditary graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• Centers and medians of distance-hereditary graphs
• Helly-gap of a graph and vertex eccentricities
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
• scientific article; zbMATH DE number 175723 (Why is no real title available?)

This page was built for publication: Eccentricity function in distance-hereditary graphs

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