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

张振坤, 余敏

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

数学季刊 >

2015 , Vol. 30 >Issue 2: 308 - 316

DOI: https://doi.org/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

ZHANG Zhen-kun(1970-), male, native of Zhumadian, Henan, an associate professor of Huanghuai University, Ph.D., engages in graph theory and combinatorial optimization.

收稿日期: 2014-05-08

网络出版日期: 2020-11-24

基金资助

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

Expand

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

ZHANG Zhen-kun(1970-), male, native of Zhumadian, Henan, an associate professor of Huanghuai University, Ph.D., engages in graph theory and combinatorial optimization.

Received date: 2014-05-08

Online published: 2020-11-24

Supported by

Supported by the National Natural Science Foundation of China(11101383)； Supported by the Natural Science Foundation of Henan Province(112300410047)；

Fold

摘要

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

本文引用格式

张振坤, 余敏 . 分裂图的区间图完全化问题[J]. 数学季刊, 2015 , 30(2) : 308 -316 . DOI: 10.13371/j.cnki.chin.q.j.m.2015.02.019

Abstract

Key words： interval graph; graph labeling; graph completion; split graph

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract