Article
Mathematics
Sakander Hayat, Asad Khan, Yubin Zhong
Summary: This paper points out an error in the proof of a graph characterization and provides complete multipartite graphs as counterexamples. Furthermore, it finds several metric values for complete multipartite graphs and generalizes existing results from complete bipartite to complete multipartite graphs.
Article
Multidisciplinary Sciences
Yongsheng Rao, Ruiqi Cai, Ali Asghar Talebi, Masomeh Mojahedfar
Summary: This paper focuses on the study of double domination in vague graphs, making contributions to the field of graph theory and the symmetry/asymmetry of symmetry. Symmetry, an important criterion in fuzzy graphs, has applications in dominating sets and construction placement. The concept of energy is introduced in this work to model problems related to dominating vague graphs (DVGs) and a new notion of double dominating vague graphs (DDVGs) is proposed with examples provided. Additionally, an application of energy on DVGs is presented.
Article
Mathematics, Applied
Shao-Liang Chen, Rong-Xia Hao, Xiao-Wen Qin
Summary: This paper introduces the concepts of connected dominating sets and their connected domination numbers in graphs, and proposes an algorithm for finding connected dominating sets in maximal outerplanar graphs. An upper bound for the connected domination number of maximal outerplanar graphs is obtained through this algorithm. Additionally, the advantages of the results are evaluated through simulations.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Mathematics
Yongsheng Rao, Ruxian Chen, Pu Wu, Huiqin Jiang, Saeed Kosari
Summary: Fuzzy graph algorithms are used to model and solve practical problems, with a wide range of applications. Fuzzy graph theory may not successfully handle all uncertainties. Many research studies are exploring other applications for domination theory in various fields.
Article
Mathematics, Applied
Zongpeng Ding, Yuanqiu Huang, Licheng Zhang
Summary: In this paper, a complete characterization of a maximal 1-plane graph G is provided for values of k between 3 and 6. Moreover, it is proven that G has at least 25n-4 edges for k=2, and this bound is tight. Finally, it is shown that G has at least 73n-103 edges for k=1. These results also resolve an open problem posed by Ouyang et al. in 2019.
APPLIED MATHEMATICS AND COMPUTATION
(2023)
Letter
Mathematics
Landon Rabern
Summary: We provide a concise inductive proof of Brooks' Theorem.
DISCRETE MATHEMATICS
(2023)
Article
Computer Science, Interdisciplinary Applications
Shu-Yu Cui, Yiqiao Wang, Danjun Huang, Hongwei Du, Weifan Wang
Summary: This paper investigates the structural characterization of non-universal maximal planar graph with diameter two, identifying 10 basic graphs to generate all 25 non-universal maximal planar graphs. Additionally, it shows that maximal planar graphs with diameter two are pancyclic, except for five special cases.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Review
Mathematics
Yamuna Manimuthu, Karthika Kumarasamy
Summary: This survey presents a collection of results on characterizing trees using domination number, highlighting the importance of this field in graph domination.
Article
Physics, Multidisciplinary
Xiaolong Shi, Saeed Kosari
Summary: Product vague graph (PVG) is a significant issue in fuzzy graph theory, with applications in the medical sciences. This study introduces new concepts and properties related to domination in PVGs, and proposes an implementation of dominating sets in medicine related to the COVID-19 pandemic.
FRONTIERS IN PHYSICS
(2021)
Article
Computer Science, Artificial Intelligence
Necla Kircali Gursoy, Alper Ulker, Arif Gursoy
Summary: This paper examines the independent domination polynomials of zero-divisor graphs of the ring Z(n) and their properties.
Article
Computer Science, Interdisciplinary Applications
Lihe Guan, Hong Wang
Summary: This paper introduces rough set theory to solve the minimum dominating set problem of undirected graphs. By establishing an induced decision table and defining the significance of attributes based on rough set theory, a heuristic approximation algorithm is designed to improve the approximation accuracy of the minimum dominating set. The use of a cumulative strategy also helps reduce computational complexity.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Mathematics, Applied
Sangram K. Jena, Gautam K. Das
Summary: This study examines the vertex-edge domination problem in unit disk graphs and proves that the decision version of the problem belongs to the NP-complete class. It also presents a simple polynomial-time 4-factor approximation algorithm and a polynomial-time approximation scheme (PTAS) for the problem in unit disk graphs.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Information Systems
Jingwei Xie, Yong Chen, An Zhang, Guangting Chen
Summary: This paper studies the problem of partitioning a given graph into three independent sets with minimizing the maximum one. The problem is proven to be NP-hard, even for bipartite graphs. A simple 3/2-approximation algorithm is presented for any 2-colorable graph, followed by an improved 75-approximation algorithm for trees. The theoretical proof of the improved algorithm provides an explicit partition approach for each case based on the cardinality of two color classes.
TSINGHUA SCIENCE AND TECHNOLOGY
(2023)
Article
Computer Science, Information Systems
Yun Peng, Xin Lin, Byron Choi, Bingsheng He
Summary: Graph coloring has broad applications in various fields, and our VColor and VColor* approaches address efficiency challenges in graph coloring. VColor* demonstrates superior efficiency compared to VColor in experimental evaluations.
FRONTIERS OF COMPUTER SCIENCE
(2021)
Article
Mathematics
Enrico Enriquez, Grace Estrada, Carmelita Loquias, Reuella J. Bacalso, Lanndon Ocampo
Summary: This paper introduces the concept of domination in a fuzzy digraph, characterizes the domination number of a fuzzy digraph, and models the domination number of a fuzzy dipath and a fuzzy dicycle.
