how many orientations does a simple graph g have?

**Louise** · November 28th 2009, 07:06 AM

hi

I'm stuck on the followinq question

How many orientations does a simple graph g have?

for one vertex there is one, just the isolated vertex

for two vertices there are 3, i think...two isolated vertices u and v, a digraph with arc uv and a digraph with arc vu.

i'm not sure where to go from here

thanks for your help

**qmech** · November 28th 2009, 08:02 AM

Your description of your calculation already lets you count how many directed graphs there are. Between each pair of points, there seem to be 3 possibilities - no edge, an edge directed one way, an edge directed the other. You can count how many pairs of points there are - n choose 2 - points. So you've counted
$ 3 ^ { \binom{n}{2} } $
graphs.

However there is another definition of simple graph that doesn't allow for directed vertices. If so, your calculation overcounts because there's only 2 possibilities - no edge, or yes, there's an edge.

**Louise** · November 28th 2009, 08:19 AM

hi, i just want to check i understand

i'm working from the definition of a simple graph which states that g contains no loops or multiple edges, so i don't think i need to worry about overcounting

i understand now that i need to divide into the three cases for each pair of vertices

using your formula i get

n number of orientations
1 1
2 3
3 9
4 24
....

are these values correct?

thanks again for your help

**qmech** · November 28th 2009, 12:56 PM

I'm still not sure if you're working with simple graphs or simple directed graphs. The definition I'm getting from the web for simple graph is: "unweighted, undirected" graph. Please note the "undirected"!

The formula is not being interpreted correctly. The
$ \binom {n}{m} = \frac {n!}{m!(n-m)!} $

so the first few values are:
$ \binom {2}{2} = 1, \implies 3^{\binom{2}{2}} = 3 $
$ \binom {3}{2} = 3, \implies 3^{\binom{3}{2}} = 27 $
$ \binom {4}{2} = 6, \implies 3^{\binom{4}{2}} = 729 $

**Louise** · November 29th 2009, 12:28 AM

I need the graphs to be directed since i'm looking for the number of orientations.

i think that if i have 3 vertices and and a directed edge (arc) between 1 pair i count this once not 6 times for alternate direction and the choice of the two other pairs.

this means that for n=1,2,3,4,5,.... i get 1,2,7,42,582

(this sequence is from wolfram mathworld)

im trying to find the formula for this sequence, does anyone know it?

thank you

Thread: how many orientations does a simple graph g have?

LinkBack

Thread Tools

Display

how many orientations does a simple graph g have?

Check definition of "simple" graph

Definition of simple graph

Similar Math Help Forum Discussions

k-regular simple graph

simple graph

A simple graph

Very simple graph question

Vertices of a simple graph

Search Tags