Graphs with small boundary (Q879396): Difference between revisions

In a graph \(G\), a vertex \(x\) is a boundary vertex of a vertex \(y\) if they belong to the same (connected) component of \(G\) and the distance between \(y\) and each neighbor of \(x\) is at most the distance between \(y\) and \(x\). A boundary vertex is one that is a boundary vertex of some vertex. The boundary \(B(G)\) of \(G\) is the set of all boundary vertices in \(G\). Every connected graph with at least two vertices has at least two boundary vertices. The authors characterize connected graphs \(G\) with at most three boundary vertices as follows: \(| B(G)| = 2\) if and only if \(G\) is a path, and \(| B(G)| = 3\) if and only if \(G\) is a claw-like tree or a tripod. (A claw-like tree is a subdivision of the claw \(K_{1,3}\), and a tripod is obtained from a triangle \(H\) by taking a subset \(X\) of vertices of \(H\) and for each vertex \(x\in X\), preparing a path \(P_x\) and joining \(x\) and one of the endvertices of \(P_x\).) The authors also prove that the minimum degree of any connected graph \(G\) is at most six whenever \(G\) has exactly four boundary vertices.