On minimal embedding of two graphs as center and periphery
As usual, the distance \(d(u,v)\) between two vertices of a graph is the length of the shortest path joining them. The eccentricity of a vertex \(u\), denoted \(e(u)\), is the maximum of the quantities \(d(u,v)\), where \(v\) ranges over the vertex set. The minimum of the vertex eccentricities of a graph is known as the radius of \(G\) and is denoted \(r(G)\). The maximum of the vertex eccentricities is the diameter of \(G\) and is denoted \(\text{dia}(G)\). The center of \(G\) is the subgraph induced by the set of vertices \(v\) with \(e(v)=\text{dia}(G)\). For graphs \(G_ 1\) and \(G_ 2\) and an integer \(d\), \(2\leq d\leq r(G_ 2)\), let \(\Gamma\) be the set of all graphs \(G\) so that \(G_ 1\) is the center of \(G\) and \(G_ 2\) is the periphery. Let \(\Gamma_ d\) be the subset of \(\Gamma\) where \(\text{dia}(G)=d\). Define \(\beta(G_ 1,G_ 2)\) to be the minimum of the number of vertices of \(G\), \(G\in\Gamma\). Define \(\beta(G_ 1,G_ 2,d)\) to be the minimum of the number of vertices of \(G\), \(G\in\Gamma_ d\). The paper under review investigates the values of \(\beta(G_ 1,G_ 2)\) and the upper bound of \(\beta(G_ 1,G_ 2,d)\).
scientific article; zbMATH DE number 490738