PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (23)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Low Entry average rating: No information on entry rating
hypohamiltonian (Definition)

A graph $ G$ is hypohamiltonian if $ G$ is not Hamiltonian, but $ G - v$ is Hamiltonian for each $ v \in V$ ($ V$ the vertex set of $ G$). The smallest hypohamiltonian graph is the Petersen graph, which has ten vertices.



"hypohamiltonian" is owned by digitalis.
(view preamble | get metadata)

View style:

See Also: Hamiltonian graph, Petersen graph

Keywords:  hamiltonian
Log in to rate this entry.
(view current ratings)

Cross-references: vertices, Petersen graph, vertex, Hamiltonian, graph
There is 1 reference to this entry.

This is version 1 of hypohamiltonian, born on 2002-02-21.
Object id is 2432, canonical name is Hypohamiltonian.
Accessed 1970 times total.

Classification:
AMS MSC: 05C45 (Combinatorics :: Graph theory :: Eulerian and Hamiltonian graphs)
 05C65 (Combinatorics :: Graph theory :: Hypergraphs)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy
Smallest example? by azi on 2008-07-05 10:27:57
It is stated in the text that the petersen graph is the smallest example of a hypohamiltonian graph. What about the complete graph on two vertices?
[ reply | up ]
Interact
post | correct | update request | add derivation | add example | add (any)