Study into Fully Orientable Graphs

假設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.Acknowledgements ii Abstract (in Chinese) iii Abstract (in English) v Contents vii List of Figures x 1 Introduction 1 1.1 Basic Concepts 1 1.2 Orientations and Colorings 4 1.3 Dependent Arcs 7 1.4 Fully Orientability 12 2 Parameters about Triangles, Dependent Arcs and Covering Subgraphs 17 2.1 Covering Graphs 17 2.2 Parameters and Inequalities 21 2.3 Bounds of Parameters 25 2.4 Complete Graphs and Cycles 28 2.5 Results about $chi(G)<g(G)$ 28 2.6 $pi_E(G)=1$ if and only if $d_{min}(G)=1$ 30 2.7 Removing an Edge 34 2.8 Removing a Vertex 36 2.9 $K_4$-free Graphs and 3-colorable Graphs 38 2.10 $K_5$-minor Free Graphs and Planar Graphs 39 3 Generalized Mycielski Graphs 42 3.1 Results about $d_{min}(M_m(G))$ and $pi_{E}(M_m(G))$ 43 3.2 $M_m(G)$ whose $d_{min}$ is 1 48 3.3 Upper Bound of $pi_E(M_m(G))$ 51 4 Graph Operations Preserving Fully Orientability 52 4.1 Graph Union 52 4.2 Path Addition 55 4.3 Adding an Edge between Two Vertices of Degree Two 61 5 2-degenerate Graphs 63 5.1 Characterization of $k$-degenerate Graphs 63 5.2 Fully Orientability of 2-degenerate Graphs 64 5.3 $d_{min}(G)$ of 2-degenerate Graphs 65 5.4 Outerplanar Graphs 68 6 Applications of Adding a Skirt 70 6.1 Operation of Adding a Skirt 70 6.2 Wheel 72 6.3 Dependent Arcs and Adding a Skirt 73 6.4 Halin Graphs and Their Subdivisions 83 6.5 Graphs with Maximum Degree at Most 3 85 7 Applications of Color-First Trees 89 7.1 Color-First Trees 89 7.2 Relations among Dependent Arcs, Depth-First Searchs and Color-First Trees 91 7.3 Graphs with $d_{min}(G) leq 1$ 93 7.4 General Graphs 95 8 Conclusions and Further Research 100 8.1 Results Obtained 100 8.2 Open Problems 103 Bibliography 105 Index 10