Competition Numbers Of Generalized Halin Graphs

The notion of the competition graph was introduced by Cohen in connection with a problem in ecology. Let D=(V, A) be a digraph in which V is the vertex set and A the set of directed arcs. The competition graph C(D) of D is the undirected graph G with the same vertex set as D and with an edge uv ∈ E(G) if and only if there exists some vertex x such that (u,x),(v,x)∈A(D). We say that a graph G is a competition graph if there exists a digraph D such that C(D)=G. Roberts observed that adding sufficiently many isolated vertices to an arbitrary graph G allows it to be the competition graph of some acyclic digraph. The minimum number of such isolated vertices is called the competition number of the graph G and is denoted by k(G). It is difficult to compute the competition number of a graph in general as Opsut has shown that the computation of the competition number of a graph is an NP-hard problem. Till now the competition numbers are known just for some special graph classes. If G is a graph, θe(G) is the smallest number of cliques in an edge clique cover of G, a collection of cliques that covers all edges of G.A Halin graph G= T∪C is a planar graph that consists of a planar embedding of a tree T that has no vertices of degree 2, and a cycle C connecting the leaves of the tree such that C is the boundary of the exterior face. A vertex v ∈ V(C) is a simple leaf of T if NT(v)∩NT(x)=(?) for each vertex x∈Nc(v), denote all simple leaves of T by V1. An (n)-Halin graph is a planar simple graph having the property that its edge set E can be partitioned as E=E(T)∪E(C1)∪E(C2)∪…∪E(Cn) where T is a tree with no vertices of degree 2 and C1,C2,…,Cn are pairwise disjoint cycles such that V(C1)∪V(C2)∪…∪V(Cn) is the set of all leaves of T. Thus, (1)-Halin graphs are the usual Halin graphs. A 2-connected planar graph G with minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single face f0 yields a tree. It is a Halin graph if the vertices of f0 all have degree 3 in G. The irregular vertex set IR(f0) of f0 includes the vertices with degree more than 3.If we allow the trees T in Halin graphs and in (n)-Halin graphs having the vertices of degree 2, then we have the notions of the generalized Halin graph and the generalized (n)-Halin graph. In this thesis, we study the competition numbers of generalized Halin graphs, generalized (n)-Halin graphs and pseudo-Halin graphs, determine the exact ’alues of the competition numbers of the generalized Halin graphs and the generalized (n)-Halin graphs, and provide the upper bounds of the competition numbers of a kind of pseudo-Halin graphs. The main results are as follows:1. Let G be a generalized Halin graph or a generalized (n)-Halin graph. Then we have2. Let G be a pseudo-Halin graph with IR(fo)={x}. Suppose that the neighbors of x on the boundary of f0 are u and v, and let NT(u)={u’} and NT (v)={v’}. Then we have...