For a handlebody H w ith dH = 5, let F belong S be an essential connected subsurface of S. Let C（S） be the curve complex of S, AC（F） be the arc and curve complex of F , D（H） belong C（S） be ...For a handlebody H w ith dH = 5, let F belong S be an essential connected subsurface of S. Let C（S） be the curve complex of S, AC（F） be the arc and curve complex of F , D（H） belong C（S） be the disk complex of H and πf（D （H ） ） belong AC（F） be the image of D （H） in AC （F）. We introduce the definition of subsurface 1-distance between the 1-simplices of AC（F） and show that under some hypothesis, πF（D（H） ） comes within subsurface 1-distance at most 4 of every 1-simplex of AC （F）.展开更多
A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors.A list assignment of a graph G is a mapping L which assigns to each vertex v a set ...A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors.A list assignment of a graph G is a mapping L which assigns to each vertex v a set L(v)of positive integers.The list 2-distance chromatic number of G denoted byχ_(2)^(l)(G)is the least integer k for which G is list 2-distance k-colorable.In this paper,we prove that every planar graph with g(G)≥5 and△(G)≥40 is list 2-distance(△(G)+4)-colorable.展开更多
The directed L-distance minimal dominating set(MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theo...The directed L-distance minimal dominating set(MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi(ER)random graph and regular random(RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation(BP) algorithm does not converge when the inverse temperatureβ exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds3.3;there is no entropy transition point(or β = ■) in other circumstances. Third, the results of the replica symmetry(RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm.展开更多
文摘For a handlebody H w ith dH = 5, let F belong S be an essential connected subsurface of S. Let C（S） be the curve complex of S, AC（F） be the arc and curve complex of F , D（H） belong C（S） be the disk complex of H and πf（D （H ） ） belong AC（F） be the image of D （H） in AC （F）. We introduce the definition of subsurface 1-distance between the 1-simplices of AC（F） and show that under some hypothesis, πF（D（H） ） comes within subsurface 1-distance at most 4 of every 1-simplex of AC （F）.
基金supported by the National Natural Science Foundation of China(Nos.11771443,12071265)。
文摘A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors.A list assignment of a graph G is a mapping L which assigns to each vertex v a set L(v)of positive integers.The list 2-distance chromatic number of G denoted byχ_(2)^(l)(G)is the least integer k for which G is list 2-distance k-colorable.In this paper,we prove that every planar graph with g(G)≥5 and△(G)≥40 is list 2-distance(△(G)+4)-colorable.
基金supported by the doctoral startup fund of Xinjiang University of China (grant number 208-61357)the National Natural Science Foundation of China (grant number 11 465 019,11 664 040)。
文摘The directed L-distance minimal dominating set(MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi(ER)random graph and regular random(RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation(BP) algorithm does not converge when the inverse temperatureβ exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds3.3;there is no entropy transition point(or β = ■) in other circumstances. Third, the results of the replica symmetry(RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm.
