Halin graph

Halin graph

In graph theory, a mathematical discipline, a Halin graph is a planar graph constructed from a plane embedding of a tree with at least 4 vertices and with no vertices of degree 2, by connecting all end vertices (i.e., the ones of degree 1) with a cycle in the natural cyclic order defined by the embedding of the tree.

Properties

  • It is an edge-minimal planar 3-connected graph.
  • It has a unique planar embedding (up to the choice of the outer space; i.e., a unique embedding onto a 2-sphere).
  • It is a Hamiltonian graph, moreover, it remains Hamiltonian after deletion of any vertex.

References

Search another word or see Halin graphon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature