Premium
Closure for the property of having a hamiltonian prism
Author(s) -
Král Daniel,
Stacho Ladislav
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20203
Subject(s) - combinatorics , mathematics , quartic graph , graph , hamiltonian (control theory) , prism , graph power , discrete mathematics , line graph , physics , optics , mathematical optimization
We prove that a graph G of order n has a hamiltonian prism if and only if the graph Cl 4 n /3–4/3 ( G ) has a hamiltonian prism where Cl 4 n /3–4/3 ( G ) is the graph obtained from G by sequential adding edges between non‐adjacent vertices whose degree sum is at least 4 n /3–4/3. We show that this cannot be improved to less than 4 n /3–5. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 209–220, 2007