Intersection graphs, fraternally orientable graphs and hamiltonian cycles.

Abstract

Consider a graph G(V, E), where V and E denote the vertex and edge sets of G(V, E), respectively. An orientation $\vec G$ of G(V, E) is the result of giving an orientation to the edges of G. A directed graph is fraternally oriented if for every three vertices u, v, w, the existence of the edges $u\to w$ and $v\to w$ implies that $u\to v$ or $v\to u$. A graph G is fraternally orientable if there exists an orientation $\vec G$ that is fraternally oriented. In this thesis we study some properties of fraternally orientable graphs, and we describe an algorithm to find a hamiltonian cycle in strongly connected fraternally oriented graphs $\vec G$.