Gated independence in graphs.

If G = (V , E) is a (finite and simple) graph, we call an independent set X a gated independent set in G if for each x ∈ X , there exists a neighbor y of x such that (X ∖ { x }) ∪ { y } is an independent set in G. We define the gated independence number gi (G) of G to be the maximum cardinality of a gated independent set in G. We demonstrate that the gated independence number is closely related to both matching and domination parameters of graphs. We prove that the inequalities im (G) ⩽ gi (G) ⩽ m ur (G) hold for every graph G , where im (G) and m ur (G) denote the induced and uniquely restricted matching numbers of G. On the other hand, we show that γ i (G) ⩽ gi (G) and γ pr (G) ⩽ 2 gi (G) for every graph G without any isolated vertex, where γ i (G) and γ pr (G) denote the independence and paired domination numbers. Furthermore, we provide bounds on the gated independence number involving the order, size and maximum degree. In particular, we prove that gi (G) ⩾ n 5 for every n -vertex subcubic graph G without any isolated vertex or any component isomorphic to K 3 , 3 , and gi (B) ⩽ 3 n 8 for every n -vertex connected cubic bipartite graph B. [ABSTRACT FROM AUTHOR]