All, I have: typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, place, link> mapType; place* newPlace = new place("here-and-there"); mapType::vertex_descriptor newPlaceDesc = add_vertex(*newPlace, theMap); where the destructor of place is: place::~place() { // Just to make sure... std::cout << "Deleting place " << name << std::endl; // ... } When I run that, I do get: Deleting place here-and-there just after adding the vertex. In other words, a property is being deleted, probably a copy of the one I gave. I even tried (to make it explicitly like the documentation says): mapType::vertex_descriptor newPlaceDesc = add_vertex(static_cast<const place&>(*newPlace), theMap); and the same happens. Is that suppose to happen? Cheers, Fred