Isometric path numbers of graphs

2003/10/21 by Junjie Pan, Jun-Jie Pan, Pan, Jun-Jie +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Graph Labeling and Dimension Problems #math.CO #msc:05C38 #msc:05C70

paper · pdf · doi:10.48550/arxiv.math/0310332

9 pages

arxiv created 2003/10/21 · arxiv updated 2009/12/01

Abstract

An isometric path between two vertices in a graph G is a shortest path joining them. The isometric path number of G, denoted by \ip(G), is the minimum number of isometric paths needed to cover all vertices of G. In this paper, we determine exact values of isometric path numbers of complete r-partite graphs and Cartesian products of 2 or 3 complete graphs.

Related

• Isometric-path numbers of block graphs
• On the isometric path partition problem
• Isometric and induced path partitions: a new upper bound and a characterization of some extremal graphs
• Isometric path complexity of graphs
• Counterexamples to statements on isometric graph coverings