Fractional isometric path number

Authors: 

Shannon L. Fitzpatrick
Jeannette C.M. Janssen
Richard J. Nowakowski

Author Addresses: 

Jeannette Janssen (janssen@mathstat.dal.ca)
Richard Nowakowski (rjn@mathstat.dal.ca)
Dept. of Mathematics and Statistics
Dalhousie University
B3H 3J5 Halifax, NS

Shannon Fitzpatrick (slfitzpatric@upei.ca)
Dept. of Mathematics and Computer Science
University of Prince Eward Island
C1A 4P3 Charlottetown, PEI

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
AttachmentSize
PDF icon CS-2004-02.pdf394.69 KB