LexBFS-orderings and powers of chordal graphs

被引：29

作者：

Brandstadt, A

Dragan, FF

Nicolai, F

机构：

[1] UNIV ROSTOCK,FACHBEREICH INFORMAT,LEHRSTUHL THEORET INFORMAT,D-18051 ROSTOCK,GERMANY

[2] MOLDOVA STATE UNIV,DEPT MATH & CYBERNET,KISHINEV 277009,MOLDOVA

[3] GERHARD MERCATOR UNIV GH DUISBURG,FB MATH,FG INFORMAT,D-47048 DUISBURG,GERMANY

来源：

DISCRETE MATHEMATICS | 1997年 / 171卷 / 1-3期

关键词：

D O I：

10.1016/S0012-365X(96)00070-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For an undirected graph G the kth power G(k) of G is the graph with the same vertex set as G where two vertices are adjacent iff their distance is at most k in G. In this paper we prove that any LexBFS-ordering of a chordal graph is a common perfect elimination ordering of all odd powers of this graph. Moreover, we characterize those chordal graphs by forbidden isometric subgraphs for which any LexBFS-ordering of the graph is a common perfect elimination ordering of all powers. For MCS-orderings of chordal graphs the situation is worse: even for trees MCS does not give a common perfect elimination ordering of powers.

引用

页码：27 / 42

页数：16

共 14 条

[1]

BRANDSTADT A, 1991, SMDU199 GERH MERC U

[2]

BRANDSTADT A, 1994, LECT NOTES COMPUTER, V790, P237

[3]

BRANDSTADT A, 1994, IN PRESS DISCRETE MA

[4]

Dragan F.F., 1992, DISKRETNAJAMATEMATIK, V4, P67

[5]

DRAGAN FF, 1994, LECT NOTES COMPUTER, V775, P735

[6]

Duchet P., 1984, North-Holland Math. Stud., V88, P67, DOI 10.1016/S0304-0208(08)72924-4

[7] CONVEXITY IN GRAPHS AND HYPERGRAPHS [J].

FARBER, M ;

JAMISON, RE .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (03) :433-444

[8]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[9] ON THE SEMI-PERFECT ELIMINATION [J].

JAMISON, B ;

OLARIU, S .

ADVANCES IN APPLIED MATHEMATICS, 1988, 9 (03) :364-376

[10] ON POWERS AND CENTERS OF CHORDAL GRAPHS [J].

LASKAR, R ;

SHIER, D .

DISCRETE APPLIED MATHEMATICS, 1983, 6 (02) :139-147

← 1 2 →