Strong edge geodetic problem on grids

DOI10.1007/S40840-021-01137-4zbMATH Open1476.05046arXiv2101.09259OpenAlexW3165316363MaRDI QIDQ2239003FDOQ2239003

Authors: Eva Zmazek 

Publication date: 2 November 2021

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Abstract: Let $G=(V(G),E(G))$ be a simple graph. A set $SsubseteqV(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 $extsge(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_2$, $P_n,square,P_3$ and $P_n,square,P_4$. Some general upper bounds for $extsge(P_n,square,P_m)$ are also proved.

Full work available at URL: https://arxiv.org/abs/2101.09259

Recommendations

• Strong geodetic problem in grid-like architectures
• Strong geodetic problem on Cartesian products of graphs
• Strong geodetic cores and Cartesian product graphs
• The edge geodetic number of product graphs
• The edge geodetic number and Cartesian product of graphs

zbMATH Keywords

strong geodetic problemCartesian product of pathsstrong edge geodetic problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• The geodetic number of a graph
• Strong edge geodetic problem in networks
• Strong geodetic problem in grid-like architectures
• Strong geodetic number of graphs and connectivity
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• Strong geodetic problem in networks
• Edge geodetic number of a graph
• Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes
• Strong geodetic cores and Cartesian product graphs
• Strong geodetic problem on Cartesian products of graphs
• Strong geodetic problem on complete multipartite graphs
• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs

Cited In (7)

• Strong geodetic cores and Cartesian product graphs
• Strong geodetic problem in grid-like architectures
• Strong geodetic problem on Cartesian products of graphs
• The edge geodetic number of product graphs
• Strong Edge Geodetic Problem on Complete Multipartite Graphs and some Extremal Graphs for the Problem
• Strong edge geodetic problem in networks
• On the approximation hardness of geodetic set and its variants

This page was built for publication: Strong edge geodetic problem on grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2239003)