Vol. 58, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Vol. 320: 1  2
Vol. 319: 1  2
Vol. 318: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
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