• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Chen, Xuegang (Chen, Xuegang.) | Huang, Jing (Huang, Jing.)

收录:

EI Scopus SCIE

摘要:

As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition is an NP-complete problem for general graphs, and is polynomial time solvable for several classes of graphs. In this paper, we investigate graphs that admit a unique such partition and call them uniquely monopolar-partitionable graphs. By employing a tree trimming technique, we obtain a characterization of uniquely monopolar-partitionable block graphs. Our characterization implies a polynomial time algorithm for determining whether a block graph is uniquely monopolar-partitionable.

关键词:

block graph characterization Monopolar graph monopolar partition polynomial time algorithm uniquely monopolar-partitionable grap

作者机构:

  • [ 1 ] [Chen, Xuegang]North China Elect Power Univ, Dept Math, Beijing 102206, Peoples R China
  • [ 2 ] [Chen, Xuegang]Beijing Univ Technol, Dept Appl Math, Beijing 100124, Peoples R China
  • [ 3 ] [Huang, Jing]Univ Victoria, Dept Math & Stat, Victoria, BC V8W 2Y2, Canada

通讯作者信息:

  • [Chen, Xuegang]North China Elect Power Univ, Dept Math, Beijing 102206, Peoples R China

电子邮件地址:

查看成果更多字段

相关关键词:

相关文章:

来源 :

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

ISSN: 1462-7264

年份: 2014

期: 2

卷: 16

页码: 21-34

0 . 7 0 0

JCR@2022

ESI学科: MATHEMATICS;

ESI高被引阀值:56

JCR分区:4

中科院分区:4

被引次数:

WoS核心集被引频次: 0

SCOPUS被引频次:

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 2

在线人数/总访问数:315/2905312
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司