The total interval number of a tree and the Hamiltonian completion number of its line graph

被引：16

作者：

Raychaudhuri, A

机构：

[1] Department of Mathematics, College of Staten Island (CUNY), Island, NY 10314, 2800, Victory Blvd, Staten

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 56卷 / 06期

关键词：

combinational problems; discrete mathematics; graph theory; interval graph; total interval number; Hamiltonian path; Hamiltonian completion number; line graph; tree;

D O I：

10.1016/0020-0190(95)00163-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we investigate the problem of computing two parameters of a graph: the Total Interval Number TIN(G), and the Hamiltonian Completion Number HCN(G). We show that in case of a triangle-free graph these two parameters (TIN(G) and HCN(L(G)), where L(G) is the line graph of G) are related by a simple formula. We use this relationship to find a polynomial algorithm which determines TIN(G), for a tree G. Then we describe a construction which gives an interval representation of a tree G with TIN(G) number of intervals.

引用

页码：299 / 306

页数：8

共 8 条

[1]

AIGNER M, 1989, J COMB THEORY B, V46, P7

[2]

BOESCH FT, 1974, LECT NOTES MATH, V406, P202

[3]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[4]

Goodman S., 1974, GRAPH COMBINATOR, P262

[5] EXTREMAL VALUES OF THE INTERVAL NUMBER OF A GRAPH [J].

GRIGGS, JR ;

WEST, DB .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (01) :1-7

[6]

HARARY F, 1979, J GRAPH THEOR, V3, P205

[7]

Kundu S., 1976, Information Processing Letters, V5, P55, DOI 10.1016/0020-0190(76)90080-6

[8]

ROBERTS FS, 1979, DISCRETE MATH MODELS

← 1 →