๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Some results on graphs without long induced paths

โœ Scribed by Dong, Jinquan

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
294 KB
Volume
22
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let I(t) be the set of integers with the property that in every Pt-free connected graph G, the i-center C,(G) induces a connected subgraph. What is the minimum element of /(t)? In this paper, we prove that this minimum is [2t/3] -1 if t = 0 or Z(mod3) and is [ 2 t / 3 ] otherwise. Furthermore, as conjectured by G. Bacso and Z. Tuza, the set /(t) is an interval. In addition, a counterexample to a conjecture proposed by G. Bacso and Z. Tuza is also presented.

๐Ÿ“œ SIMILAR VOLUMES

On the diameter ofi-center in a graph wi
On the diameter ofi-center in a graph without long induced paths
โœ Dong, Jinquan ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 117 KB ๐Ÿ‘ 1 views

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 c