Graphs with four boundary vertices (Q625373)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs with four boundary vertices |
scientific article |
Statements
Graphs with four boundary vertices (English)
0 references
17 February 2011
0 references
Summary: A vertex \(v\) of a graph \(G\) is a boundary vertex if there exists a vertex u such that the distance in \(G\) from \(u\) to \(v\) is at least the distance from \(u\) to any neighbour of \(v\). We give a full description of all graphs that have exactly four boundary vertices, which answers a question of Hasegawa and Saito. To this end, we introduce the concept of frame of a graph. It allows us to construct, for every positive integer \(b\) and every possible ``distance-vector'' between \(b\) points, a graph \(G\) with exactly \(b\) boundary vertices such that every graph with \(b\) boundary vertices and the same distance-vector between them is an induced subgraph of \(G\).
0 references
boundary vertex
0 references
distance vector
0 references
frame of a graph
0 references