...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On minimal forbidden subgraph characterizations of balanced graphs
【24h】

On minimal forbidden subgraph characterizations of balanced graphs

机译：关于平衡图的最小禁止子图刻画

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

摘要

A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.
机译：如果图的集团矩阵不包含奇无弦循环的边线顶点入射矩阵作为子矩阵，则该图是平衡的。尽管已知平衡图的禁止诱导子图表征，但是最小限度禁止诱导子图没有这种表征。在这项工作中，我们提供了平衡图的最小禁止诱导子图特征，这些图仅限于属于以下图类之一的图：二部图的补图，多图的折线图和多图的折线图。这些特征导致针对相同三个图类中的平衡图的线性时间识别算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号