The Interval Graph Completion Problem on Split Graphs

ZHANG Zhen-kun, YU Min

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

Chinese Quarterly Journal of Mathematics >

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

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2015.02.019

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

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

Cite this article

ZHANG Zhen-kun, YU Min . The Interval Graph Completion Problem on Split Graphs[J]. Chinese Quarterly Journal of Mathematics, 2015 , 30(2) : 308 -316 . DOI: 10.13371/j.cnki.chin.q.j.m.2015.02.019

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article