Secondary and Internal Distances of Sets in Graphs II

Abstract

For any given type of a set of vertices in a connected graph G = (V, E), we seek to determine the smallest integers (x, y: z) such that for all minimal (or maximal) sets S of the given type, where |V| > |S| ≥ 2, every vertex v ∊ V - S is within shortest distance at most x to a vertex u ∊ S (called dominating distance), and within distance at most y to a second vertex w ∊ S (called secondary distance). We also seek to determine the smallest integer z such that every vertex u ∊ S is within distance at most z to a closest neighbor w ∊ S (called internal distance). In this paper, a sequel to two previous papers [21, 18], we determine the secondary and internal distances (2, y: z) for 16 types of sets, all of which are distance-2 dominating sets, that is, whose dominating distances are at most 2.

Keywords:

• distance-2 domination
• 2-packings
• irredundant sets
• induced matching
• acyclic matching
• disconnected matching

2010 Mathematics Subject Classification:

• 05C69
• 05C70