|
Title:
|
On k-domination and j-independence in graphs
|
|
Author:
|
Hansberg Pastor, Adriana; Pepper, Ryan
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
|
Abstract:
|
Let GG be a graph and let kk and jj be positive integers. A subset DD of the vertex set of GG is a kk-dominating set if every vertex not in DD has at least kk neighbors in DD. The kk-domination numberγk(G)γk(G) is the cardinality of a smallest kk-dominating set of GG. A subset I⊆V(G)I⊆V(G) is a jj-independent set of GG if every vertex in II has at most j−1j−1 neighbors in II. The jj-independence numberαj(G)αj(G) is the cardinality of a largest jj-independent set of GG. In this work, we study the interaction between γk(G)γk(G) and αj(G)αj(G) in a graph GG. Hereby, we generalize some known inequalities concerning these parameters and put into relation different known and new bounds on kk-domination and jj-independence. Finally, we will discuss several consequences that follow from the given relations, while always highlighting the symmetry that exists between these two graph invariants. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta
-Domination (Graph theory)
-kk-domination
-jj-independence
-Domination
-Independence
-Dominació (Grafs, Teoria de) |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Article |
|
Share:
|
|
