摘要
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.
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.
