JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (12): 130-136.doi: 10.6040/j.issn.1671-9352.0.2014.567

Previous Articles    

Solving the algebraic model of k-dominating sets of graph by Grbner basis

YIN Jie-jie   

  1. Department of Applied Mathematics of Information and Technology College, Hainan University, Haikou 570228, Hainan, China
  • Received:2014-12-22 Revised:2015-11-18 Online:2015-12-20 Published:2015-12-23

PDF (PC)

794

Abstract: Let G be a simple connected graph of n vertices. It is shown that finding all dominating sets of G is equivalent to finding all 0-1 solutions of a system of multivariate polynomial equations; furthermore, it is shown that this polynomial equation model can be modified to give a polynomial equation model for finding dominating sets of k vertices (i.e. k-dominating sets) of G, and that such a model can be solved by using the Grbner basis method. Consequently, a feasible way of finding minimal dominating sets and the dominating number of G is obtained. The numerical example is presented to illustrate the effectiveness of this algebraic computational method.

Key words: k-dominating set, Grbner basis, minimal dominating set, dominating number, Graph

CLC Number: 

  • O157. 5
[1] ADAMS W, LOUSTAUNAUS P. An introduction to Grbner bases[M]. Washington, D C: American Mathematical Society, 1994:118-276.
[2] Sk Md Abu Nayeem, PAL Madhumangal. Genetic algorithmic approach to find the maximum weight independent set of a graph[J]. Journal of Applied Mathematics and Computing, 2007, 25(1):217-219.
[3] 熊雪玮,赵志琴. 图的k-独立集与Grbner 基求解[J].工程数学学报,2012, 29(5):696-702. XIONG Xuewei, ZHAO Zhiqing. Solving the k-independent sets of graph by Grbner basis[J]. Chinese Journal Engineering Mathematics, 2012, 29(5):696-702.
[4] 熊雪玮.几个图论问题的多项式建模与Grbner 基求解[M]. 海口:海南大学出版社,2012. XIONG Xuewei. The polynomial modeling and Grbner basis solving of several problems in graph theory[M]. Haikou: Hainan University Press, 2012.
[5] MARGULIES S, HICKS I V. An algebraic exploration of dominating sets and Vizing's conjecture[J]. The Electronic Journal of Combinatorics, 2012, 19(2):1-30.
[6] MNUK M. Representing graph properties by polynomial ideals[M]. New York: Computer Algebra in Scientific Computing, 2001:431-444.
[7] BONDY J A, MURTY U S R. Graph theory [M]. Berlin: Springer, 2008: 78-156.
[8] 殷剑宏,吴开亚. 图论及其算法[M]. 合肥:中国科学技术大学出版社,2003:179-185. YIN Jianhong,WU Kaiya. Graph theory and algorithms[M]. Hefei:University of Science and Technology of China Press, 2003:179-185.
[1] YE Xiao-ming, CHEN Xing-shu, YANG Li, WANG Wen-xian, ZHU Yi, SHAO Guo-lin, LIANG Gang. Anomaly detection model of host group based on graph-evolution events [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 1-11.
[2] . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60.
[3] LIU Xiao-hua, MA Hai-cheng. Order of matching energy and Hosoya index of Q-shape graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 61-65.
[4] CUI Zhao-yang, SUN Jia-qi, XU Song-yan, JIANG Xin. A secure clustering algorithm of Ad Hoc network for colony UAVs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 51-59.
[5] GAO Rui-mei, CHU Ying. Freeness of arrangements between the Weyl arrangements of types An-1 and Bn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 70-75.
[6] LI Mei-lian, DENG Qing-ying. Maple calculation of the transition polynomial of plane graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 27-34.
[7] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35-41.
[8] KANG Hai-yan, HUANG Yu-xuan, CHEN Chu-qiao. Enhancing privacy for geographic information based on video analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 19-29.
[9] . Graph model based trustworthy resource scheduling algorithm in cloud environment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 63-74.
[10] DAI Hong-xiu, WANG Nan, AIMAIER·Aikebaijiang, LIN Meng. Preparation of the GO/PPy/Pb3O4 modified electrode for electrochemical sensing application [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(9): 98-102.
[11] WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106.
[12] PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.
[13] ZHANG Cong, PEI Jia-huan, HUANG Kai-yu, HUANG De-gen, YIN Zhang-zhi. Semantic graph optimization algorithm based chinesemicroblog opinion summarization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(7): 59-65.
[14] SU Yang. Reconfigurable design of Galois field multiplication in symmetric cryptography [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(6): 76-83.
[15] CHEN Xiang-en, MIAO Ting-ting, WANG Zhi-wen. Vertex-distinguishing I-total colorings of the join of two paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 30-33.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd