Strong edge geodetic problem on grids

DOI10.1007/S40840-021-01137-4MaRDI QIDQ2239003zbMATH OpenOpenAlexFDO

Authors Eva Zmazek

Publication date 2 November 2021

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

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

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)

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.

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

Cites work

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

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)