Graphs 003: Graph families

Complete graphs

The complete graph K_n, n\geq1 is the graph with n vertices, such that every pair of vertices is adjacent.

three complete graphs, aligned

Paths

The path P_n, n\geq2 is the graph with V(P_n)=\{1,2,\ldots,n\} and

\displaystyle E(P_n)=\{\{1,2\},\{2,3\},\ldots,\{n-1,n\}\}.

three paths

Cycles

The cycle C_n, n\geq3 is the graph with V(C_n)=\{1,2,\ldots,n\} and

\displaystyle E(C_n)=E(P_n)\cup\{\{1,n\}\}.

three cycles

Complete bipartite graphs

The complete bipartite graph K_{m,n}, m\geq1, n\geq1 is the graph where:

\displaystyle V(K_{m,n})=\{(1,i)\mid i=1,2,\ldots,m\}\cup\{(2,j)\mid i=1,2,\ldots,n\}

and (i,r)\sim (j,s) if and only if i\ne j.

three cycles

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