Competition Numbers of a Kind of Pseudo-Halin Graphs

• 作者: Guoyan Ye Yonggang Cui Yongqiang Zhao Zhijun Cao
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: COMPETITION GRAPH COMPETITION Number Halin GRAPH Generalized Halin GRAPH Pseudo-Halin GRAPH
• 年，卷（期）: 2017,（1）
• 页码范围: 3-12
• 页数: 10页
• 分类号: O1

摘要

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.