Complexity Issues of Bi-efficient Domination in Certain Classes of Graphs
In a graph [Formula: see text], a dominating set [Formula: see text] is a bi-efficient dominating set of [Formula: see text], if for every vertex [Formula: see text] in [Formula: see text], [Formula: see text]. The bi-efficient domination number of [Formula: see text], denoted by [Formula: see text] is the minimum cardinality of a bi-efficient dominating set of [Formula: see text], if it exists. In this paper, many bounds of [Formula: see text] are obtained and its relationship with other parameters are investigated. The complexity of the problem is studied for bipartite and chordal graphs. An algorithm has been designed to find bi-efficient domination number of trees and unicyclic graphs. Further, the problem is shown to be fixed-parameter tractable when parameterized by treewidth of the input graph.
Authors
- K. Venugopal
- K. A. Vidya
- Basavaraju Chaluvaraju (ORCID: https://orcid.org/0000-0002-4697-0059)
Institutions
- Twitter (United States) (US)
Publication Details
- Journal
- Discrete Mathematics Algorithms and Applications
- Published
- 2026-11-19
- DOI
- https://doi.org/10.1142/s1793830926501168
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00