×

The closed geodetic numbers of graphs. (English) Zbl 1176.05040

Let \(G=(V,E)\) be a graph. For \(S\subseteq V\), the geodetic closure \(I_G[S]\) of \(S\) is the set of all vertices on geodesics between two vertices of \(S\). Geodetic number \(gn(G)\) is defined by \(gn(G)=\min\{|S|;\;I_G[S]=V\}\). The closed geodetic number \(cgn(G)\) is defined by \(cgn(G)=\min\{k;\;I_G[v_1,\dots,v_k]=V\) and \(v_i\notin I_G[v_1,\dots v_{i-1}]\) for \(2\leq i\leq k\}\).
In the paper there are characterized connected graphs \(G\) of order \(n\), for which \(cgn(G)=2,3,n-1,n\). The first two cases follow from the fact that \(gn(G)=cgn(G)\) if \(cgn(G)=2,3\). It is shown that for any positive integers \(k\) and \(n\) for which \(4\leq k\leq\lfloor\frac n2\rfloor\), there always exists a connected graph \(G\) with \(|V|=n\), \(gn(G)=4\) and \(sgn(G)=k\).

MSC:

05C38 Paths and cycles
PDFBibTeX XMLCite