Study into Fully Orientable Graphs

Assume that $D$ is an acyclic orientation of a graph $G$. An arc is dependent if its reversal creates a directed cycle. Let $d(D)$ be the number of dependent arcs in $D$. Let $d_{min}(G)$ ($d_{max}(G)$) be the minimum (maximum) number of dependent arcs in all acyclic orientations of $G$. A graph $G$ is said to be fully orientable if, for each integer $d$ satisfying $d_{min}(G) leq d leq d_{max}(G)$, there is an acyclic orientation $D$ of $G$ with $d(D)=d$.

We begin this thesis by introducing basic definitions, notation, and known results about fully orientability of graphs. In order to characterize $d_{min}(G)$, we then introduce several parameters about triangles and covering graphs. A graph is called a covering graph if it is the underlying graph of the Hasse diagram of a partially ordered set.

We generalize results in Collins and Tysdal [4] about $d_{min}(M_m(G))$ of generalized Mycielski graphs $M_m(G)$. A method to construct generalized Mycielski graphs $M_m(G)$ with $d_{min}(M_m(G))=1$ is also given.

We discuss the following graph operations that preserve fully orientability: the union of two graphs whose intersection is an edge, addition of a path of length at least 2 and addition of an edge between two vertices of degree 2 with a unique common neighbor. We introduce a graph operation called adding a skirt in the following manner. We add a new cycle to a given graph. For each vertex in the cycle, add at most one edge incident to a vertex in the given graph. Except one case, we can prove that the new graph operation preserving fully orientability.

We generalize the color-first tree algorithm in Fisher, Fraughnaugh, Langley and West [5] to obtain the following stronger result. For each spanning tree $T$ obtained by depth-first search, there exists an integer $k_T$ such that, for each $d$ satisfying $k_T leq d leq d_{max}(G)$, there is an acyclic orientation $D$ of $G$ with $d(D)=d$.

A graph is called 2-degenerate if every subgraph has a vertex of degree at most two. A Halin graph is a plane graph obtained by drawing a tree without vertex of degree 2 in the plane, then drawing a cycle through all leaves in the plane. We prove that $2$-degenerate graphs, Halin graphs, graphs with maximum degree at most 3 and graphs with $d_{min}(G) leq 1$ are fully orientable. Furthermore, we characterize $d_{min}(G)$ of these graphs.

In the final chapter, we give brief conclusions and pose some open problems for further study.