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

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

doi:10.1007/bfb0066442

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

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

Research output: Contribution to conference › Paper › peer-review

38 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 language	English (US)
Pages	201-212
Number of pages	12
DOIs	https://doi.org/10.1007/bfb0066442
State	Published - 1974
Externally published	Yes
Event	Cap Conf on Graph Theory and Comb, Proc, Graphs and Comb - Washington, DC, USA Duration: Jun 18 1973 → Jun 22 1973

Other

Other	Cap Conf on Graph Theory and Comb, Proc, Graphs and Comb
City	Washington, DC, USA
Period	6/18/73 → 6/22/73

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1007/bfb0066442

Cite this

@conference{a45aa5b2faf54e7eac1acc7f6ba89738,

title = "ON COVERING THE POINTS OF A GRAPH WITH POINT DISJOINT PATHS.",

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 .",

author = "Boesch, {F. T.} and S. Chen and McHugh, {J. A.M.}",

year = "1974",

doi = "10.1007/bfb0066442",

language = "English (US)",

pages = "201--212",

note = "Cap Conf on Graph Theory and Comb, Proc, Graphs and Comb ; Conference date: 18-06-1973 Through 22-06-1973",

}

TY - CONF

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

AU - Boesch, F. T.

AU - Chen, S.

AU - McHugh, J. A.M.

PY - 1974

Y1 - 1974

N2 - 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 .

AB - 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 .

UR - http://www.scopus.com/inward/record.url?scp=0016141284&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0016141284&partnerID=8YFLogxK

U2 - 10.1007/bfb0066442

DO - 10.1007/bfb0066442

M3 - Paper

AN - SCOPUS:0016141284

SP - 201

EP - 212

T2 - Cap Conf on Graph Theory and Comb, Proc, Graphs and Comb

Y2 - 18 June 1973 through 22 June 1973

ER -

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

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this