✦ LIBER ✦

On the characterization of path graphs

✍ Scribed by Huaien Li; Yixun Lin

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 191 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170403

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

📜 SIMILAR VOLUMES

On the hamiltonian path graph of a graph

✍ George R. T. Hendry 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap

On Path-amenable Graphs

✍ Gabriel Dirac; Ove Steen Nielsen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB

A characterization of graphs without lon

A characterization of graphs without long induced paths

✍ Gábor Bacsó; Zsolt Tuza 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB 👁 1 views

## 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

Characterizing directed path graphs by f

Characterizing directed path graphs by forbidden asteroids

✍ Kathie Cameron; Chính T. Hoàng; Benjamin Lévêque 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal grap

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

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.