Contents

Research note: Ruv\(\acute{e}\) numbers of a graph

Author(s): Johan Kok1
1Independent Mathematics Researcher, City of Tshwane, South Africa Visiting Faculty at CHRIST (Deemed to be a University), Bangalore, India.
Copyright © Johan Kok. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

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.

Keywords: Ruv\’e number; geodetication; geodetication set; anti-Ruv\(\acute{e}\) graph.