On Computational and Combinatorial Properties of the Total Co-independent Domination Number of Graphs. (13th April 2018)

• Record Type: Journal Article
• Authors: Cabrera Martínez, Abel; Hernández Mira, Frank A; Sigarreta Almira, José M; Yero, Ismael G
• Editors: Paulusma, Daniel
• Is Part Of: Computer journal. Volume 62:Number 1(2019)
• Page Start: 97
• Page End: 108
• Publication Date: 2018-04-13
• Subjects: total co-independent domination -- total domination -- vertex independence -- vertex cover; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy038
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: A subset D of vertices of a graph G is a total dominating set if every vertex of G is adjacent to at least one vertex of D . The total dominating set D is called a total co-independent dominating set if the subgraph induced by V − D is edgeless and has at least one vertex. The minimum cardinality of any total co-independent dominating set is the total co-independent domination number of G and is denoted by γ t, c o i ( G ) . In this work we study some complexity and combinatorial properties of γ t, c o i ( G ) . Specifically, we prove that deciding whether γ t, c o i ( G ) ≤ k for a given integer k is an NP-complete problem and give several bounds on γ t, c o i ( G ) . Moreover, since any total co-independent dominating set is a total dominating set, we characterize all the trees having equal total co-independent domination number and total domination number.