Independent 2-point set domination in graphs with specified girth

Abstract

A set D of vertices in a connected graph G is said to be an independent 2-point set dominating set (or in short i-2psd set) of G if D is an independent set and for every subset [Formula: see text] there exists a non-empty subset [Formula: see text] containing at most 2 vertices such that the induced subgraph [Formula: see text] is connected. A graph which possesses an i-2psd set is called an i-2psd graph. Every finite graph need not be an i-2psd graph; for instance [Formula: see text]. In this paper we continue to explore graphs which possess an i-2psd set and discuss i-2psd graphs with specified girth. We exhibit a relation between diameter and girth of an i-2psd graph. We characterize extremal i-2psd graphs with maximum girth, and further present a partial characterization of i-2psd graphs with girth 5.

Keywords

• Independent set
• separable graphs
• Girth and circumference of graphs
• 2-point set domination in graphs
• generalised theta graph
• 05C69