TITLE:
Competition Numbers of a Kind of Pseudo-Halin Graphs
AUTHORS:
Zhijun Cao, Yonggang Cui, Guoyan Ye, Yongqiang Zhao
KEYWORDS:
Competition Graph, Competition Number, Halin Graph, Generalized Halin Graph, Pseudo-Halin Graph
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.7 No.1,
December
30,
2016
ABSTRACT: For any graphG,Gtogether with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition numberk(G)of a graphGis defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition numberk(G)for a graphGand chara-cterizing a graph by its competition number has been one of important research problems in the study of competition graphs. A 2-connected planar graphGwith minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single facef0yields a tree. It is a Halin graph if the vertices off0all have degree 3 inG. In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.