An application of path polynomials to discrete random allocation problems

Abstract

The path polynomial of a graph is used to investigate certain models associated with random space filling problems. In particular, various discrete forms of Renyi's Random Parking Problem[4, 5, 6] can be modeled by path covers of chains. There are also equivalent finite resource allocation problems in Computer Science which can be investigated, by means of path polynomials of graphs.