Strong geodetic problem on complete multipartite graphs

DOI10.26493/1855-3974.1725.2E5MaRDI QIDQ5217086zbMATH OpenOpenAlexWikidataFDO

Authors Vesna Iršič, Matjaž Konvalinka

Publication date 21 February 2020

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

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

zbMATH Keywords

(complete) bipartite graphscomplete multipartite graphsgeodetic problemstrong geodetic problem

Mathematics Subject Classification ID

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The strong geodetic problem is to find the smallest number of vertices such that by fixing one shortest path between each pair, all vertices of the graph are covered. In this paper we study the strong geodetic problem on complete bipartite graphs; in particular, we discuss its asymptotic behavior. Some results for complete multipartite graphs are also derived. Finally, we prove that the strong geodetic problem restricted to (general) bipartite graphs is NP-complete.

Recommendations

• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• scientific article; zbMATH DE number 1145913
• Strong geodetic problem on Cartesian products of graphs
• Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes
• Strong geodetic problem in grid-like architectures

Cites work

• Block decomposition approach to compute a minimum geodetic set
• Computational Complexity of Geodetic Set
• Computing minimum geodetic sets of proper interval graphs
• Finding a dominating set on bipartite graphs
• Geodetic sets in graphs
• Geodetic sets in graphs
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• On pitfalls in computing the geodetic number of a graph
• On the hardness of finding the geodetic number of a subcubic graph
• Some remarks on the 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 problem in grid-like architectures
• Strong geodetic problem in networks
• Strong geodetic problem on Cartesian products of graphs
• The geodetic number of a graph

Cited in

(12)

• 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 edge geodetic problem on grids
• Strong geodetic problem in networks
• Strong edge geodetic problem in networks
• On the approximation hardness of geodetic set and its variants
• scientific article; zbMATH DE number 1145913 (Why is no real title available?)
• STRONG DOUBLY GEODETIC PROBLEM ON GRAPHS
• STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS
• Strong Edge Geodetic Problem on Complete Multipartite Graphs and some Extremal Graphs for the Problem
• On the computational complexity of the strong geodetic recognition problem
• Strong geodetic problem in grid-like architectures

This page was built for publication: Strong geodetic problem on complete multipartite graphs

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