RECOGNIZING LOCALLY EQUIVALENT GRAPHS

被引：34

作者：

BOUCHET, A

机构：

[1] Université du Maine

来源：

DISCRETE MATHEMATICS | 1993年 / 114卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(93)90357-Y

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

To locally complement a simple graph F at one of its vertices v is to replace the subgraph induced by F on n(v)={w: vw is an edge of F} by the complementary subgraph. Graphs related by a sequence of local complementations are said to be locally equivalent. We describe invariants of locally equivalent graphs and a polynomial algorithm to recognize locally equivalent graphs. An application is given to counting the number of graphs locally equivalent to a given one. © 1993.

引用

页码：75 / 86

页数：12

共 15 条

[1]

[Anonymous], 1989, ANN NEW YORK ACAD SC, DOI DOI 10.1111/J.1749-6632.1989.TB22439.X

[2] DISTANCE-HEREDITARY GRAPHS [J].