Isometric-path numbers of block graphs.pdf

a r X i v : m a t h / 0 4 0 7 1 6 8 v 1 [ m a t h .C O ] 9 J u l 2 0 0 4 Mathematics Division, National Center for Theoretical Sciences at Taipei NCTS/TPE-Math Technical Report 2004-004 Isometric-path numbers of block graphs Jun-Jie Pan? Gerard J. Chang? Revised on March 10, 2004 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, algorithm 1 Introduction 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. This concept has a close relationship with the game of cops and robbers described as follows. The game is played by two players, the cop and the robber, on a graph. The two players move alternatively, starting with the cop. Each player’s first move consists of choosing a vertex at which to start. At each subsequent move, a player may choose either to stay at the same vertex or to move to an adjacent ?Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan. ?Department of Mathematics, National Taiwan University, Taipei 10617, Taiwan. E-mail: gjchang @math.ntu.edu.tw. Supported in part by the National Science Council under grant NSC90-2115-M002- 024. Member of Mathematics Division, National Center for Theoretical Sciences at Taipei. 1 vertex. The object for the cop is to catch the robber, and for the robber is to prevent this from happening. Nowakowski and Winkler [7] and Quilliot [8] independently proved that the cop wins if and only if the graph can be reduced to a single vertex by successively