Strong geodetic problem in grid-like architectures

DOI10.1007/S40840-018-0609-XMaRDI QIDQ723639zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• Analogies between the geodetic number and the Steiner number of some classes of graphs
• Block decomposition approach to compute a minimum geodetic set
• Computing minimum geodetic sets of proper interval graphs
• Geodesic Convexity in Graphs
• Geodetic sets in graphs
• Isometric path numbers of graphs
• On the Steiner, geodetic and hull numbers of graphs
• On the geodetic and the hull numbers in strong product graphs
• On the geodetic number and related metric sets in Cartesian product graphs
• Products of geodesic graphs and the geodetic number of products
• Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs
• Strong edge geodetic problem in networks
• The Steiner number of a graph
• The geodetic number of a graph
• The geodetic number of the lexicographic product of graphs
• The geodetic numbers of Cartesian products of trees
• The isometric path number of a graph
• Topics in graph theory. Graphs and their Cartesian product

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
• Strong geodetic number of graphs and connectivity
• On the computational complexity of the strong geodetic recognition problem
• On the approximation hardness of geodetic set and its variants
• scientific article; zbMATH DE number 1104386 (Why is no real title available?)

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)