Total domination in interval graphs

DOI10.1016/0020-0190(86)90022-0zbMath0595.05063MaRDI QIDQ5903156

J. Mark Keil

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90022-0

zbMATH Keywords

interval graph; total domination; total dominating set; linear algorithm

Mathematics Subject Classification ID

05C99: Graph theory

Related Items

Bibliography on domination in graphs and some basic definitions of domination parameters, A survey of selected recent results on total domination in graphs, Finding the minimum bandwidth of an interval graph, A unified approach to domination problems on interval graphs, Total domination in interval graphs revisited, Labeling algorithms for domination problems in sun-free chordal graphs, Total domination in block graphs, Dominating sets in perfect graphs, The bottleneck independent domination on the classes of bipartite graphs and block graphs., Achromatic number is NP-complete for cographs and interval graphs, Weighted independent perfect domination on cocomparability graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Finding Hamiltonian circuits in interval graphs
• Clustering and domination in perfect graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A linear algorithm for the domination number of a series-parallel graph
• Representation of a finite graph by a set of intervals on the real line
• On the Algorithmic Complexity of Total Domination
• Domination in permutation graphs
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Dominating Sets in Chordal Graphs
• A Characterization of Comparability Graphs and of Interval Graphs