In this paper,we consider the NP-hard problem offinding the minimum connected resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distanc...In this paper,we consider the NP-hard problem offinding the minimum connected resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the ver-tices in B.A resolving set B of G is connected if the subgraph B induced by B is a nontrivial connected subgraph of G.The cardinality of the minimal resolving set is the metric dimension of G and the cardinality of minimum connected resolving set is the connected metric dimension of G.The problem is solved heuristically by a binary version of an enhanced Harris Hawk Optimization(BEHHO)algorithm.This is thefirst attempt to determine the connected resolving set heuristically.BEHHO combines classical HHO with opposition-based learning,chaotic local search and is equipped with an S-shaped transfer function to convert the contin-uous variable into a binary one.The hawks of BEHHO are binary encoded and are used to represent which one of the vertices of a graph belongs to the connected resolving set.The feasibility is enforced by repairing hawks such that an addi-tional node selected from V\B is added to B up to obtain the connected resolving set.The proposed BEHHO algorithm is compared to binary Harris Hawk Optimi-zation(BHHO),binary opposition-based learning Harris Hawk Optimization(BOHHO),binary chaotic local search Harris Hawk Optimization(BCHHO)algorithms.Computational results confirm the superiority of the BEHHO for determining connected metric dimension.展开更多
A problem of the air pollution control in China is getting to know a regional contribution rate of internal and external source of PM2.5. In this paper,Set Pair Analysis( SPA) method is proposed to calculate the con...A problem of the air pollution control in China is getting to know a regional contribution rate of internal and external source of PM2.5. In this paper,Set Pair Analysis( SPA) method is proposed to calculate the contribution rate of PM2.5in Dongguan City. Due to geographic,meteorological factors and the low concentration of air pollutants in Qingxi area,the PM2.5in this place is mainly contributed by the regional transport of air pollutants from other inside areas of Dongguan,and less affected by the outside of Dongguan. So the concentration of PM2.5in Qingxi area can reflect the Dongguan's basic background concentration of PM2.5. On the basis of the basic background concentration,firstly the concentration of each pollutant components is divided into the internal part and the mixed part. Secondly using the source apportionment samples of five monitoring sites in Dongguan we can respectively construct a sample set A and an evaluation set B. Thirdly the SPA is operated onto the mixed part in terms of set B.At last the connection degree between the concentration of each pollutant components and external source and internal source will be calculated,that is the contribution rate. The research reveals that the contribution rate of internal source and external source of PM2.5in Dongguan City is 83%and 17% respectively,which roughly met expectations. This method is simple and effective and it can provide a reference for the government taking reduction measures to control PM2.5pollutants emission.展开更多
The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that...The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that every square of an n × n board is attacked? Beginning in 2005 with Amirabadi, Burchett, and Hedetniemi [2] [3], work on this problem, and two other related problems, has seen progress. Bounds have been given for the values of all three domination parameters on the queen’s graph. In this paper, formations of queens are given that provide new bounds for the values of total, paired, and connected domination on the queen’s graph, denoted , , and respectively. For any n × n board size, the new bound of is arrived at, along with the separate bounds of , for with , and , for with .展开更多
An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adj...An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least k. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ<sub>h</sub>k</sup> ( G )denote the least λ such that G admits an L(h,k) -labeling using labels from {0,1,...λ}. A Cayley graph of group is called circulant graph of order n, if the group is isomorphic to Z<sub>n.</sub> In this paper, initially we investigate the L(h,k) -labeling for circulant graphs with “large” connection sets, and then we extend our observation and find the span of L(h,k) -labeling for any circulants of order n. .展开更多
文摘In this paper,we consider the NP-hard problem offinding the minimum connected resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the ver-tices in B.A resolving set B of G is connected if the subgraph B induced by B is a nontrivial connected subgraph of G.The cardinality of the minimal resolving set is the metric dimension of G and the cardinality of minimum connected resolving set is the connected metric dimension of G.The problem is solved heuristically by a binary version of an enhanced Harris Hawk Optimization(BEHHO)algorithm.This is thefirst attempt to determine the connected resolving set heuristically.BEHHO combines classical HHO with opposition-based learning,chaotic local search and is equipped with an S-shaped transfer function to convert the contin-uous variable into a binary one.The hawks of BEHHO are binary encoded and are used to represent which one of the vertices of a graph belongs to the connected resolving set.The feasibility is enforced by repairing hawks such that an addi-tional node selected from V\B is added to B up to obtain the connected resolving set.The proposed BEHHO algorithm is compared to binary Harris Hawk Optimi-zation(BHHO),binary opposition-based learning Harris Hawk Optimization(BOHHO),binary chaotic local search Harris Hawk Optimization(BCHHO)algorithms.Computational results confirm the superiority of the BEHHO for determining connected metric dimension.
基金Supported by National Natural Science Foundation of China(71171089)Research for PM_(2.5) Contamination Characteristics and Prevention and Control Countermeasures in Dongguan City(Dongcaidan[2013]222)
文摘A problem of the air pollution control in China is getting to know a regional contribution rate of internal and external source of PM2.5. In this paper,Set Pair Analysis( SPA) method is proposed to calculate the contribution rate of PM2.5in Dongguan City. Due to geographic,meteorological factors and the low concentration of air pollutants in Qingxi area,the PM2.5in this place is mainly contributed by the regional transport of air pollutants from other inside areas of Dongguan,and less affected by the outside of Dongguan. So the concentration of PM2.5in Qingxi area can reflect the Dongguan's basic background concentration of PM2.5. On the basis of the basic background concentration,firstly the concentration of each pollutant components is divided into the internal part and the mixed part. Secondly using the source apportionment samples of five monitoring sites in Dongguan we can respectively construct a sample set A and an evaluation set B. Thirdly the SPA is operated onto the mixed part in terms of set B.At last the connection degree between the concentration of each pollutant components and external source and internal source will be calculated,that is the contribution rate. The research reveals that the contribution rate of internal source and external source of PM2.5in Dongguan City is 83%and 17% respectively,which roughly met expectations. This method is simple and effective and it can provide a reference for the government taking reduction measures to control PM2.5pollutants emission.
文摘The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that every square of an n × n board is attacked? Beginning in 2005 with Amirabadi, Burchett, and Hedetniemi [2] [3], work on this problem, and two other related problems, has seen progress. Bounds have been given for the values of all three domination parameters on the queen’s graph. In this paper, formations of queens are given that provide new bounds for the values of total, paired, and connected domination on the queen’s graph, denoted , , and respectively. For any n × n board size, the new bound of is arrived at, along with the separate bounds of , for with , and , for with .
文摘An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least k. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ<sub>h</sub>k</sup> ( G )denote the least λ such that G admits an L(h,k) -labeling using labels from {0,1,...λ}. A Cayley graph of group is called circulant graph of order n, if the group is isomorphic to Z<sub>n.</sub> In this paper, initially we investigate the L(h,k) -labeling for circulant graphs with “large” connection sets, and then we extend our observation and find the span of L(h,k) -labeling for any circulants of order n. .