On diameters and radii of bridged graphs
type: Item
instance of: scholarly article
title: On diameters and radii of bridged graphs
zbMATH Open document ID: 0667.05036
DOI: 10.1016/0012-365X(89)90268-9
author: Martin Farber
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: A subgraph H of a graph G is isometric if the distance between any pair of vertices in H is the same as that in G. A graph is bridged if it contains no isometric cycles of length greater than 3. This class includes, as a proper subclass, the class of chordal graphs, i.e., graphs with no induced cycle of length greater than 3. Denoting the diameter and radius of a graph G by d(G) and r(G), respectively, it follows immediately that \(\lceil d(G)\rceil \leq r(G)\leq d(G)\). Let \(T_ p\) be the graph obtained by triangulating an equilateral triangle of side p with equilateral triangles of side 1. \textit{G. J. Chang} and \textit{G. L. Newhauser} [SIAM J. Algebraic Discrete Methods 5, 332-345 (1984; Zbl 0576.05054)] showed that if G is chordal then \(2r(g)\leq d(G)+2\) and if, furthermore, G contains no induced \(T_ 2\), then \(2r(G)\leq d(G)+1.\) Generalizing this, the author shows that if G is a bridged graph containing no isometric \(T_ p\), then \(6r(G)\leq 3d(G)+p+3.\)
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4091544
zbMATH Keywords: chordal graphs
zbMATH Keywords: bridged graph
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: On bridged graphs and cop-win graphs
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: On rigid circuit graphs
cites work: Bridged graphs and geodesic convexity
cites work: Convexity in Graphs and Hypergraphs
cites work: On local convexity in graphs
cites work: On the null-homotopy of bridged graphs
cites work: On powers and centers of chordal graphs
cites work: Conditions for invariance of set diameters under d-convexification in a graph
description: scientific article; zbMATH DE number 4091544