Strong geodetic problem on Cartesian products of graphs

DOI10.1051/RO/2018003zbMATH Open1392.05033arXiv1708.02414OpenAlexW2963699455MaRDI QIDQ4579894FDOQ4579894

Authors: Vesna Iršič, Sandi Klavžar 

Publication date: 10 August 2018

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

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.

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

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

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)

Cites Work

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

Cited In (12)

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

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)