Vol. 58, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
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