Graphs 002: Connectedness, diameter and girth

Connectedness

Let G be a graph.

A path P in G is a sequence P=(v_0, v_1,\ldots,v_n) of distinct vertices of G, such that v_i\sim v_{i+1} for i=0,1,\ldots,n-1. In this case, we say that the path P is a v_0v_n-path and that it has length n.

We say that a graph G is connected if for any pair of vertices u,v\in V(G) there is an uv-path.

The sequence (a_n), where a_n is the number of connected graphs on n vertices, is considered in this link.

Distance

The distance d(u,v) between vertices u,v\in V(G) is defined as:

\displaystyle d(u,v)=\min\{\textrm{length of }P\mid P \textrm{ is an }uv\textrm{-path}\},

whenever there is at least an uv-path.

Observe that d(u,v)=0 if and only if u=v, and that d(u,v)=1 if and only if u\sim v.

For example, in the following graph G (the cube):

cube

we have that d(a_0,a_2)=2, since the vertices a_0, a_2 are not adjacent and there is an a_0a_2-path with length 2, namely P=(a_0,a_1,a_2).

Diameter

If G is a connected graph, we define its diameter \textrm{diam}\,G as:

\displaystyle \textrm{diam}\,G=\max\{d(u,v)\mid u,v\in V(G)\}.

The cube graph G has diameter 3, since there are two vertices which are at distance 3 and no two vertices are at greater distance.

Girth

A cycle C in G is a sequence C=(v_1,v_2,\ldots,v_n), n\geq3 of distinct vertices of G, such that v_i\sim v_{i+1} for i=1,\ldots,n-1 and v_1\sim v_n. We say that C has length n, and that it is an n-cycle. If n is an odd number, we say that C is an odd cycle.

If G has at least a cycle, we define the girth g(G) of G, as:

\displaystyle g(G)=\min\{\textrm{length of }C\mid C \textrm{ is a cycle in }G\}.

A cycle of length 3 will be also called a triangle.

The cube graph G has girth G, since it has no triangles and has a 4-cycle.

Exercises

  1. Show that the relation \approx in V(G), defined by u\approx v if and only if there is an uv-path in G, is an equivalence relation.
  2. Determine the graphs that have diameter 0, and the graphs that have diameter 1.
  3. Determine the diameter and the girth of the Petersen graph:

petersen

Advertisements
This entry was posted in Math and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s