article

Free access

R-Domination in Graphs

Author:

Peter J. SlaterAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 3

Pages 446 - 450

https://doi.org/10.1145/321958.321964

Published: 01 July 1976 Publication History

PDF eReader

Abstract

The problem of finding a minimum k-basis of graph G is that of selecting as small a set B of vertices as possible such that every vertex of G is at distance k or less from some vertex in B. Cockayne, Goodman, and Hedetniemi previously developed a linear algorithm to find a minimum 1-basis (a minimum dominating set) when G is a tree. In this paper the k-basis problem is placed in a more general setting, and a linear algorithm is presented that solves the problem for any forest.

References

[1]

COCKAYNE, E J, GOODMAN, S E, AND HEDETNIEMI, S T A hnear algomthm for the dommatmn number of a tree Submitted for pubhcatlon

Google Scholar

[2]

COCKAYNE, E J, AND HEDETNIEMI, S T Dominating part~tmns of graphs To appear

Google Scholar

[3]

LIU, C Introductmn to Comb~natorml Mathematics McGraw-Hill, New York, 1968

Google Scholar

[4]

MATULA, D W, AND KOLDE, R A Multiple faclhtms location-allocation m certain sparse networks (abstract) SIAM Rev 14 (1972), 533-534

Google Scholar

[5]

ORE, O Theory of Graphs Amer Math Soc Colloqumm Pub, Vol XXXVIII, Amer Math Soc, Providence, Rhode Island, 1962

Google Scholar

Cited By

View all

Samanta Adhya AMondal SCharan Barman S(2023)Edge-vertex domination on interval graphsDiscrete Mathematics, Algorithms and Applications10.1142/S179383092350015516:02Online publication date: 28-Mar-2023
https://doi.org/10.1142/S1793830923500155
He XYesha Y(2023)Efficient parallel algorithms forr-dominating set andp-center problems on treesAlgorithmica10.1007/BF018403815:1-4(129-145)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840381
Mizutani YStaker ASullivan BZhang ARangwala H(2022)Minimizing Congestion for Balanced DominatorsProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539371(1264-1274)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539371
Show More Cited By

Index Terms

R-Domination in Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Paired versus double domination in K1,r-free graphs

A vertex in G is said to dominate itself and its neighbors. A subset S of vertices is a dominating set if S dominates every vertex of G . A paired-dominating set is a dominating set whose induced subgraph contains a perfect matching. The paired-...
k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k ...
Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Let G=(V,E) be a graph. A set S@__ __V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S@__ __V is a restrained dominating set if every vertex in V-S is ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 23, Issue 3

July 1976

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321958

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in JACM Volume 23, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
975
Total Downloads

Downloads (Last 12 months)110
Downloads (Last 6 weeks)9

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Samanta Adhya AMondal SCharan Barman S(2023)Edge-vertex domination on interval graphsDiscrete Mathematics, Algorithms and Applications10.1142/S179383092350015516:02Online publication date: 28-Mar-2023
https://doi.org/10.1142/S1793830923500155
He XYesha Y(2023)Efficient parallel algorithms forr-dominating set andp-center problems on treesAlgorithmica10.1007/BF018403815:1-4(129-145)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF01840381
Mizutani YStaker ASullivan BZhang ARangwala H(2022)Minimizing Congestion for Balanced DominatorsProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539371(1264-1274)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539371
Abu-Affash ACarmi PKrasin A(2022) A linear-time algorithm for minimum -hop dominating set of a cactus graph Discrete Applied Mathematics10.1016/j.dam.2022.06.006320(488-499)Online publication date: Oct-2022
https://doi.org/10.1016/j.dam.2022.06.006
Alagarsamy AMahilmaran SGopalakrishnan LKo S(2022)SaHNoC: an optimal energy efficient hybrid networks-on-chip architectureThe Journal of Supercomputing10.1007/s11227-022-04910-979:6(6538-6559)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/s11227-022-04910-9
Carević M(2021)Dominating Number on Icosahedral-Hexagonal NetworkMathematical Problems in Engineering10.1155/2021/66633892021(1-8)Online publication date: 10-Apr-2021
https://doi.org/10.1155/2021/6663389
Biedl TMehrabi S(2021)On Orthogonally Guarding Orthogonal Polygons with Bounded TreewidthAlgorithmica10.1007/s00453-020-00769-583:2(641-666)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s00453-020-00769-5
Pandiaraja DShanmugam ESivakumar R(2020)Linear programming formulation for some generalized domination parametersDiscrete Mathematics, Algorithms and Applications10.1142/S179383092150044013:04(2150044)Online publication date: 5-Dec-2020
https://doi.org/10.1142/S1793830921500440
Samanta Adhya AMondal SBarman S(2020) An Optimal Algorithm to Find Minimum k -hop Connected Dominating Set of Permutation Graphs Asian-European Journal of Mathematics10.1142/S1793557121500492Online publication date: 27-Feb-2020
https://doi.org/10.1142/S1793557121500492
Habibulla Y(2020)Statistical mechanics of the directed 2-distance minimal dominating set problemCommunications in Theoretical Physics10.1088/1572-9494/aba24972:9(095602)Online publication date: 27-Aug-2020
https://doi.org/10.1088/1572-9494/aba249
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Paired versus double domination in K1,r-free graphs

k-tuple domination in graphs

Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations