On independence domination

DOI10.1007/978-3-642-40164-0_19MaRDI QIDQ2842784zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Sheung-Hung Poon, Yue-Li Wang

Publication date 16 August 2013

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.6450

zbMATH Keywords

cographdistance-hereditary graphdominationexact algorithmindependence dominationpermutation graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: Let G be a graph. The independence-domination number is the maximum over all independent sets I in G of the minimal number of vertices needed to dominate I. In this paper we investigate the computational complexity of independence domination for graphs in several graph classes related to cographs. We present an exact exponential algorithm. We also present a PTAS for planar graphs.

Recommendations

• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Results on independent sets in categorical products of graphs, the ultimate categorical independence ratio and the ultimate categorical independent domination ratio
• Independent domination in finitely defined classes of graphs
• Independent Domination in Triangle Graphs
• Independent domination and matchings in graphs

Cited in

(6)

• On Kim-independence
• A remark on strict independence relations
• A Note on the Concept of Independence
• Strong triadic closure in cographs and graphs of low maximum degree
• Background independence: lessons for further decades of dispute
• Mind the independence gap

This page was built for publication: On independence domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842784)