Decomposition of Graphs into Geodesic Paths

A path cover of a graph G is a set of non-trivial paths in G such that every edge of G lies in exactly one path in the set. A simple geodesic path cover (SGPC) of a graph G is a decomposition of G into shortest paths such that any two members of the decomposition share at most one vertex. The minimum cardinality of a SGPC of G is called the simple geodesic path covering number of G and is denoted by πsg(G). In this paper, we determine the value of πsg for some common classes of graphs such as paths, cycles, trees, complete graphs, wheels, and uni-cyclic graphs. Also we discuss relationship of πsg with some existing path covering parameters.

View article page

Download PDF