✦ LIBER ✦
On the diameter ofi-center in a graph without long induced paths
✍ Scribed by Dong, Jinquan
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 117 KB
- Volume
- 30
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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.