2.1. Hamiltonian Graphs

A vertex u is said to be connected to a vertex v in a graph G if there exists a  path in G.

A graph is connected if every two of its vertices are connected. Otherwise the graph is disconnected.

If G is connected and  is disconnected, where W is a set of vertices, then we say that W separates G, or that W is a vertex-cut .

If in  two vertices s and t belong to different components then W separates s from t.

A graph G is k-vertex-connected  if

  • either
  • or it has at least vertices and no set of vertices separate G.
The maximal value of k for which a connected graph G is k-vertex-connected is the vertex-connectivity of G, denoted by . If G is disconnected, we put .

 

The vertex-connectivity -  - of a graph G is

  • the minimum cardinality of a vertex-cut if G is not complete, and
  • if for some positive integer n.

Two nonadjacent vertices in a graph are said to be independent.

A set S of vertices is independent if every two vertices of S are independent.

The vertex independence number  of a graph G is the maximum cardinality among the independent sets of vertices of G.

If G is a noncomplete graph and t is a nonnegative real number such that  for every vertex-cut S of G and , then G is defined t-tough. (Here  means the number of components of a graph G.)

If G is t-tough and s is a nonnegative real number such that , then G is also s-tough.

The maximum real number t for which a graph G is t-tough is called the toughness of G and denoted by .

Since complete graphs do not contain vertex-cuts, this definition does not apply to such graphs. We define  for every positive integer n.

The independence number is related to the toughnes in the sense that among all the vertex-cuts S of a noncomplete graph G, the maximum value of  is , so for every vertex-cut S of G, we have that .

Theorem 2.1. Let G be a k-connected graph, . Then every k vertices of G lie on a common cycle of G.

Theorem 2.2.  If G is a k-connected graph and  are  distinct vertices of G, then there exist internally disjoint  paths .