Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs

Chuan-Min Lee ()
Additional contact information
Chuan-Min Lee: Department of Applied Artificial Intelligence, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan

Mathematics, 2025, vol. 13, issue 3, 1-30

Abstract: Domination problems are fundamental problems in graph theory with diverse applications in optimization, network design, and computational complexity. This paper investigates { k } -domination, k -tuple domination, and their total domination variants in weighted strongly chordal graphs and chordal bipartite graphs. Specifically, the { k } -domination problem in weighted strongly chordal graphs and the total { k } -domination problem in weighted chordal bipartite graphs are shown to be solvable in O ( n + m ) time. For weighted proper interval graphs and convex bipartite graphs, we solve the k -tuple domination and total k -tuple domination problems in O ( n 2.371552 log 2 ( n ) log ( n / δ ) ) , where δ is the desired accuracy. Furthermore, for weighted unit interval graphs, the k -tuple domination problem achieves a significant complexity improvement, reduced from O ( n k + 2 ) to O ( n 2.371552 log 2 ( n ) log ( n / δ ) ) . These results are achieved through a combination of linear and integer programming techniques, complemented by totally balanced matrices, totally unimodular matrices, and graph-specific matrix representations such as neighborhood and closed neighborhood matrices.

Keywords: domination; total domination; { k }-domination; k -tuple domination; strongly chordal graph; chordal bipapartite graph; proper interval graph; convex bipartite graph; totally balanced matrix; totally unimodular matrix (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/3/403/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/3/403/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:3:p:403-:d:1577192

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().