𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A characterization of graphs without long induced paths

✍ Scribed by Gábor Bacsó; Zsolt Tuza

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
461 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In a connected graph define the k‐center as the set of vertices whose distance from any other vertex is at most k. We say that a vertex set S d‐dominates G if for every vertex x there is a y ∈ S whose distance from x is at most d.

Call a graph P~t~‐free if it does not contain a path on t vertices as an induced subgraph. We prove that a connected graph is P~2k‐1~‐free (P~2k~‐free) if and only if each of its connected induced subgraphs H satisfy the following property: The k‐center of H (k ‐ 1)‐dominates ((k ‐ 2)‐dominates) H.

Moreover, we show that the subgraph induced by the (t ‐ 3)‐center in any P~t~‐free connected graph is again connected and has diameter at most t ‐ 3.

📜 SIMILAR VOLUMES

Some results on graphs without long indu
Some results on graphs without long induced paths
✍ Dong, Jinquan 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 2 views

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 co

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 👁 2 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

Characterizing path graphs by forbidden
Characterizing path graphs by forbidden induced subgraphs
✍ Benjamin Lévêque; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009

Subdivisions of large complete bipartite
Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs
✍ Thomas Böhme; Bojan Mohar; Riste Škrekovski; Michael Stiebitz 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

## Abstract It is proved that for every positive integers __k__, __r__ and __s__ there exists an integer __n__ = __n__(__k__,__r__,__s__) such that every __k__‐connected graph of order at least __n__ contains either an induced path of length __s__ or a subdivision of the complete bipartite graph __

On the characterization of path graphs
On the characterization of path graphs
✍ Huaien Li; Yixun Lin 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

## Abstract Broersma and Hoede have introduced path graphs. Their characterization of __P__~3~‐graphs contains a flaw. This note presents the correct form of the characterization. © 1993 John Wiley & Sons, Inc.

Long cycles passing through a specified
Long cycles passing through a specified path in a graph
✍ Hirohata, Kazuhide 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 2 views

## For a graph G and an integer an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V (G)|, σ 2 (G) -s} passing through any path of length s. We generalize this result as follows. Let k ≥