On the Maximal Shortest Paths Cover Number

Iztok Peterin and Gabriel Semanišin
Additional contact information
Iztok Peterin: Institute of Mathematics and Physics, Faculty of Electrical Engineering and Computer Science, University of Maribor, 2000 Maribor, Slovenia
Gabriel Semanišin: Institute of Computer Science, Faculty of Science, Pavol Jozef Šafárik University, 041 54 Košice, Slovakia

Mathematics, 2021, vol. 9, issue 14, 1-10

Abstract: A shortest path P of a graph G is maximal if P is not contained as a subpath in any other shortest path. A set S ? V ( G ) is a maximal shortest paths cover if every maximal shortest path of G contains a vertex of S . The minimum cardinality of a maximal shortest paths cover is called the maximal shortest paths cover number and is denoted by ? ( G ) . We show that it is NP-hard to determine ? ( G ) . We establish a connection between ? ( G ) and several other graph parameters. We present a linear time algorithm that computes exact value for ? ( T ) of a tree T .

Keywords: distance; shortest path; maximal shortest paths cover; tree (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/14/1592/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/14/1592/ (text/html)

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:gam:jmathe:v:9:y:2021:i:14:p:1592-:d:589785

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().