On 3-Distance Independent Sets of Graphs.

Abstract

Let G be a graph with vertex set V(G) and edge set E(G). A set S \subseteq V(G) is a 3-distance independent set of G if d_G(v,w) \neq 3 for any two distinct vertices v,w \in S. The maximum cardinality of a 3-distance independent set of G, denoted by \alpha^3(G), is called the 3-distance independence number of G. In this paper, we establish basic bounds for \alpha^3(G), we characterize the graphs for which \alpha^3(G) attains its extreme values, and we introduce the outer 3-distance independent vertex cover of a graph, obtaining a lower bound for its cardinality in terms of \alpha^3(G).