分裂图的区间图完全化问题

doi:10.13371/j.cnki.chin.q.j.m.2015.02.019

数学季刊 ›› 2015, Vol. 30 ›› Issue (2): 308-316.doi: 10.13371/j.cnki.chin.q.j.m.2015.02.019

• • 上一篇

分裂图的区间图完全化问题

1. Department of Mathematics, Huanghuai University 2. Software College,Zhengzhou Raiway Vocational and Technical College

收稿日期:2014-05-08 出版日期:2015-06-30 发布日期:2020-11-24
作者简介:ZHANG Zhen-kun(1970-), male, native of Zhumadian, Henan, an associate professor of Huanghuai University, Ph.D., engages in graph theory and combinatorial optimization.
基金资助:
Supported by the National Natural Science Foundation of China(11101383)； Supported by the Natural Science Foundation of Henan Province(112300410047)；

The Interval Graph Completion Problem on Split Graphs

1. Department of Mathematics, Huanghuai University 2. Software College,Zhengzhou Raiway Vocational and Technical College

Received:2014-05-08 Online:2015-06-30 Published:2020-11-24
About author:ZHANG Zhen-kun(1970-), male, native of Zhumadian, Henan, an associate professor of Huanghuai University, Ph.D., engages in graph theory and combinatorial optimization.
Supported by:
Supported by the National Natural Science Foundation of China(11101383)； Supported by the Natural Science Foundation of Henan Province(112300410047)；

摘要/Abstract

摘要： The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.

关键词: interval graph, graph labeling, graph completion, split graph

Abstract: The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.

Key words: interval graph, graph labeling, graph completion, split graph

中图分类号:

O157.5

张振坤, 余敏. 分裂图的区间图完全化问题[J]. 数学季刊, 2015, 30(2): 308-316.

ZHANG Zhen-kun, YU Min. The Interval Graph Completion Problem on Split Graphs[J]. Chinese Quarterly Journal of Mathematics, 2015, 30(2): 308-316.

[1]	张振坤, 叶稀琼. K 割宽临界树的构造[J]. 数学季刊, 2022, 37(4): 366-379.
[2]	张振坤, 高风昕. 补树的扩充侧廓[J]. 数学季刊, 2010, 25(4): 515-521.
[3]	张振坤, 侯亚林. 完全多部图的区间图完全化问题[J]. 数学季刊, 2009, 24(2): 290-297.
[4]	郝建修, 李湘露. L_∞模下的二维带宽问题[J]. 数学季刊, 2004, 19(4): 362-367.

分裂图的区间图完全化问题

The Interval Graph Completion Problem on Split Graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价