Slimness of graphs

zbMATH Open1411.05072arXiv1705.09797MaRDI QIDQ5377232FDOQ5377232

Abdulhakeem O. Mohammed, Feodor F. Dragan

Publication date: 23 May 2019

Abstract: Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph $G=(V,E)$, a geodesic triangle $$ with $x,y,zinV$ is the union $P(x,y)cupP(x,z)cupP(y,z)$ of three shortest paths connecting these vertices. A geodesic triangle $$ is called $delta$-slim if for any vertex $uinV$ on any side $P(x,y)$ the distance from $u$ to $P(x,z)cupP(y,z)$ is at most $delta$, i.e. each path is contained in the union of the $delta$-neighborhoods of two others. A graph $G$ is called $delta$-slim, if all geodesic triangles in $G$ are $delta$-slim. The smallest value $delta$ for which $G$ is $delta$-slim is called the slimness of $G$. In this paper, using the layering partition technique, we obtain sharp bounds on slimness of such families of graphs as (1) graphs with cluster-diameter $Delta(G)$ of a layering partition of $G$, (2) graphs with tree-length $lambda$, (3) graphs with tree-breadth $ho$, (4) $k$-chordal graphs, AT-free graphs and HHD-free graphs. Additionally, we show that the slimness of every 4-chordal graph is at most 2 and characterize those 4-chordal graphs for which the slimness of every of its induced subgraph is at most 1.

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

Recommendations

• Chordality properties and hyperbolicity on graphs
• Slim graphs
• On the hyperbolicity of chordal graphs
• On slim graphs, even pairs, and star-cutsets
• scientific article; zbMATH DE number 23019

zbMATH Keywords

hyperbolicitychordalitytree-lengthslimnesslayering partitionmetric tree-like structures

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Cited In (8)

• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• The diameter of AT‐free graphs
• Thin strip graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Graphs with small book thickness
• Fellow travelers phenomenon present in real-world networks
• Title not available (Why is that?)
• \(M\)-slenderness

This page was built for publication: Slimness of graphs

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