On strong geodeticity in the lexicographic product of graphs

Abstract

The strong geodetic number of a graph and its edge counterpart are recent variations of the pioneering geodetic number problem. Covering every vertex and edge of $ G $, respectively, using a minimum number of vertices and the geodesics connecting them, while ensuring that one geodesic is fixed between each pair of these vertices, is the objective of the strong geodetic number problem and its edge version. This paper investigates the strong geodetic number of the lexicographic product involving graph classes that include complete graph $ K_{m} $, path $ P_{m} $, cycle $ C_{m} $ and star $ K_{1, \, m} $ paired with $ P_{n} $ and with $ C_{n} $. Furthermore, the parameter is studied in the lexicographic product of, arbitrary trees with diameter-2 graphs whose geodetic number is equal to 2, $ K_{n}-e $ with $ K_{2} $ and their converses. Upper and lower bounds for the parameter are established for the lexicographic product of general graphs and in addition, the edge variant of the aforementioned problem is studied in certain lexicographic products. The strong geodetic parameters considered in this paper have pivotal applications in social network problems, thereby making them indispensable in the realm of graph theoretical research. This work contributes to the expansion of the current state of research pertaining to strong geodetic parameters in product graphs.

Keywords

• strong geodetic number
• lexicographic product
• strong edge geodetic number
• shortest path