Feodor F. Dragan ; Abdulhakeem Mohammed - Slimness of graphs

dmtcs:4288 - Discrete Mathematics & Theoretical Computer Science, March 4, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-10
Slimness of graphsArticle

Authors: Feodor F. Dragan ; Abdulhakeem Mohammed

    Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph $G=(V,E)$, a geodesic triangle $\bigtriangleup(x,y,z)$ with $x, y, z\in V$ is the union $P(x,y) \cup P(x,z) \cup P(y,z)$ of three shortest paths connecting these vertices. A geodesic triangle $\bigtriangleup(x,y,z)$ is called $\delta$-slim if for any vertex $u\in V$ on any side $P(x,y)$ the distance from $u$ to $P(x,z) \cup P(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 $\rho$, (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.

    Volume: Vol. 21 no. 3
    Section: Graph Theory
    Published on: March 4, 2019
    Accepted on: February 20, 2019
    Submitted on: February 15, 2018
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 770 times.
    This article's PDF has been downloaded 590 times.