dirac's constant

Dirac's theorem

In graph theory, there are two theorems that are commonly referred to as Dirac's theorem, both named after the mathematician Gabriel Andrew Dirac:

  1. Let G be a k-connected graph. Then for any set of k vertices in G, there exists a cycle in G that passes through all k vertices.
  2. Let G be a graph on n ≥ 3 vertices. If each vertex has degree at least n/2 then G is hamiltonian.

Search another word or see dirac's constanton Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature