Hamiltonian Graphs

Question 1

Definition: Hamiltonian Path

Answer 1

A path that visits each vertex exactly once

Question 2

Definition: Hamiltonian Cycle

Answer 2

A cycle that visits every vertex in the graph exactly once

Question 3

Definition: Hamiltonian Graph

Answer 3

A graph containing a Hamiltonian Cycle

Question 4

Definition: Closure

Answer 4

The closure of a graph is obtained by iteratively joining pairs of nonadjacent vertices whose degree sum at each stage is at least p (number of vertices) until no such pair remains.

Question 5

Hamiltonian Graph: Basic Necessary Condition 1

Answer 5

The graph must be connected

Question 6

Hamiltonian Graph: Basic Necessary Condition 2

Answer 6

The graph must have no cut vertices

Question 7

Hamiltonian Graph: Basic Necessary Condition 3

Answer 7

The graph must have an order equal to or greater than 3

Question 8

Sufficient and Necessary Conditions

Answer 8

There are no known conditions which are sufficient and necessary for a graphs Hamiltonicity

Question 9

Sufficient Conditions

Answer 9

Sufficient conditions, if proven to hold for a graph showing that a graph is Hamiltonian however if proven not to hold for a graph does not disprove a graphs Hamiltonicity

Question 10

Necessary Conditions

Answer 10

Necessary conditions, if proven to hold do not prove that the given graph is Hamiltonian, however, if disproven they are sufficient proof of a graph not being Hamiltonian

Question 11

Vertex deletion result (Necessary condition)

Answer 11

If the number of components left after vertex deletion is less than or equal to the number of vertices deleted then the graph may be Hamiltonian

k(G - S) <= |S| where G is a graph and S a non-empty subset of vertices of G

Question 12

Dirac’s Theorem (Sufficient Condition)

Answer 12

Let G be a connected graph of order p >= 3, then if the minimum degree is >= p/2, the graph is Hamiltonian

Question 13

Sufficient Condition for a Hamiltonian path (Corollary for Dirac’s Theorem)

Answer 13

Let G be a connected graph of order >=3, then if the minimum degree is >= (p-1)/G then the graph contains a Hamiltonian Path.

Question 14

Bondy & Chvatal’s Theorem

Answer 14

Let u and v be two distinct nonadjacent vertices of a graph G of order p such that the sum of the degree of u and v is greater than or equal to p then G is Hamiltonian if and only if G plus the edges uv is Hamiltonian

Question 15

Hamiltonian Closure

Answer 15

A graph is Hamiltonian if and only if its closure is Hamiltonian

Question 16

Ore’s Theorem

Answer 16

If the sum of the degrees of the vertices u and v for all distinct nonadjacent vertices u and v is greater than or equal to the order then G is Hamiltonian.

Question 17

The Travelling Salesmen Problem (TPP)

Answer 17

The objective of the Travelling Salesman problem is to find an optimal Hamiltonian Cycle of a given graph G (Minimum weight)