Graphs with small boundary
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.
- Graphs with small book thickness
- Boundary-type sets in maximal outerplanar graphs
- Boundary domination in graphs
- scientific article; zbMATH DE number 1404133 (Why is no real title available?)
- Graph Stories in Small Area
- Strict boundary vertices of a graph
- The boundary of a graph and its isoperimetric inequality
- Graphs with four boundary vertices
- A characterization of graphs with at most four boundary vertices
- Reconstructing a graph from the boundary distance matrix
- Lower bounding the boundary of a graph in terms of its maximum or minimum degree
This page was built for publication: Graphs with small boundary
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879396)
