In this thesis, we focus on the study of dependent arcs of
acyclic orientations of graphs. Given an acyclic orientation D of G, Edelman cite{West} defined an arc to be {em dependent} if its reversal creates a cycle in D; otherwise, it is independent. Let d(D) and i(D) be the numbers of dependent arcs and independent arcs in D, respectively. And, let d_{max}(G)(d_{min}(G)) and i_{max}(G) (i_{min}(G)) be the maximum (minimum) numbers of dependent arcs and independent
arcs over all acyclic orientations of G, respectively. Edelman
cite{Fisher} showed that if G is connected, then
d_{max}(G)=||G||-|G|+1. A graph G is said to satisfy the
{em interpolation property} (or G is fully orientable) if $G$
has an acyclic orientation with exactly k dependent arcs for
every k with d_{min}(G) leq k leq d_{max}(G). West
established the interpolation property for complete bipartite graphs cite{West}. We obtain the minimum numbers of dependent arcs of the outerplane graphs and show that the outerplane graphs satisfy the interpolation property. Let N(G) be the set { i(D)| D is an acyclic orientation of G }. N(G) is called the independent-arc spectra of G. For complete k-partite graphs G, we obtain i_{max}(G) and discuss the independent-arc spectra for some classes. On the other hand, we consider the cover problem. A cover graph is the underlying graph of the Hasse diagram of a finite partially ordered set. The cover problem is that whether a given graph is a cover graph. It is easy to see that a graph G is a cover graph if and only if d_{min}(G)=0. We show that the generalized Mycielski graphs M_m(C_{2t+1}) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m geq 1, t geq 1, k geq 3 and n geq 2k+2.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0116106-154154 |
| Date | 16 January 2006 |
| Creators | Lin, Chen-ying |
| Contributors | Li-Da Tong, B. L. Chen, Ko-Wei Lih, Gerard J. Chang, Yeong-Nan Yeh, Xuding Zhu, D.J. Guan |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0116106-154154 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.1301 seconds