On the structure of graphs with few P4s

被引：39

作者：

Babel, L

Olariu, S ^{[1
]}

机构：

[1] Old Dominion Univ, Dept Comp Sci, Norfolk, VA 23529 USA

[2] Tech Univ Munich, Inst Math, D-80290 Munchen, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 1998年 / 84卷 / 1-3期

关键词：

D O I：

10.1016/S0166-218X(97)90120-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present new classes of graphs for which the isomorphism problem can be solved in polynomial time. These graphs are characterized by containing - in some local sense - only a small number of induced paths of length three. As it turns out, every such graph has a unique tree representation: the internal nodes correspond to three types of graph operations, while the leaves are basic graphs with a simple structure. The paper extends and generalizes known results about cographs, P-4-reducible graphs, and P-4-sparse graphs. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：1 / 13

页数：13

共 17 条

[1]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[2]

[Anonymous], 1979, CS7704 U WAT COMP SC

[3] The isomorphism problem for directed path graphs and for rooted directed path graphs [J].