可全定向圖的研究

Abstract

假設D是圖形G的一個無圈定向，若一個邊倒轉後會產生一有向圈，則稱此邊為一個相依邊。令d(D)代表D的相依邊總數。令dmin(G) (dmax(G))代表G的所有無圈定向裡所能給出最少(最多)的相依邊數。如果圖G存在無圈定向使得其相依邊數可為dmin(G)至dmax(G)中的任意整數，則稱圖G為可全定向的。 在這篇論文的開頭，我們會介紹基本定義、符號及一些可全定向圖的基本性質。為了刻劃dmin(G)，我們會介紹幾個與三角形、覆蓋圖有關的圖參數。如果圖G是一個偏序集合的Hasse圖的底圖，則稱圖G為一個覆蓋圖。 我們會推廣在Collins與Tysdal [4]中關於generalized Mycielski圖之dmin(Mm(G))的結果。我們亦會給出一個建造dmin(Mm(G))為1的generalized Mycielski圖之方法。 我們會討論下列幾種能保持可全定向性質的圖運算：將兩個交集為一個邊的圖取聯集、加入一個長度至少為2的路徑及將兩個度數為2且僅有一個共用鄰點的不相鄰點相連。我們會介紹一個新的圖運算，稱之為加入一個裙。該運算如下所述。新加一個圈到所給定的圖；對圈上的每個點，由該點連最多一條邊至原給定圖。我們會證明除了一個特殊的未知情況之外，這個新的圖運算能保持圖的可全定向性質。 我們會推廣在Fisher, Fraughnaugh, Langley及West [5]中所給出的演算法並得出更強的結果。對每一個由縱向優先搜尋所得出的生成樹T，會存在一個值kT，圖G存在無圈定向使得其相依邊數可為kT至dmax(G)中的任意整數。 如果圖Ｇ的每個子圖都有一度數小於或等於2的點，則稱G為2-退化。Halin圖是將一個沒有度數為2的點之樹畫在一平面上，再加上一個通過該樹所有葉的圈所得出的平面圖。我們會證明所有的2-退化圖、Halin圖、最大度小於或等於3的圖及dmin(G)小於或等於1的圖皆為可全定向的。除此之外，我們亦會刻劃出上述圖類的dmin(G)。 在最後一章，我們會列出簡略的結果整理並給出數個可供後續研究的問題。

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.