On the reconstruction of planar graphs

被引：5

作者：

Bilinski, Mark

Kwon, Young Soo

Yu, Xingxing ^{[1
]}

机构：

[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

[2] Yeungnam Univ, Dept Math, Kyongsan 712749, South Korea

[3] Nankai Univ, Ctr Combinator, LPMC, Tianjin 300071, Peoples R China

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2007年 / 97卷 / 05期

基金：

中国国家自然科学基金; 新加坡国家研究基金会;

关键词：

reconstruction; recognition; planar graph; non-separating cycle; wheel neighborhood;

D O I：

10.1016/j.jctb.2006.12.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the planarity of a graph can be recognized from its vertex deleted subgraphs, which answers a question posed by Bondy and Hemminger in 1979. We also state some useful counting lemmas and use them to reconstruct certain planar graphs. (c) 2007 Elsevier Inc. All rights reserved.

引用

页码：745 / 756

页数：12

共 18 条

[1]

Bondy J. A., 1977, Journal of Graph Theory, V1, P227, DOI 10.1002/jgt.3190010306

[2]

BONDY JA, 1991, P 13 BRIT COMB C, P221

[3]

Diestel R., 2000, GRAPH THEORY

[4]

ELLINGHAM MN, 1988, C NUMER, V62, P3

[5] THE RECONSTRUCTION OF MAXIMAL PLANAR GRAPHS .1. RECOGNITION [J].

FIORINI, S ;

LAURI, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 30 (02) :188-195

[6] THEOREM ON PLANAR GRAPHS WITH AN APPLICATION TO RECONSTRUCTION PROBLEM .1. [J].

FIORINI, S .

QUARTERLY JOURNAL OF MATHEMATICS, 1978, 29 (115) :353-361

[7]

FIORINI S, 1978, J COMBINATORICS INFO, V3, P200

[8]

Harary F., 1964, Theory of graphs and its applications, P47

[9]

HEMMINGER RL, 1985, RECONSTRUCTION GRAPH

[10]

Kelly Paul J., 1957, Pacific J. Mathe, V7, P961

← 1 2 →