# Fractional isometric path number

Abstract:

An isometric path is merely any shortest path between two vertices. The isometric path number is defined to be the minimum number of isometric paths required to cover the vertices of a graph. In this paper, we consider its fractional analogue. For classes of graphs such as trees, cycles and hypercubes, we determine the fractional isometric path number exactly. For square grid graphs, we provide lower and upper bounds. For grid graphs, finding the fractional isometric path number is equivalent to solving a network flow problem involving two simultaneous flows.

Tech Report Number:

CS-2004-02

Report Date:

February 1, 2004

Attachment | Size |
---|---|

CS-2004-02.pdf | 394.69 KB |