A finite, connected simple graph \(G\) is a geodetic graph if and only if for each pair of vertices \(v_i, v_j\) there exists a unique distance path (or unique shortest \(v_iv_j\)-path). The insertion of vertices in an edge or edges of a non-geodetic graph \(G\) to, if possible, obtain a resultant geodetic graph is called geodetication of the graph \(G\). The paper introduces two new graph parameters generally called the Ruv\(\acute{e}\) numbers of a graph. The Ruv\(\acute{e}\) numbers of \(G\) are denoted by \(\rho_1(G)\) and \(\rho_2(G)\) respectively, and \(\rho_1(G) = \rho_2(G) = 0\) if and only if \(G\) is geodetic. Furthermore, for some graphs the parameter, \(\rho_1(G) \to \infty\). The latter graphs \(G\) do not permit geodetication in respect of \(\rho_1(G)\). It is evident that geodetication presents various challenging minimization problems. The core field of application will be, restricting graphs to distance path uniqueness. Intuitive applications are foreseen in military science, IT anti-hacking coding and predictive flow through networks.
It is assumed that the reader has good knowledge of the basic notions and notation in graph theory. For reference reading see [1,2]. For this introductory study a graph \(G\) will be a finite, connected simple graph. Reference to vertices \(v_i,v_j\) (or \(u,v\)) in a particular graph \(G\) will mean that \(v_i\) and \(v_j\) (or \(u\) and \(v\)) are distinct vertices in \(G\). If a vertex (or more) is added to an edge (or edges) of a graph the operation is called vertex insertion or insert a vertex (or insert vertices). Recall that a graph \(G\) is a geodetic graph if and only if for each pair of vertices \(v_i, v_j\) there exists a unique distance path (or unique shortest \(v_iv_j\)-path). The length of such shortest path is denoted by \(d_G(v_i,v_j)\).
Definition 1. (Ruv\(\acute{e}_1\) number):Consider a non-geodetic graph \(G = (V,E)\) and let \(X = \{w_j: j \in \Bbb{N}\}\)(\(j\) sufficiently large) be a separate set of vertices. The Ruv\(\acute{e}_1\) number of \(G\) denoted by \(\rho_1(G)\) is the minimum number of vertices \(\rho_1(G)=|Y|\), \(w_i \in Y \subseteq X\), to be inserted in an edge or edges of \(G\) to, if possible, obtain a geodetic graph \(G'\) with \(V(G') = V(G) \bigcup Y\). If obtaining a finite \(\rho_1(G)\) is impossible then, \(\rho_1(G) \to \infty\) or for purposes of bounds, \(\rho_1(G) \geq \ell\) where, \(\ell \to \infty\). The latter graphs \(G\) do not permit geodetication in respect of \(\rho_1(G)\).
Definition 2. (Ruv\(\acute{e}_2\) number):Consider a non-geodetic graph \(G = (V,E)\) and let \(X = \{w_j: j \in \Bbb{N}\}\)(\(j\) sufficiently large) be a separate set of vertices. The Ruv\(\acute{e}_2\) number of \(G\) denoted by \(\rho_2(G)\) is the minimum number of vertices \(\rho_2(G)=|Y|\), \(w_i \in Y \subseteq X\), to be inserted in an edge or edges of \(G\) to obtain a graph \(G''\) such that, \(\forall~v_i,v_j \in V(G)\) the shortest \((v_i,v_j)\)-path in \(G''\) is unique.
Note that both the Ruv\(\acute{e}\) numbers are well-defined because,
(i) A graph \(G\) is well-defined,
(ii) It is permissible that \(|X| \to \infty\),
(iii) \(0 \leq \rho_1(G) \leq k\), \(k\in \Bbb{N}_0\) or \(\ell \to \infty\) is permissible,
(iv) Non-permissibility in respect of \(\rho_1(G)\) is unambiguous,
(v) \(0 \leq \rho_2(G) \leq k\), \(k\in \Bbb{N}_0\),
(vi) Both \(G'\) and \(G''\) are well-defined.
Three classical families of graphs i.e. complete graphs \(K_n\), \(n\geq 1\), odd cycles \(C_n\), \(n \geq 3\) and trees \(T\) will be of importance in this study. Note that a graph \(G\) from any of the three said families of graphs is geodetic thus has, \(\rho_1(G) = \rho_2(G) = 0\). Hereafter, unless mentioned otherwise, all graphs will be undirected, simple and connected non-geodetic graphs of order \(n \geq 4\). The operation to yield the graph \(G'\) or \(G''\) from \(G\) as per Definition 1 or Definition 2 respectively, is called geodetication of \(G\) in respective of \(\rho_1(G)\), \(\rho_2(G)\) respectively. If the context is clear we simply refer to geodetication. Note that geodetication in respect of \(\rho_1(G)\) or \(\rho_2(G)\) is an iterative graph operation. Hence in both cases, following the insertion of say, \(w_1\) in an edge of \(G\) a graph \(G_1\) is obtained to be considered and so on. The number of iterations required is exactly, \(\rho_1(G)\) or \(\rho_2(G)\) meaning, \(G_{\rho_1(G)} = G'\) and \(G_{\rho_2(G)} = G''\).
Various real world applications may require geodetication of a graph or a network. Whereas in \(G\), generic flow between \(v_i\) and \(v_j\) could be along different shortest paths such flow, following geodetication, is restricted to a unique distance path. For the Ruv\(\acute{e}_1\) number the vertices \(w_i \in Y\) are functional vertices whilst those for the Ruv\(\acute{e}_2\) number are blockage vertices. Conceptually similar studies have been published with regards to the notion of forbidden transitions in graphs. See [3-5]. The latter observation motivates this introductory study. The core field of application will be, restricting graphs to distance path uniqueness. Intuitive applications are foreseen in military science, IT anti-hacking coding and predictive flow through networks.
Sections 2 and 3 will provide preliminary results and concepts related to the Ruv\(\acute{e}_1\) number. Thereafter, a discussion of the Ruv\(\acute{e}_2\) number will follow.
Clearly, if \(G\) is geodetic then \(\rho_1(G) = 0\). It is well known that a cycle graph (or cycle) \(C_n\), \(n \geq 4\) and \(n\) is even, is non-geodetic. By inserting one \(w_i \in X\) to any edge of \(C_n\) the cycle \(C'_{n+1}\), \(n+1\) is odd is obtained. Since \(C'_{n+1}\) is geodetic it follows that for \(C_n\), \(n \geq 4\) and \(n\) is even, \(\rho_1(C_n) = 1\).
The \(J9\)-graphs were first defined in [6]. These graphs were independently conceptualized by Scott and Seymour in [7]. In [7] these graphs are called bananas. A revised though equivalent definition is provided below.
Definition 3. Take \(k \geq 1\) copies of a path \(P_n\), \(n \geq 3\). Let \(j = 1,2,3,\dots,k\). Merge the respective, \(k\) origin vertices and the \(k\) terminus vertices of the paths and label the vertices consecutively as follows:
\[u_1,v_{1,j},v_{2,j},\dots,v_{n-2,j},u_2,\,\, n\geq 3 \quad \text{for}\quad j= 1,2,3,\dots,k,\,\,k\geq 1.\]
The family of graphs is called the \(J9\)-graphs. A member of the \(J9\)-graphs is denoted by, \(P^{(k)}_n,\) and is called a Joost graph.
For this study we consider Joost graphs for \(k \geq 3\). Note that each such Joost graph has \(\binom{k}{2} \geq 3\) distinct \(C_n\) cycles each of even order. Hence, any Joost graph \(P^{(k)}_n\), \(k \geq 3\) is non-geodetic.
Proposition 1. A Joost graph \(G = P^{(k)}_n\), \(k \geq 3\) does not permit geodetication in respect of \(\rho_1(G)\).
Proof. Consider any Joost graph \(P^{(k)}_n\), \(k \geq 3\). Without loss of generality let step 1 of geodetication be inserting the first vertex \(w_1 \in X\) in any edge of the path labeled \(u_1,v_{1,1},v_{2,1},\dots,v_{n-2,1},u_2\). Exactly \(k-1\) distinct \(C_{n+1}\) cycles are of odd order are obtained. The remaining \(\binom{k}{2}-(k-1)\) distinct \(C_n\) cycles are of even order. At step 2 of geodetication that is, inserting vertex \(w_2 \in X\) either in an edge of \(u_1,v_{1,1},v_{2,1},\dots,v_{n-2,1},u_2\) or otherwise then, either \((k-1)\) distinct \(C_{n+2}\) cycles and \(\binom{k-1}{2}\) distinct \(C_n\) cycles are of even order or, exactly one \(C_{n+2}\) cycle is of even order. Note that other distinct \(C_n\) cycles of even order may exist as well. Clearly this dilemma perpetuates infinitely. Therefore, if \(k \geq 3\) then \(\rho(P^{(k)}_n) \to \infty\). Hence, a Joost graph \(P^{(k)}_n\), \(k \geq 3\) does not permit geodetication. ◻
Lemma 1. Consider two cycle \(C_n\), \(n \geq 3\) and \(C_m\), \(m \geq 3\). Obtain \(G\) by merging a vertex of \(C_n\) with a vertex of \(C_m\). This is called the Type I simple cycle link.
(i) If both \(n, m\) are odd then \(\rho_1(G) = 0\).
(ii) If say, \(n\) is odd and \(m\) is even then \(\rho_1(G) = 1\).
(iii) If both \(n, m\) are even then \(\rho_1(G) = 2\).
Proof. Result (i) follows from the fact the all odd cycles are geodetic.
Result (ii) follows from the fact that an even cycle is non-geodetic and requires the insertion of one vertex in any one edge of cycle \(C_m\).
Result (iii) follow from the fact that all even cycles are non-geodetic and require the insertion of one vertex in any one edge of each cycle. ◻
By immediate induction it follows cycles \(C_n\), \(C_m\), …, \(C_q\) can pairwise be merged by a common vertex in “treelike” fashion to construct multiple (clustered or chained) Type I simple cycle links. If a graph \(G\) has an induced cycle \(C_k\) such cycle is called a simple cycle (or unchorded cycle) in \(G\). A graph \(G\) is called a cactus graph if any two simple cycles in \(G\), if such exist, share at most one common vertex (Type I simple cycle link). Note that any tree and any cycle may be considered to be cactus graphs.
Proposition 2. Let \(G\) be a cactus graph which has \(t_1 \geq 0\) even simple cycles and \(t_2 \geq 0\) odd simple cycles. Then \(\rho_1(G) = t_1\).
Proof. If \(t_1 = 0\) then \(G\) is geodetic hence, \(\rho_1(G) = 0\). If \(t_1 > 0\) then \(G\) is non-geodetic. Then the result follows through the application of Lemma 1. ◻
Consider two cycle \(C_n\), \(n \geq 3\) and \(C_m\), \(m \geq 3\). Obtain \(G\) by merging a path section of \(C_n\) with a path section of \(C_m\). This is called the Type II simple cycle link. By immediate induction it follows cycles \(C_n\), \(C_m\), …, \(C_q\) can be merged in “treelike” fashion to construct multiple (clustered or chained) Type II simple cycle links. This family of graphs is called the anti-Ruv\(\acute{e}_1\) graphs (for brevity, \((a\)–\(R)\)-graphs).
Lemma 2. An anti-Ruv\(\acute{e}_1\) graph \(G\) does not permit geodetication in respect of \(\rho_1(G)\).
Proof. Clearly, \(G\) is non-geodetic. The proof follows by similar reasoning found in the proof of Proposition 1. ◻
Recall from [1] that a closed trail in a graph \(G\) is called a cycle in \(G\). The latter cycle in \(G\) may or may not be a simple cycle in \(G\). A graph without any cycle is a tree. It is axiomatically true that if a vertex (or more vertices) is inserted in an edge (or more edges) of a tree \(T\) only the distance between some pairs of vertices will increase. No cycle can be constructed in tree \(T\). In cyclic graphs, vertex insertion can only change the order of a cycle in \(G\) to switch between even and odd. It is axiomatically true that the insertion of a single vertex on an edge \(e\) of a particular cycle can switch the order of another cycle if and only if both cycles share \(e\) as a common edge. Hence, the latter two cycles induce a \((a\)–\(R)\)-graphs). Let,
\(\mathcal{G} = \{G: G\) has some \((a\)–\(R)\)–subgraph(s) and for each pair \(u\),\(v\) of vertices of a \((a\)–\(R)\)–subgraph say, \(H\) there exist a shortest \((u,v)\)–path of length \(d_G(u,v)\) in \(H\}\).
Theorem 1. A graph \(G\) permits geodetication in respect of \(\rho_1(G)\) if and only if \(G\) is \((G \in \mathcal{G})\)-free.
Proof. It is obvious that if \(G\) has an induced \((G \in \mathcal{G})\)-subgraph then \(G\) does not permit geodetication. If \(G\) is \((G \in \mathcal{G})\)-free then it is trivially possible to insert a sufficiently large number say, \(\ell\) vertices into some edges of \(G\) to yield a graph \(H\) which besides minimization (or minimum minimality), satisfies Definition 1. The aforesaid is possible because vertex insertion cannot construct a \((G \in \mathcal{G})\)-subgraph. Thus \(\rho_1(G) \leq \ell\) and \(\ell\) is finite. The aforesaid implies that graph \(G\) permits geodetication. ◻
Proposition 3. A complete bipartite graph of the form \(K_{n,m}\), \(n \geq m \geq 2\) does not permit geodetication in respect of \(\rho_1(G)\).
Proof. Let \(K_{n,m}\) have the independent vertex sets \(X = \{v_i: 1 \leq i \leq n\}\) and \(Y = \{u_i:1 \leq i \leq m\}\). The \(K_{m,m}\) induced subgraph of \(K_{n,m}\) can be presented diagrammatically as a chorded cycle \(C^{\oplus}_{2m}\). However, each vertex \(v_{m+1}\),\(v_{m+2},\dots,v_n\) when added with corresponding edges constructs a \((G \in \mathcal{G})\)-graph. By Theorem 1 the complete bipartite graph \(K_{n,m}\), \(n \geq m \geq 2\) does not permit geodetication. ◻
Clearly, if \(G\) is geodetic then \(\rho_2(G) = 0\). By inserting one \(w_i \in X\) to any edge of \(C_n\), \(n \geq 4\) and \(n\) is even the cycle \(C'_{n+1}\), \(n+1\) is odd is obtained. Since \(C'_{n+1}\) is geodetic it follows that for \(C_n\), \(n \geq 4\) and \(n\) is even, \(\rho_2(C_n) = 1\).
Lemma 3. A graph \(G\) always permit geodetication in respect of \(\rho_2(G)\).
Proof. It is known that if \(G\) is geodetic then \(\rho_2(G) = 0\). Hence, although geodetication is not required it is permitted. The aforesaid is equivalent to inserting the empty set \(\emptyset \subseteq X\) to some edges of \(G\). Assume \(G\) is non-geodectic. Then it is axiomatically valid that a sufficient number of vertices from the set \(X\) can be inserted in some edges (at most \(\lceil \frac{\varepsilon(G)}{2}\rceil\)) such that all induced subgraphs in \(G''\) restricted to vertices in \(V(G)\) will be trees. Since \(w_i \in Y\) is of no concern the vertex insertions can be done such that, \(\forall~v_i,v_j \in V(G)\) the shortest \((v_i,v_j)\)-path in \(G''\) is unique. This settles the result. ◻
Theorem 2. For a graph \(G\) it follows that, \(\rho_1(G) \geq \rho_2(G)\).
Proof. If \(G\) is geodetic then \(\rho_1(G)=\rho_2(G) = 0\). Assume \(G\) is non-geodectic and does not permit geodetication in respect of \(\rho_1(G)\). From Lemma 3 \(G\) permits geodetication in respect of \(\rho_2(G)\). Hence, \(\rho_2(G)\) is finite say, \(\rho_2(G) = k\). Surely, \(\rho_1(G) \geq \ell > k\), \(\ell \to \infty\).
Finally assume \(G\) is non-geodectic and permits geodetication in respect of \(\rho_1(G)\). Let \(\rho_1(G) = t\). If distance paths are tested which exclude \(w_i \in Y\) then, since \(G''\) is geodetic it implies that, \(\rho_1(G) \leq \rho_2(G)\). The latter is true because if \(\rho_1(G) >\rho_2(G)\) then, \(\rho_1(G)\) was not a minimum. It thus implies that \(\rho_1(G) = \rho_2(G)\). ◻
The next corollary is a direct consequence of the proof of Theorem 2.
Corollary 1. If a graph \(G\) permits geodetication in respect of \(\rho_1(G)\) then, \(\rho_1(G) = \rho_1(G)\).
Lemma 4. Consider two cycle \(C_n\), \(n \geq 3\) and \(C_m\), \(m \geq 3\). Obtain \(G\) by merging a section of length \(l\) of \(C_n\) with a path section of length \(l\) of \(C_m\).
(i) If both \(n, m\) are odd then \(\rho_2(G) = 2\).
(ii) If say, \(n\) is odd and \(m\) is even then \(\rho_1(G) = 1\).
(iii) If both \(n, m\) are even then \(\rho_1(G) = 2\).
Proof. (i) Insert a vertex \(w_i \in X\) in any edge of the common path section to obtain \(G''\). Clearly, the induced graph \(\langle V(G)\rangle\) in \(G''\) is a cactus with one even cycle. Hence, from Proposition 2 it follows that \(\rho_2(G) =2\).
(ii) Insert a vertex \(w_i \in X\) in any edge of the common path section to obtain \(G''\). Clearly, the induced graph \(\langle V(G)\rangle\) in \(G''\) is a cactus with one odd cycle. Hence, from Proposition 2 it follows that \(\rho_2(G) =1\).
(iii) Follow similar to result (i). ◻
It is assumed that the reader is familiar with the definitions of the line graph \(L(G)\), the middle graph \(M(G)\) and the total graph \(T(G)\) respectively, of a graph \(G\). Various results from [8] have relevance with regards to the study of the Ruv\(\acute{e}\) number. We recall four useful results from [8].
Lemma 5. (Lemma 2 in [8]). If a graph \(G\) is non-geodetic, then its line graph \(L(G)\) is non-geodetic.
Theorem 3. (Theorem 3 in [8]). Let \(G\) be a connected graph with at least one edge. Then the line graph \(L(G)\) is geodetic if and only if \(G\) is a tree or an odd cycle.
Corollary 2. (Corollary 2 in [8]). The middle graph \(M(G)\) of a connected graph \(G\) is geodetic if and only if \(G\) is a tree.
Theorem 4. (Theorem 4 in [8]). The total graph \(T(G)\) of a graph \(G\) is geodetic if and only if every connected component of \(G\) has at most one edge.
Without further proof we can deduce the following useful results with regards to the study of the Ruv\(\acute{e}\) number.
Theorem 5. (i) For a graph \(G\) the line graph \(L(G)\) is non-geodetic if \(G\) is non-geodetic or, not a tree nor an odd cycle.
(ii) Let \(G\) be, not a tree then the middle graph \(M(G)\) is non-geodetic.
(iii) If \(G\) has more than one edge then the total graph \(T(G)\) is non-geodetic.
Theorem 5 read together with Theorem 1 distinguishes which of the line, middle and total graphs of a graph, permit (or not permit) geodetication.
Recall that the corona of the two graphs \(G\) of order \(n\) with \(H\) of order \(m\) and denoted by \(G\circ H\) is the operation whereby we take \(n\) copies of \(H\) labeled \(H_i\), \(i = 1,2,3,\dots,n\) and attach the vertex \(v_i \in V(G)\) to each vertex \(u_{i,l} \in V(H_i)\), \(l = 1,2,3,\dots,m\). Recall that \(K_1+H\) is obtained by attaching the vertex \(K_1\) to each vertex in \(V(H)\).
Theorem 6. For \(G\circ H\) where both \(G\) and \(H\) permits geodetication in respect of \(\rho_1(G)\), \(\rho_2(H)\) respectively, let \(diam(H) = t\). Then,
\[\rho_1(G\circ H) \leq \rho_1(G) + min\{2n\varepsilon(H),n((m-1)(t-1) + \rho_1(H))\},\] and, \[\rho_2(G\circ H) \leq \rho_2(G) + min\{2n\varepsilon(H),n((m-1)(t-1) + \rho_2(H))\}.\]
Proof. Part 1: Requiring the term \(\rho_1(G)\) is obvious. For each of the \(n\) subgraphs which are isomorphic to \(K_1+H\) at least two options are considered. Option 1 is to insert two vertices from \(X\) in each edge of each \(H_i\). The latter option will for each pair \(u_{i,j},u_{i,k} \in V(H_i)\) result in a unique distance path of length two. For each \(v_j \in V(G)\) the second option is to insert \((t-1)\) vertices from \(X\) in all but one of the edges \(v_ju_{i,k}\), \(u_{i,k} \in V(H_i)\) and to geodeticate each \(H_i\) in respect of \(\rho_1(H_i)\). Any of the two options will yield a unique distance path for any pair \(v_i, u_{j,l}\) and any pair \(u_{i,j},u_{i,k}\). Clearly, the minimum of the two options i.e. \(min\{2n\varepsilon(H),n((m-1)(t-1) + \rho_2(H))\} \geq 0\) yields an upper bound.
Part 2: The result follows by similar reasoning to that in Part 1. ◻
the next corollary requires no further proof.
Corollary 3. For graphs \(G\) and \(H\) in Theorem 6 both, \(\rho_1(G) \geq 0\) and \(\rho_1(H) \geq 0\) and both be finite. Furthermore, Theorem 6 settles all the possible cases i.e.:
(i) \(\rho_1(G) > 0\) and \(\rho_1(H) > 0\),
(ii) \(\rho_1(G) = 0\) and \(\rho_1(H) = 0\),
(iii) \(\rho_1(G) > 0\) and \(\rho_1(H) = 0\),
(iv) \(\rho_1(G) = 0\) and \(\rho_1(H) > 0\).
Finally, the same applies to \(\rho_2(G)\) and \(\rho_2(H)\).
Finding an efficient algorithm to obtain \(\rho_1(G)\) and \(\rho_2(G)\) is of importance. The complexity of an exhaustive method lies in the fact that geodetication is an iterative graph operation. It requires the evaluation of,
\(\prod\limits_{i=0}^{\rho_1(G)~ or~ \rho_2(G)}(n+i-1)\)
possibe vertex insertions. On completion we have that,
(i) \(\varepsilon(G') = \varepsilon(G) + \rho_1(G)\),
(ii) \(\varepsilon(G'') = \varepsilon(G) + \rho_2(G)\).
In any graph the distance path between any pair of adjacent vertices
is unique. It can be said that any graph is partially
1-geodetic. A cycle \(C_n\), \(n \geq 4\) and \(n\) is even is partially \((\frac{n}{2}-1)\)-geodetic in that all
distance paths of length \(1 \leq l \leq
\frac{n}{2}-1\) are unique. Therefore, any graph \(G\) is partially \(l\)-geodetic for some \(1 \leq l \leq diam(G)-1\). Note that if
\(l = diam(G)\) that \(G\) is geodetic. Author proposes that the
notion of partially \(l\)-geodetic
graphs is worthy of further research. More specifically in the context
of research related to the Ruv\(\acute{e}\) numbers of graphs.
For a graph \(G\) define the total
distance weight as,
\(\psi(G) = \sum\limits_{\forall v_i,v_j \in V(G)}d_G(v_i,v_j)\).
In respect of \(G'\) (geodetication in respect of \(\rho_1(G)\)) the total distance weight is restricted to,
\(\psi(G') = \sum\limits_{\forall v_i,v_j \in V(G')}d_{G'}(v_i,v_j)\).
Clearly, after geodetication of \(G\) we have that, \(\psi(G) \leq \psi(G')\). Let the edge
\(e_q = v_iv_j\) and let the string
\(s_q = [e_q:w_k,w_l,\dots,w_t]\)
denote the vertices inserted in \(e_q\). Let a geodetication set of \(G\) be \(Y =
\{s_q: 1 \leq q \leq \varepsilon(G)\}\).
Problem 1: Find a geodetication set \(Y\) of \(G\) such that \(\psi(G') – \psi(G)\) is a minimum.
If a graph \(G\) has say, one induced \(M = (G \in \mathcal{G})\)-subgraph then a minimum number of edges can be added to complete \(M\), to obtain a graph \(G^\star\) which will permit geodetication in respect of \(\rho_1(G^\star)\). Clearly, \(G\) may have more than one \((G \in \mathcal{G})\)-subgraph. The minimum number of edges to be added to \(G\) to obtain \(G^\star\) is called the edge-Ruv\(\acute{e}\) number of a \(G\). The edge-Ruv\(\acute{e}\) number is denoted by \(\rho^e(G)\). Further research on \(\rho^e(G)\) remains open.
Another interesting observation is that the Cartesian product \(P_n \times P_2\), \(n \geq 2\) yields a ladder graph \(L_n\). Note that although both \(P_n\) and \(P_2\) are geodetic hence, \(\rho_{1,2}(P_n) = \rho_{1,2}(L_2) = 0\), the ladder is a \((a\)–\(R)\)-graph. The transition between geodeticability was from one extreme to the other extreme. In other words, whereas neither \(P_n\) nor \(P_2\) requires geodetication in respect of \(\rho_1\), the ladder does not permit geodetication in respect of \(\rho_1(L_n)\). This observation leads to a trivial theorem.
Theorem 7. For any graph \(G\) of order \(n \geq 3\) let \(H = G\times P_2\). The graph \(G\) does not permit geodetication in respect of \(\rho_1(H)\).
Proof. Because \(G \times P_2\) is a prism or prism-like it has either an induced ladder subgraph or an induced circular ladder subgraph. Thus it contains a \((G \in \mathcal{G})\)-subgraph. Hence, by Theorem 1 the graph \(H\) does not permit geodetication in respect of \(\rho_1(H)\). ◻
Researching the Cartesian product to gain an understanding in respect of geodeticability in respect of \(\rho_1(H)\) is deemed a worthy avenue. Numerous other graph products can be studied.
Geodetication in respect of \(\rho_1(G)\) or \(\rho_2(G)\) may change certain graph parameters. One example, is that the chromatic number of an even cycle is given by \(\chi(C_n) = 2\). After inserting one vertex into any edge an odd cycle is obtained and \(\chi(C'_{n+1}) = 3\). Let \(t\) be even then a cycle \(C_{3t}\) has domination number \(\gamma(C_n) = \lceil \frac{3t}{3}\rceil = t\). The cycle \(C_{3t+1}\) has \(\gamma(C_n) = t+1\). Some parameters for some graphs will remain unchanged. For example, let \(n\) be even then the independence number of \(C_n\) is \(\alpha(C_n) = \frac{n}{2} = t\). However, \(\alpha(C_{n+1}) = \lfloor \frac{n+1}{2}\rfloor = t\). In the case of \(\rho_2(G)\) it is suggested to insert the \(\rho_2(G)\) vertices as multiples into the minimum number of edges of \(E(G)\) to be optimal. In more advanced graphs the notion of geodetication sets come into play. Since various graph parameters are possibly changed for some graphs through geodetication, numerous minimization problems similar to Problem 1 come to the fore.
Finding an efficient algorithm to test whether or not a graph \(G\) is \((a\)–\(R)\)-free is of importance. Adaption of Brent’s algorithm [9] or other can be considered. Complexity studies with regards to finding \(\rho_1(G)\) will be insightfull.
This paper is dedicated to Ruv\(\acute{e}\) de Beer. Ruv\(\acute{e}\) is a very special family member of the author.
The author would like to thank the anonymous referees for their constructive comments, which helped to improve the elegance of this paper.
The author declares there is no conflict of interest in respect of this research.