Strong edge geodetic problem on grids

2021/01/22 by Zmazek, Eva
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2101.09259

Abstract

Let G=(V(G),E(G)) be a simple graph. A set S ⊆ V(G) is a strong edge geodetic set if there exists an assignment of exactly one shortest path between each pair of vertices from S, such that these shortest paths cover all the edges E(G). The cardinality of a smallest strong edge geodetic set is the strong edge geodetic number sge(G) of G. In this paper, the strong edge geodetic problem is studied on the Cartesian product of two paths. The exact value of the strong edge geodetic number is computed for P_n \square P₂, P_n \square P₃ and P_n \square P₄. Some general upper bounds for sge(P_n \square P_m) are also proved.

Related

• Strong Edge Geodetic Problem on Complete Multipartite Graphs and some Extremal Graphs for the Problem
• Strong geodetic problem on Cartesian products of graphs
• Strong geodetic problem in grid like architectures
• Strong geodetic cores and Cartesian product graphs
• Strong geodetic number of complete bipartite graphs and of graphs with\n specified diameter