Strong geodetic cores and Cartesian product graphs

Valentin Gledel, Vesna Iršič and Sandi Klavžar

Applied Mathematics and Computation, 2019, vol. 363, issue C, -

Abstract: The strong geodetic problem on a graph G is to determine a smallest set of vertices such that by fixing one shortest path between each pair of its vertices, all vertices of G are covered. To do this as efficiently as possible, strong geodetic cores and related numbers are introduced. Sharp upper and lower bounds on the strong geodetic core number are proved. Using the strong geodetic core number, an earlier upper bound on the strong geodetic number of Cartesian products is improved. It is also proved that sg(G □ K2) ≥ sg(G) holds for different families of graphs, a result conjectured to be true in general. Counterexamples are constructed demonstrating that the conjecture does not hold in general.

Keywords: Geodetic number; Strong geodetic number; Strong geodetic core; Complete bipartite graph; Cartesian product of graphs (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319306010
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:363:y:2019:i:c:45

DOI: 10.1016/j.amc.2019.124609

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().