\(OC\)-Irredundance, \(CO\)-Irredundance and Maximum Degree in Trees

E.J. Cockayne1, J.S. Swarts1
1Department of Mathematics and Statistics University of Victoria P.O. Box 3045 STN CSC Victoria, BC Canada V8W 3P4

Abstract

A vertex subset \( X \) of a simple graph is called OC-irredundant (respectively CO-irredundant) if for each \( v \in X \), \( N(v) – N[X – \{v\}] \neq \emptyset \) (respectively \( N[v] – N(X – \{v\}) \neq \emptyset \)). Sharp bounds involving order and maximum degree for the minimum cardinality of a maximal OC-irredundant set and a maximal CO-irredundant set of a tree are obtained, and extremal trees are exhibited.

Keywords: OC-irredundance; CO-irredundance, OO-irredundant AMS Subject Classification Number 2000: 05C69, 05C78.