• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The competition number of a graph with exactly h holes, all of which are independent
【24h】

The competition number of a graph with exactly h holes, all of which are independent

机译：具有正好h个孔的图的竞争编号，所有这些孔都是独立的

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Given an acyclic digraph D, the competition graph C(D) of D is the graph with the same vertex set as D where two distinct vertices x and y are adjacent in C(D) if and only if there is a vertex v in D such that (x, v) and (y, v) are arcs of D. The competition number kappa(G) of a graph G is the least number of isolated vertices that must be added to G to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly h holes, all of which are independent, is at most h + 1. This generalizes the result for h = 0 given by Roberts, and the result for h = 1 given by Cho and Kim.
机译：给定一个无圈有向图D，D的竞争图C（D）是具有与D相同的顶点集的图，其中且仅当D中存在一个顶点v时，C（D）中两个不同的顶点x和y相邻。这样，（x，v）和（y，v）是D的弧。图G的竞争数kappa（G）是必须添加到G才能形成竞争图的最小隔离顶点数。本文的目的是证明具有正好h个孔（均独立）的图的竞争数最多为h +1。这可以概括罗伯茨给出的h = 0的结果和h的结果= Cho和Kim给出的1。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号