2017/05/02 by Abel Cabrera Martínez, Frank A. Hernández Mira, Martinez, Abel Cabrera +5
Computer Science · Engineering · #Advanced Graph Theory Research #Interconnection Networks and Systems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1705.01036
A subset D of vertices of a graph G is a total dominating set if every\nvertex of G is adjacent to at least one vertex of D. The total dominating\nset D is called a total co-independent dominating set if the subgraph induced\nby V-D is edgeless and has at least one vertex. The minimum cardinality of\nany total co-independent dominating set is the total co-independent domination\nnumber of G and is denoted by \γt,coi(G). In this work we study some\ncomplexity and combinatorial properties of \γt,coi(G). Specifically,\nwe prove that deciding whether \γt,coi(G)\≤ k for a given integer k\nis an NP-complete problem and give several bounds on \γt,coi(G). Also,\nsince any total co-independent dominating set is also a total dominating set,\nwe characterize all the trees having equal total co-independent domination\nnumber and total domination number.\n