House Graphs and House X Graphs – Eulerian and Hamiltonian Paths

As stated before, House and House X Graphs aren’t widely described on the Internet, following from my previous post on the properties of House Graphs, I wanted to show that House (X) Graphs aren’t Eulerian (do not have a Eulerian Path) and aren’t Hamiltonian.

An Eulerian Graph is a graph whereby all the vertices within the graph have an even degree. This definition is obtained from Euler’s Theorem which was published in 1736.

Theorem (Euler 1736): A connected graph  is Eulerian if and only if every vertex has an even degree.

Using this theorem, it is easy to prove that House and House X Graphs do not have an Eulerian Path. An Eulerian Path is a path whereby each edge is visited exactly once.

Using GraphTea, I’ve constructed a House Graph and a House X Graph. I’ve labeled each vertex within the graph with it’s corresponding degree. You can easily see that both graphs do not possess the law of Euler’s Theorem, and therefore these graphs are not Eulerian.

House X Graph

 A Hamiltonian Graph is quite similar to an Eulerian Graph, however, the conditions are different. A Hamiltonian Graph is where there exists a cycle which can visit each vertex within the graph exactly once, with the exclusion of the start and end of the cycle.

I attempt to show if the House Graphs are Hamiltonian, or at least, if they contain a Hamiltonian path.

Using Ore’s Theorem (1960), we can investigate if the House X Graph and the House Graph contain a Hamiltonian Cycle.

Theorem (Ore 1960): Let G be a finite and simple graph on n \geq 3 vertices. If deg v + deg u  \geq n for every pair of non-adjacent v and u vertices of G, then G is Hamiltonian.

I’ve created a line between each non-adjacent pair of vertices within both graphs. We can see that the House Graph is non-Hamiltonian and the House X graph is Hamiltonian.

house-x-graphReferences:

Ore’s Theorem

Hamiltonian Graph

Graduate Texts in Mathematics: Graph Theory (Diestel)

 

Advertisements

About 0x14c

I'm a Computer Science student and writer. My primary interests are Graph Theory, Number Theory, Programming Language Theory, Logic and Windows Debugging.
This entry was posted in Computer Science, Graph Theory, Mathematics, Theoretical Computer Science. Bookmark the permalink.

One Response to House Graphs and House X Graphs – Eulerian and Hamiltonian Paths

  1. My spoսse аnnd I stumbled over hеre from a different website and thought I might as well check
    things out. I like what I seе so noѡ i’m folloԝing you.
    Look fօrward to exploring your web page for а second time.

    Like

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