ON COVERING THE POINTS OF A GRAPH WITH POINT DISJOINT PATHS.

F. T. Boesch, S. Chen, J. A.M. McHugh

Research output: Contribution to conferencePaperpeer-review

34 Scopus citations

Abstract

The minimum number of point disjoint paths which cover all the points of a graph defines a covering number denoted by zeta . The relation of zeta to some other well-known graphical invariants is discussed, and zeta is evaluated for a variety of special classes of graphs. A simple algorithm is developed for determining zeta in the case of a tree, and it is shown that this tree algorithm can be generalized to yield zeta for any connected graph. Degree conditions are also derived which yield simple upper bounds for zeta .

Original languageEnglish (US)
Pages201-212
Number of pages12
DOIs
StatePublished - 1974
Externally publishedYes
EventCap Conf on Graph Theory and Comb, Proc, Graphs and Comb - Washington, DC, USA
Duration: Jun 18 1973Jun 22 1973

Other

OtherCap Conf on Graph Theory and Comb, Proc, Graphs and Comb
CityWashington, DC, USA
Period6/18/736/22/73

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this