...
首页> 外文期刊>Discrete Applied Mathematics >Total domination in inflated graphs
【24h】

Total domination in inflated graphs

机译:膨胀图中的总支配

获取原文
获取原文并翻译 | 示例
           

摘要

The inflation ~(GI) of a graph G is obtained from G by replacing every vertex x of degree d(x) by a clique X=Kd(_(x)) and each edge xy by an edge between two vertices of the corresponding cliques X and Y of ~(GI) in such a way that the edges of ~(GI) which come from the edges of G form a matching of ~(GI). A set S of vertices in a graph G is a total dominating set, abbreviated TDS, of G if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a TDS of G is the total domination number ~(γt)(G) of G. In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if G is a connected graph of order n<2, then ~(γt)(~(GI))<2n3, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of G to be at least 2, then we show that ~(γt)(~(GI))
机译:图G的膨胀〜(GI)是从G中获得的,方法是将等级d(x)的每个顶点x替换为集团X = Kd(_(x())),将每个边缘xy替换为对应顶点两个顶点之间的边将〜(GI)的X和Y排列成这样,即来自G边缘的〜(GI)边缘形成〜(GI)的匹配。如果G的每个顶点都与S中的顶点相邻,则图G中的顶点集S是G的总支配集,简称TDS。G的TDS的最小基数是总支配数〜(γt) (G)的G。在本文中,我们研究了膨胀图中的总支配地位。我们提供了膨胀图的总控制数的上限(按顺序和匹配数)。我们证明,如果G是n <2阶的连通图,则〜(γt)(〜(GI))<2n3,并且我们表征了在该范围内实现相等的图。此外,如果我们将G的最小度数限制为至少2,那么我们证明〜(γt)(〜(GI))

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号