Eccentricity function in distance-hereditary graphs

DOI10.1016/J.TCS.2020.05.004zbMATH Open1453.05026arXiv1907.05445OpenAlexW2959517763MaRDI QIDQ784475FDOQ784475

Authors: Feodor F. Dragan, Heather M. Guarnera 

Publication date: 3 August 2020

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

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.

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

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

zbMATH Keywords

diametercenterradiuslinear-time algorithmdistance-hereditary grapheccentricity function

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• 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
• Title not available (Why is that?)
• The axiomatic characterization of the interval function of distance hereditary graphs

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)