• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Dependent Arcs of Orientations of Graphs

Lin, Chen-ying 16 January 2006 (has links)
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.

Page generated in 0.0931 seconds