research-article
Authors: Valentin Bouquet, François Delbot, Christophe Picouleau, and Stéphane Rovedakis
Volume 1001, Issue C
Published: 17 July 2024 Publication History
- 0citation
- 0
- Downloads
Metrics
Total Citations0Total Downloads0Last 12 Months0
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
- View Options
- References
- Media
- Tables
- Share
Abstract
A set S ⊆ V of a graph G = ( V, E ) is a dominating set if each vertex has a neighbor in S or belongs to S. Dominating Set is the problem of deciding, given a graph G and an integer k ≥ 1, if G has a dominating set of size at most k. It is well known that this problem is NP-complete even for claw-free graphs. We give a (almost) complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter d. We show that the problem is NP-complete for every fixed d ≥ 3 and polynomial-time solvable for d ≤ 2. To prove the case d = 2, we show that Minimum Maximal Matching can be solved in polynomial-time for 2 K 2-free graphs.
References
[1]
J.A. Bondy, U.S.R. Murty, Graphs Theory, Springer, 2008.
[2]
A. Brandstädt, V.B. Le, J. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.
[3]
S. Dhanalakshmi, N. Sadagopan, V. Manogna, On 2 K 2-free graphs, Int. J. Pure Appl. Math. 109 (7) (2016) 167–173.
[4]
M. Farber, On diameters and radii of bridged graphs, Discrete Math. 73 (3) (1989) 249–260.
[5]
M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
Digital Library
[6]
T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc., 1998.
[7]
D. Hermelin, M. Mnich, E. Jan Van Leeuven, G. Woeginger, Domination when the stars are out, ACM Trans. Algorithms 15 (2) (2019) 1–90.
[8]
W.-L. Hsu, K.-H. Tsai, Linear time algorithms on circular-arc graphs, Inf. Process. Lett. 40 (1991) 123–129.
[9]
T. Kikuno, N. Yoshida, Y. Kakuda, The NP-completeness of the dominating set problem in cubic planer graphs, IEICE Trans. 6 (1980) 443–444.
[10]
A. King, B. Reed, Bounding χ in terms of ω and δ for quasi-line graphs, J. Graphs Theory 59 (2008) 215–228.
[11]
P.G.H. Lehot, An optimal algorithm to detect a line graph and output its root graph, J. ACM 21 (1974) 569–575.
[12]
D. Lokshtanov, N. Misra, G. Philip, M.S. Ramanujan, S. Saurabh, Hardness of r-dominating set on graphs of diameter ( r + 1 ), in: International Symposium on Parameterized and Exact Computation, in: LNCS, vol. 8246, 2013, pp. 255–267.
[13]
B. Martin, D. Paulusma, E.J. van Leeuwen, Disconnected cuts in claw-free graphs, J. Comput. Syst. Sci. 113 (2020) 60–75.
[14]
M. Yannakakis, F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38 (3) (1980) 364–372.
Digital Library
Recommendations
- Dominating set is fixed parameter tractable in claw-free graphs
We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K"1","3, the complete bipartite graph on four vertices where the two parts have one and three vertices, ...
Read More
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a ...
Read More
- On s-hamiltonian line graphs of claw-free graphs
Abstract
For an integer s ≥ 0, a graph G is s-hamiltonian if for any vertex subset S ⊆ V ( G ) with | S | ≤ s, G − S is hamiltonian, and G is s-hamiltonian connected if for any vertex subset S ⊆ V ( G ) with | S | ≤ s, G − S is hamiltonian ...
Read More
Comments
Information & Contributors
Information
Published In
Theoretical Computer Science Volume 1001, Issue C
Jun 2024
111 pages
ISSN:0304-3975
Issue’s Table of Contents
Elsevier B.V.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 17 July 2024
Author Tags
- Minimum dominating set
- Minimum maximal matching
- Diameter
- Claw-free graphs
- Line graphs
- 2 K 2-free
- Complexity
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Other Metrics
View Author Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
Media
Figures
Other
Tables
