A unified approach to domination problems on interval graphs. (English) Zbl 0658.05040

A subset D of the vertex set V(G) of a graph G is called dominating (or total dominating) in G, if for each vertex \(x\in V(G)-D\) (or for each vertex \(x\in V(G)\) respectively) there exists a vertex \(y\in D\) adjacent to x. A dominating set of G which induces a connected subgraph of G is called connected. Also independent dominating sets are considered. The mentioned concepts are studied for interval graphs, i.e. intersection graphs of families of intervals on a real line. Some recurrence relations for various types of dominating sets in interval graphs are stated. These relations lead to linear-time algorithms for the weighted version of the various dominating problems in a unified way.
Reviewer: B.Zelinka


05C35 Extremal problems in graph theory
05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Bertossi, A.A., Total domination in interval graphs, Inform. process. lett., 23, 131-134, (1986) · Zbl 0604.05032
[2] Booth, K.S.; Johnson, J.H., Dominating sets in chordal graphs, SIAM J. comput., 11, 191-199, (1982) · Zbl 0485.05055
[3] Booth, K.S.; Lueker, G.S., Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. comput. system sci., 13, 335-379, (1976) · Zbl 0367.68034
[4] Farber, M., Domination, independent domination, and duality in strongly chordal graphs, Discrete appl. math., 7, 115-130, (1984) · Zbl 0531.05045
[5] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[6] Keil, J.M., Total domination in interval graphs, Inform. process. lett., 22, 171-174, (1986) · Zbl 0595.05063
[7] Laskar, R.; Pfaff, J.; Hedetniemi, S.M.; Hedetniemi, S.T., On the algorithmic complexity of total domination, SIAM J. alg. disc. meth., 5, 420-425, (1984) · Zbl 0576.68056
[8] White, K.; Farber, M.; Pulleyblank, W., Steiner trees, connected domination and strongly chordal graphs, Networks, 15, 109-124, (1985) · Zbl 0579.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.