✦ LIBER ✦

On the hamiltonian path graph of a graph

✍ Scribed by George R. T. Hendry

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 491 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110312

No coin nor oath required. For personal study only.

✦ Synopsis

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 graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that xd C H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with a t least five vertices is at least IV(f)I + t(t b 0). then H ( f ) contains a complete subgraph of order t + 4.

📜 SIMILAR VOLUMES

Hamiltonian path graphs

✍ Gary Chartrand; S. F. Kapoor; E. A. Nordhaus 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 389 KB

## Abstract The Hamiltonian path graph __H(G)__ of a graph __G__ is that graph having the same vertex set as __G__ and in which two vertices __u__ and __v__ are adjacent if and only if __G__ contains a Hamiltonian __u‐v__ path. A characterization of Hamiltonian graphs isomorphic to their Hamiltonia

Line graphs of bipartite graphs with Ham

Line graphs of bipartite graphs with Hamiltonian paths

✍ Francis K. Bell 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

It is shown that, if t is an integer !3 and not equal to 7 or 8, then there is a unique maximal graph having the path P t as a star complement for the eigenvalue À2: The maximal graph is the line graph of K m,m if t ¼ 2mÀ1, and of K m,m þ1 if t ¼ 2m. This result yields a characterization of L(G ) wh

Trees and unicyclic graphs with hamilton

Trees and unicyclic graphs with hamiltonian path graphs

✍ Xingxing Yu 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract We prove two conjectures of Broersma and Hoede about path graphs of trees and unicyclic graphs.

On minimum degree in Hamiltonian path gr

On minimum degree in Hamiltonian path graphs

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

Metamaterial inclusions based on grid-gr

Metamaterial inclusions based on grid-graph Hamiltonian paths

✍ Vincenzo Pierro; John McVay; Vincenzo Galdi; Ahmad Hoorfar; Nader Engheta; Innoc 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 287 KB

## Abstract This article deals with a study of novel classes of metamaterial inclusions based on space‐filling curves. The graph–theoretic Hamiltonian‐path (HP) concept is exploited to construct a fairly broad class of space‐filling curve geometries that include as special cases the well‐known Hilb

Powers of Hamiltonian paths in interval

Powers of Hamiltonian paths in interval graphs

✍ Isaak, Garth 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB 👁 3 views

We give a simple proof that the obvious necessary conditions for a graph to contain the k th power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a greedy algorithm tests for the existence of Hamiltonian path powers in interval graphs. We wi