Strong geodetic problem on Cartesian products of graphs

DOI10.1051/RO/2018003MaRDI QIDQ4579894zbMATHOpenAlexFDO

Authors Vesna Iršič, Sandi Klavžar

Publication date 10 August 2018

Published in RAIRO - Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

Cartesian productsubgraphgeodetic problemstrong geodetic problemisometric path problem

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The strong geodetic problem is a recent variation of the geodetic problem. For a graph $G$, its strong geodetic number $msg(G)$ is the cardinality of a smallest vertex subset $S$, such that each vertex of $G$ lies on a fixed shortest path between a pair of vertices from $S$. In this paper, the strong geodetic problem is studied on the Cartesian product of graphs. A general upper bound for $msg(G,square,H)$ is determined, as well as exact values for $K_m,square,K_n$, $K_{1,k},square,P_l$, and certain prisms. Connections between the strong geodetic number of a graph and its subgraphs are also discussed.

Recommendations

• Strong geodetic cores and Cartesian product graphs
• Strong geodetic problem in grid-like architectures
• Strong edge geodetic problem on grids
• Strong geodetic number of graphs and connectivity
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter

Cites work

• scientific article; zbMATH DE number 1439423 (Why is no real title available?)
• Block decomposition approach to compute a minimum geodetic set
• Extreme Geodesic Graphs
• Geodesic Convexity in Graphs
• Geodetic contraction games on graphs
• Geodetic number versus hull number in \(P_3\)-convexity
• Geodetic sets in graphs
• Graphs with large geodetic number
• Handbook of product graphs
• Isometric path numbers of graphs
• Products of geodesic graphs and the geodetic number of products
• Strong edge geodetic problem in networks
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• Strong geodetic problem in grid-like architectures
• The geodetic number of a graph
• The geodetic numbers of graphs and digraphs
• The isometric path number of a graph

Cited in

(13)

• Strong geodetic cores and Cartesian product graphs
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• On the computational complexity of the strong geodetic recognition problem
• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
• Strong Edge Geodetic Problem on Complete Multipartite Graphs and some Extremal Graphs for the Problem
• Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes
• STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS
• Strong geodetic number of graphs and connectivity
• Strong geodetic problem in grid-like architectures
• Strong edge geodetic problem in networks
• Strong edge geodetic problem on grids
• STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS
• Strong geodetic problem on complete multipartite graphs

This page was built for publication: Strong geodetic problem on Cartesian products of graphs

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