Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T06:49:23.005Z Has data issue: false hasContentIssue false
  • English
  • Français

Irredundance and Maximum Degree in Graphs

Published online by Cambridge University Press:  01 June 1997

E. J. COCKAYNE  and
C. M. MYNHARDT
E. J. COCKAYNE
Affiliation:
University of Victoria, BC, Canada
C. M. MYNHARDT
Affiliation:
Department of Mathematics, University of South Africa, P. O. Box 392, Pretoria 0001, South Africa (e-mail: mynhacm@alpha.unisa.ac.za)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

It is proved that the smallest cardinality among the maximal irredundant sets in an n–vertex graph with maximum degree Δ([ges ]2) is at least 2n/3Δ. This substantially improves a bound by Bollobás and Cockayne [1]. The class of graphs which attain this bound is characterised.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 2 , June 1997 , pp. 153 - 157
Copyright
1997 Cambridge University Press