Vol. 58, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Subscriptions
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Author Index
To Appear
 
Other MSP Journals
Covering the vertices of a graph by vertex-disjoint paths

Shahbaz Noorvash

Vol. 58 (1975), No. 1, 159–168
Abstract

Define the path-covering number μ(G) of a finite graph G to be the minimum number of vertex-disjoint paths required to cover the vertices of G. Let g(n,k) be the minimum integer so that every graph, G, with n vertices and at least g(n,k) edges has μ(G) k. A relationship between μ(G) and the degree sequence for a graph G is found; this is used to show that

1(n− k)(n− k − 1) +1 ≦ g(n,k) ≦ 1(n − 1)(n − k− 1)+ 1
2                             2

A further extremal problem is solved.

Mathematical Subject Classification 2000
Primary: 05C35
Milestones
Received: 30 November 1973
Published: 1 May 1975
Authors
Shahbaz Noorvash