New upper bounds for the pseudoachromatic and upper irredundance numbers of a graph
Abstract
Let G = (V,E) be a graph having order n = \V\ vertices. The closed neighborhood of a vertex v ∈ V is the set N[ν] = {u ∈ V\uν ∈ E} U {ν}, and the closed neighborhood of a set S ⊂ V is the set N[S] = Uν∈SN[ν]-A partition π = {V1V 2..Vκ} of the vertex set V is called a complete partition if for every 1 < i < j < κ there exists a vertex u ∈ Vi; that is adjacent to a vertex v € Vj. The maximum order of a complete partition of a graph G is called the pseudoachromatic number Ψs(G) of G. The upper irredundance number IR(G) equals the maximum order of a set S ⊂ V having the property that for every vertex v ∈ S, N[ν] - N[S - {ν}] ≠ φ. In this paper we discuss a variant of an old method that can be used to prove a variety of new results like the following: for any graph G of order n > 2, IR(G) + Ψs(G) < n + 1.
