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

Quasiperfect domination in trees
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M. 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–quasiperfect dominating set ( k=1k=1) of a 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–quasiperfect dominating set of G is denoted by ¿1k(G)¿1k(G). Those sets were first introduced by Chellali et al. (2013) as a generalization of the perfect domination concept (which coincides with the case k=1k=1) and allow us to construct a decreasing chain of quasiperfect dominating parameters ¿11(G)=¿12(G)=…=¿1,¿(G)=¿(G),¿11(G)=¿12(G)=…=¿1,¿(G)=¿(G), (1) in order to indicate how far is G from being perfectly dominated. In this work, we study general properties, tight bounds, existence and realization results involving the parameters of the so-called QP-chain ( 1), for trees.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística
Graph theory
Domination
Perfect domination
Quasiperfect domination
Trees
Grafs, Teoria de
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/submittedVersion
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, M. Luz
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M. Luz
Cáceres, Jose; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M. Luz
Cáceres, Jose; Puertas, M. Luz; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel
Cáceres, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas, M Luz
 

Coordination

 

Supporters