✦ LIBER ✦

On packing 3-vertex paths in a graph

✍ Scribed by Atsushi Kaneko; Alexander Kelmans; Tsuyoshi Nishimura

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 276 KB
Volume: 36
Category: Article
ISSN: 0364-9024
DOI: 10.1002/1097-0118(200104)36:4<175::aid-jgt1005>3.0.co;2-t

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On paths in planar graphs

✍ Sanders, Daniel P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 2 views

This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two specified vertices x, y and containing any specified edge other than xy.

A note on vertex pancyclic oriented grap

A note on vertex pancyclic oriented graphs

✍ Bang-Jensen, J�rgen; Guo, Yubao 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 1 views

Let D be an oriented graph of order n ≥ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also

Optimal tree 3-spanners in directed path

Optimal tree 3-spanners in directed path graphs

✍ Le, Ho�ng-Oanh; Le, Van Bang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB 👁 1 views

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t 3, the case t ϭ 3 still remains open. In this article, we s

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

Long paths through four vertices in a 2-

Long paths through four vertices in a 2-connected graph

✍ Barovich, Mark V. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 2 views

Let G be a 2-connected graph, let u and v be distinct vertices in V (G), and let X be a set of at most four vertices lying on a common (u

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 ≥