On the edge-reconstruction of 3-connected planar graphs with minimum valency 4

✍ Scribed by Yue Zhao

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 550 KB
• Volume: 137
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0133-o

✦ Synopsis

It is shown that a 3-connected planar graph with minimum valency 4 is edge-reconstructible if no 4-vertex is adjacent to a 5-vertex.

1. Introduction

In this paper, all graphs G=(V(G),E(G)) considered will be finite and simple. A connected graph G is said to have connectivity k o = ko(G) if the deletion of some set of ko vertices disconnects G and ko is the least integer with this property. For any k<~ko,G is said to be k-connected. If ko(G)= 1, G is said to be separable. A set S of vertices is said to be a cut set of G if the deletion of the vertices of S from G disconnects G. A graph is planar if it can be embedded in the plane; such an embedding is called a plane graph. A well-known result states that a 3-connected planar graph has a unique embedding in the plane. Thus, when G is a 3-connected planar graph we may assume with no loss of the generality that G is a plane graph. A k-vertex is a vertex of valency k. A k-face of a plane graph is a face whose boundary is a k-circuit. A subgraph C[a,b] is said to be a chain from a to b, or an [a,b]-chain if and V(C[a, b])= {a = Vo, vl, ..., v~=b} E(C[a,b ]): {viVi+ l ; i:O, 1 ..... t--1}. We use d(v) and d(x, y) to denote the degree of a vertex v and the distance between vertices x and y respectively. We define. dl(G) = min {d(x, y); x, ye V(G) with d(x) = 4, d(y) = 5 },