Premium
On the diameter of i ‐center in a graph without long induced paths
Author(s) -
Dong Jinquan
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199903)30:3<235::aid-jgt8>3.0.co;2-c
Subject(s) - combinatorics , bound graph , mathematics , path graph , graph , vertex (graph theory) , induced subgraph , upper and lower bounds , vertex connectivity , discrete mathematics , graph power , line graph , mathematical analysis
A graph G is said to be P t ‐free if it does not contain an induced path on t vertices. The i ‐center C i ( G ) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i . Denote by I ( t ) the set of natural numbers i , ⌊ t /2⌋ ≤ i ≤ t − 2, with the property that, in every connected P t ‐free graph G , the i ‐center C i ( G ) of G induces a connected subgraph of G . In this article, the sharp upper bound on the diameter of G [ C i ( G )] is established for every i ∈ I ( t ). The sharp lower bound on I ( t ) is obtained consequently. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 235–241, 1999