Convexity in graphs has been widely discussed in graph theory and G.
Chartrand et al. introduced the convexity number of oriented graphs
in 2002. In this thesis, we follow the notions addressed by them and
develop an extension in some related topics of convexity in directed
graphs.
Let D be a connected oriented graph. A set S subseteq V(D)
is convex in D if, for every pair of vertices x, yin S,
the vertex set of every x-y geodesic (x-y shortest directed
path) and y-x geodesic in D is contained in S. The convexity number con(D) of a nontrivial oriented graph D is
the maximum cardinality of a proper convex set of D. We show that
for every possible triple n, m, k of integers except for k=4,
there exists a strongly connected digraph D of order n, size
m, and con(D)=k.
Let G be a graph. We define
the convexity spectrum S_{C}(G)={con(D): D is an
orientation of G} and the strong convexity spectrum
S_{SC}(G)={con(D): D is a strongly connected orientation of
G}. Then S_{SC}(G) ⊆ S_{C}(G). We show that for any
n ¡Ú 4, 1 ≤ a ≤ n-2 and a n ¡Ú 2, there exists a
2-connected graph G with n vertices such that
S_C(G)=S_{SC}(G)={a,n-1}, and there is no connected graph G of
order n ≥ 3 with S_{SC}(G)={n-1}. We also characterizes the
convexity spectrum and the strong convexity spectrum of complete
graphs, complete bipartite graphs, and wheel graphs. Those convexity
spectra are of different kinds.
Let the difference of convexity spectra D_{CS}(G)=S_{C}(G)-
S_{SC}(G) and the difference number of convexity spectra
dcs(G) be the cardinality of D_{CS}(G) for a graph G. We show
that 0 ≤ dcs(G) ≤ ⌊|V(G)|/2⌋,
dcs(K_{r,s})=⌊(r+s)/2⌋-2 for 4 ≤ r ≤ s,
and dcs(W_{1,n-1})= 0 for n ≥ 5.
The convexity spectrum ratio of a sequence of simple graphs
G_n of order n is r_C(G_n)= liminflimits_{n to infty}
frac{|S_{C}(G_n)|}{n-1}. We show that for every even integer t,
there exists a sequence of graphs G_n such that r_C(G_n)=1/t and
a formula for r_C(G) in subdivisions of G.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0127111-064740 |
| Date | 27 January 2011 |
| Creators | Yen, Pei-Lan |
| Contributors | Dah-Jyh Guan, Sen-Peng Eu, Hong-Gwa Yeh, Tsai-Lien Wong, Gerard Jennhwa Chang, Li-Da Tong, Xuding Zhu, Ko-Wei Lih |
| 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-0127111-064740 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0014 seconds