Next Article in Journal
Blockchain for Mass Customization: The Value of Information Sharing Through Data Accuracy by Contract Coordination
Previous Article in Journal
Ribbonness of a Stable-Ribbon Surface-Link, II: General Case
Previous Article in Special Issue
On Bridge Graphs with Local Antimagic Chromatic Number 3
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
This is an early access version, the complete PDF, HTML, and XML versions will be available soon.
Article

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

by
Chuan-Min Lee
Department of Applied Artificial Intelligence, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan
Mathematics 2025, 13(3), 403; https://doi.org/10.3390/math13030403
Submission received: 25 November 2024 / Revised: 8 January 2025 / Accepted: 24 January 2025 / Published: 25 January 2025
(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

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(n2.371552log2(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(nk+2) to O(n2.371552log2(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 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

Share and Cite

MDPI and ACS Style

Lee, C.-M. Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs. Mathematics 2025, 13, 403. https://doi.org/10.3390/math13030403

AMA Style

Lee C-M. Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs. Mathematics. 2025; 13(3):403. https://doi.org/10.3390/math13030403

Chicago/Turabian Style

Lee, Chuan-Min. 2025. "Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs" Mathematics 13, no. 3: 403. https://doi.org/10.3390/math13030403

APA Style

Lee, C.-M. (2025). Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs. Mathematics, 13(3), 403. https://doi.org/10.3390/math13030403

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop