Competition Numbers of a Kind of Pseudo-Halin Graphs ()
ABSTRACT
For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and 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 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. In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.
Share and Cite:
Cao, Z. , Cui, Y. , Ye, G. and Zhao, Y. (2017) Competition Numbers of a Kind of Pseudo-Halin Graphs.
Open Journal of Discrete Mathematics,
7, 3-12. doi:
10.4236/ojdm.2017.71002.
Cited by
No relevant information.