|
|||||
|
|
Isometric-path numbers of block graphs |
|
| Authors: | Jun-Jie Pan |
| Affiliation: | a Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan b Department of Mathematics, National Taiwan University, Taipei 10617, Taiwan c Mathematics Division, National Center for Theoretical Sciences at Taipei, Old Mathematics Building, National Taiwan University, Taipei 10617, Taiwan |
| 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 required to cover all vertices of G. In this paper, we determine exact values of isometric-path numbers of block graphs. We also give a linear-time algorithm for finding the corresponding paths. |
| Keywords: | Isometric path Block graph Cut-vertex Algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |