Strong geodetic problem in grid-like architectures

DOI10.1007/S40840-018-0609-XzbMATH Open1393.05098arXiv1708.03869OpenAlexW2746832592MaRDI QIDQ723639FDOQ723639

Authors: Sandi Klavžar, Paul Manuel 

Publication date: 24 July 2018

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

Abstract: A recent variation of the classical geodetic problem, the strong geodetic problem, is defined as follows. If $G$ is a graph, then $msg(G)$ is the cardinality of a smallest vertex subset $S$, such that one can assign a fixed geodesic to each pair $x,ysubseteqS$ so that these $$ geodesics cover all the vertices of $G$. In this paper, the strong geodesic problem is studied on Cartesian product graphs. A general upper bound is proved on the Cartesian product of a path with an arbitrary graph and showed that the bound is tight on flat grids and flat cylinders.

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

Recommendations

• Strong geodetic problem on Cartesian products of graphs
• Strong edge geodetic problem on grids
• Strong geodetic cores and Cartesian product graphs
• Strong geodetic number of graphs and connectivity
• Strong geodetic problem on complete multipartite graphs

zbMATH Keywords

Cartesian product of graphscylindersgridsgeodetic problemstrong geodetic problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

• Geodesic Convexity in Graphs
• Computing minimum geodetic sets of proper interval graphs
• Topics in graph theory. Graphs and their Cartesian product
• On the geodetic and the hull numbers in strong product graphs
• The geodetic number of a graph
• On the geodetic number and related metric sets in Cartesian product graphs
• The Steiner number of a graph
• Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs
• The geodetic number of the lexicographic product of graphs
• On the Steiner, geodetic and hull numbers of graphs
• The geodetic numbers of Cartesian products of trees
• 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
• Analogies between the geodetic number and the Steiner number of some classes of graphs

Cited In (15)

• 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 number of complete bipartite graphs and of graphs with specified diameter
• Strong geodetic problem in networks
• Strong geodetic problem on Cartesian products of graphs
• 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
• On the approximation hardness of geodetic set and its variants
• Title not available (Why is that?)

This page was built for publication: Strong geodetic problem in grid-like architectures

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