Gated independence in graphs
Küçük Resim Yok
Tarih
2024
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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 is an element of X , there exists a neighbor y of x such that ( X \ { x } ) boolean OR{ 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 gamma i ( G ) gi( G ) and gamma p r ( G ) 2 gi( G ) for every graph G without any isolated vertex, where gamma i ( G ) and gamma p r ( 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 ) 5 n 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 . (c) 2024 Elsevier B.V. All rights reserved.
Açıklama
Anahtar Kelimeler
Induced matching, Uniquely restricted matching, Gated independent set, Domination, Lower Bounds
Kaynak
Discrete Applied Mathematics
WoS Q Değeri
N/A
Scopus Q Değeri
Q2
Cilt
353
