To access the full text documents, please follow this link: http://hdl.handle.net/2117/86561

Perfect and quasiperfect domination in trees
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, Maria Luz
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
A k quasip erfect dominating set of a connected graph G is a vertex subset S such that every vertex not in S is adjacent to at least one and at most k vertices in S . The cardinality of a minimum k-quasip erfect dominating set in G is denoted by 1 k ( G ) . These graph parameters were rst intro duced by Chellali et al. (2013) as a generalization of b oth the p erfect domination numb er 11 ( G ) and the domination numb er ( G ) . The study of the so-called quasip erfect domination chain 11 ( G ) 12 ( G ) 1 ( G ) = ( G ) enable us to analyze how far minimum dominating sets are from b eing p erfect. In this pap er, we provide, for any tree T and any p ositive integer k , a tight upp er b ound of 1 k ( T ) . We also prove that there are trees satisfying all p ossible equalities and inequalities in this chain. Finally a linear algorithm for computing 1 k ( T ) in any tree T is presente
Àrees temàtiques de la UPC::Matemàtiques i estadística
Graph theory
Grafs, Teoria de
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, Maria Luz
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M Luz
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M. Luz
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M. Luz
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas González, María Luz
 

Coordination

 

Supporters