Article

GENERALISED MAXIMAL INDEPENDENCE PARAMETERS FOR PATHS AND CYCLES

Published in: Quaestiones Mathematicae
Volume 13 , issue 2 , 1990 , pages: 123–139

DOI: 10.1080/16073606.1990.9631607

Author(s): E. J. Cockayne Department of Mathematics, CANADA , G. MacGillivray Department of Mathematics, CANADA , C. M. Mynhardt Department of Mathematics Applied Mathematics and Astronomy, REPUBLIC OF SOUTH AFRICA

Keywords: 05C38 , 05C99

Download full text Get new issue alerts

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but the deletion of any l-subset X from B (where l ≤ k—1) followed by the addition of any l + 1 vertices from V—B, produces a dependent set. We calculate the smallest cardinality of a kMIS for paths and cycles, and obtain Nordhaus-Gaddum type results for these parameters for graphs in general.

« EDITORIAL BOARD / REDAKSIERAAD

THE IRREDUNDANT RAMSEY NUMBER s(3,6) »