Let G be a 3-connected graph with n vertices. The paper proves that if for each pair of vertices u and v of G, d(u,v)=2, has ｜N(u)∩N(v)｜≤α(α is the minimum independent set number), and then max{d(u),d(v)}≥n+12,...Let G be a 3-connected graph with n vertices. The paper proves that if for each pair of vertices u and v of G, d(u,v)=2, has ｜N(u)∩N(v)｜≤α(α is the minimum independent set number), and then max{d(u),d(v)}≥n+12, then G is a Hamilton connected graph.展开更多
Solving for currents of an electrical circuit with resistances and batteries has always been the ultimate test of proper understanding of Kirchoff’s rules. Yet, it is hardly ever emphasized that a systematic solution...Solving for currents of an electrical circuit with resistances and batteries has always been the ultimate test of proper understanding of Kirchoff’s rules. Yet, it is hardly ever emphasized that a systematic solution of more complex cases requires good understanding of the relevant part of Graph theory. Even though this is usually not covered by Physics’ curriculum, it may still be of interest to some teachers and their mathematically inclined students, who may want to learn details of the rigorous approach. The purpose of this article is to provide a concise derivation of a linear set of equations leading to a unique solution of the problem at hand. We also present a simple computer program which builds such a solution for circuits of any textbook size.展开更多
G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to deter...G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.展开更多
The centralized radio access cellular network infrastructure based on centralized Super Base Station(CSBS) is a promising solution to reduce the high construction cost and energy consumption of conventional cellular n...The centralized radio access cellular network infrastructure based on centralized Super Base Station(CSBS) is a promising solution to reduce the high construction cost and energy consumption of conventional cellular networks. With CSBS, the computing resource for communication protocol processing could be managed flexibly according the protocol load to improve the resource efficiency. Since the protocol load changes frequently and may exceed the capacity of processors, load balancing is needed. However, existing load balancing mechanisms used in data centers cannot satisfy the real-time requirement of the communication protocol processing. Therefore, a new computing resource adjustment scheme is proposed for communication protocol processing in the CSBS architecture. First of all, the main principles of protocol processing resource adjustment is concluded, followed by the analysis on the processing resource outage probability that the computing resource becomes inadequate for protocol processing as load changes. Following the adjustment principles, the proposed scheme is designed to reduce the processing resource outage probability based onthe optimized connected graph which is constructed by the approximate Kruskal algorithm. Simulation re-sults show that compared with the conventional load balancing mechanisms, the proposed scheme can reduce the occurrence number of inadequate processing resource and the additional resource consumption of adjustment greatly.展开更多
Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a rev...Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.展开更多
This paper studies the distributed Nash equilibrium seeking(DNES)problem for games whose action sets are compact and whose network graph is switching satisfying the jointly strongly connected condition.To keep the act...This paper studies the distributed Nash equilibrium seeking(DNES)problem for games whose action sets are compact and whose network graph is switching satisfying the jointly strongly connected condition.To keep the actions of all players in their action sets all the time,one has to resort to the projected gradient-based method.Under the assumption that the unique Nash equilibrium is the unique equilibrium of the pseudogradient system,an algorithm is proposed that is able to exponentially find the Nash equilibrium.Further,the authors also consider the distributed Nash equilibrium seeking problem for games whose actions are governed by high-order integrator dynamics and belong to some compact sets.Two examples are used to illustrate the proposed approach.展开更多
Let G be a connected graph of order p, and let γ7(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results ar...Let G be a connected graph of order p, and let γ7(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G C4 or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1.展开更多
For any vertex u ? V(G), let T N (u) = {u} ∪ {uυ|uυ ? E(G), υ ? υ(G)} ∪ {υ ? υ(G)|uυ ? E(G) and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C f(u) = {f(x) | ...For any vertex u ? V(G), let T N (u) = {u} ∪ {uυ|uυ ? E(G), υ ? υ(G)} ∪ {υ ? υ(G)|uυ ? E(G) and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C f(u) = {f(x) | x ? T N (u)}. For any two adjacent vertices x and y of V(G) such that C f(x) ≠ C f(y), we refer to f as a k-avsdt-coloring of G (“avsdt” is the abbreviation of “ adjacent-vertex-strongly-distinguishing total”). The avsdt-coloring number of G, denoted by χast(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We prove Δ(G) + 1 ? χast(G) ? Δ(G) + 2 for any tree or unique cycle graph G.展开更多
Let G be a 3-connected graph with n vertices, is an independent set of G} , MC(G)=min is an independent set in G}.In this paper, the main results are as follows.TheoremⅠ. If then G is Hamilton-connected.TheoremⅡ. If...Let G be a 3-connected graph with n vertices, is an independent set of G} , MC(G)=min is an independent set in G}.In this paper, the main results are as follows.TheoremⅠ. If then G is Hamilton-connected.TheoremⅡ. If, then G is Hamilton-connected.Theorems I and IIare the best possible, and are incomparable in the sense that neither theorem implies the other.展开更多
It is shown that the lower bound on the maximum genus of a 3-edge connected loopless graph is at least one-third of its cycle rank. Moreover, this lower bound is tight. There are infinitely such graphs attaining the b...It is shown that the lower bound on the maximum genus of a 3-edge connected loopless graph is at least one-third of its cycle rank. Moreover, this lower bound is tight. There are infinitely such graphs attaining the bound.展开更多
In this paper, the problem of consensus for continuous time singular systems of multi-agent networks is considered. The definition of r-consensus is introduced for singular systems of multi-agent networks. Firstly, li...In this paper, the problem of consensus for continuous time singular systems of multi-agent networks is considered. The definition of r-consensus is introduced for singular systems of multi-agent networks. Firstly, linear systems with algebraic constraints are considered, and the corresponding results about consensus and average-consensus are derived. Then r-consensus and consensus problems of singular systems are investigated. Sufficient conditions of r-consensus and consensus are obtained,respectively. Finally, an illustrative example is given to show the effectiveness of the proposed method.展开更多
Evolutionary studies have been of prime importance to life scientists since ancient times. The advancements in technology has made it possible to make available the massive amounts of genomic data. The abundance of ge...Evolutionary studies have been of prime importance to life scientists since ancient times. The advancements in technology has made it possible to make available the massive amounts of genomic data. The abundance of genomic data poses new challenges for biologists, computer scientists and mathematicians to develop approaches for discovery of new relationships in data and evolutionary networks. In this work, nucleotide sequences are converted into binary sequences to explore the network among different species. A new approach based on binary sequences has been proposed to reconstruct the accurate phylogenetic network. The algorithm developed is validated by comparing the results with those obtained by already existing method of network construction. A program is also coded in C language on the Intel Core i3 Dell inspiron machine to obtain the evolutionary network. The new approach developed also provides the fast solutions as there is no need of aligning the sequences.展开更多
This paper considers the finite-time consensus problem for a stochastic multi-species system. First, we give out a nonlinear consensus protocol for the multi-species system with Brownian motion, and propose the defini...This paper considers the finite-time consensus problem for a stochastic multi-species system. First, we give out a nonlinear consensus protocol for the multi-species system with Brownian motion, and propose the definition of finite-time consensus in probability. Second, we prove that the multi-species system can achieve finite-time consensus in probability with different proper protocols by use of graph theory, stochastic Lyapunov function method and probability theory. Finally, some simulations are provided to illustrate the effectiveness of the theoretical results.展开更多
文摘Let G be a 3-connected graph with n vertices. The paper proves that if for each pair of vertices u and v of G, d(u,v)=2, has ｜N(u)∩N(v)｜≤α(α is the minimum independent set number), and then max{d(u),d(v)}≥n+12, then G is a Hamilton connected graph.
文摘Solving for currents of an electrical circuit with resistances and batteries has always been the ultimate test of proper understanding of Kirchoff’s rules. Yet, it is hardly ever emphasized that a systematic solution of more complex cases requires good understanding of the relevant part of Graph theory. Even though this is usually not covered by Physics’ curriculum, it may still be of interest to some teachers and their mathematically inclined students, who may want to learn details of the rigorous approach. The purpose of this article is to provide a concise derivation of a linear set of equations leading to a unique solution of the problem at hand. We also present a simple computer program which builds such a solution for circuits of any textbook size.
文摘G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.
基金supported in part by the National Science Foundationof China under Grant number 61431001the Beijing Talents Fund under Grant number 2015000021223ZK31
文摘The centralized radio access cellular network infrastructure based on centralized Super Base Station(CSBS) is a promising solution to reduce the high construction cost and energy consumption of conventional cellular networks. With CSBS, the computing resource for communication protocol processing could be managed flexibly according the protocol load to improve the resource efficiency. Since the protocol load changes frequently and may exceed the capacity of processors, load balancing is needed. However, existing load balancing mechanisms used in data centers cannot satisfy the real-time requirement of the communication protocol processing. Therefore, a new computing resource adjustment scheme is proposed for communication protocol processing in the CSBS architecture. First of all, the main principles of protocol processing resource adjustment is concluded, followed by the analysis on the processing resource outage probability that the computing resource becomes inadequate for protocol processing as load changes. Following the adjustment principles, the proposed scheme is designed to reduce the processing resource outage probability based onthe optimized connected graph which is constructed by the approximate Kruskal algorithm. Simulation re-sults show that compared with the conventional load balancing mechanisms, the proposed scheme can reduce the occurrence number of inadequate processing resource and the additional resource consumption of adjustment greatly.
文摘Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.
基金supported in part by the Research Grants Council of the Hong Kong Special Administration Region under Grant No.14202619in part by the National Natural Science Foundation of China under Grant No.61973260。
文摘This paper studies the distributed Nash equilibrium seeking(DNES)problem for games whose action sets are compact and whose network graph is switching satisfying the jointly strongly connected condition.To keep the actions of all players in their action sets all the time,one has to resort to the projected gradient-based method.Under the assumption that the unique Nash equilibrium is the unique equilibrium of the pseudogradient system,an algorithm is proposed that is able to exponentially find the Nash equilibrium.Further,the authors also consider the distributed Nash equilibrium seeking problem for games whose actions are governed by high-order integrator dynamics and belong to some compact sets.Two examples are used to illustrate the proposed approach.
基金Supported by the National Science Foundation of Jiangxi province.
文摘Let G be a connected graph of order p, and let γ7(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G C4 or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1.
基金the National Natural Science Foundation of China (Grant Nos. 10771091, 10661007)
文摘For any vertex u ? V(G), let T N (u) = {u} ∪ {uυ|uυ ? E(G), υ ? υ(G)} ∪ {υ ? υ(G)|uυ ? E(G) and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C f(u) = {f(x) | x ? T N (u)}. For any two adjacent vertices x and y of V(G) such that C f(x) ≠ C f(y), we refer to f as a k-avsdt-coloring of G (“avsdt” is the abbreviation of “ adjacent-vertex-strongly-distinguishing total”). The avsdt-coloring number of G, denoted by χast(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We prove Δ(G) + 1 ? χast(G) ? Δ(G) + 2 for any tree or unique cycle graph G.
文摘Let G be a 3-connected graph with n vertices, is an independent set of G} , MC(G)=min is an independent set in G}.In this paper, the main results are as follows.TheoremⅠ. If then G is Hamilton-connected.TheoremⅡ. If, then G is Hamilton-connected.Theorems I and IIare the best possible, and are incomparable in the sense that neither theorem implies the other.
文摘It is shown that the lower bound on the maximum genus of a 3-edge connected loopless graph is at least one-third of its cycle rank. Moreover, this lower bound is tight. There are infinitely such graphs attaining the bound.
基金supported by the National Natural Science Foundation of China under Grant Nos.61174141 and 61374025Research Awards Young and Middle-Aged Scientists of Shandong Province under Grant Nos.BS2011SF009 and BS2011DX019Excellent Youth Foundation of Shandong Province under Grant No.JQ201219
文摘In this paper, the problem of consensus for continuous time singular systems of multi-agent networks is considered. The definition of r-consensus is introduced for singular systems of multi-agent networks. Firstly, linear systems with algebraic constraints are considered, and the corresponding results about consensus and average-consensus are derived. Then r-consensus and consensus problems of singular systems are investigated. Sufficient conditions of r-consensus and consensus are obtained,respectively. Finally, an illustrative example is given to show the effectiveness of the proposed method.
文摘Evolutionary studies have been of prime importance to life scientists since ancient times. The advancements in technology has made it possible to make available the massive amounts of genomic data. The abundance of genomic data poses new challenges for biologists, computer scientists and mathematicians to develop approaches for discovery of new relationships in data and evolutionary networks. In this work, nucleotide sequences are converted into binary sequences to explore the network among different species. A new approach based on binary sequences has been proposed to reconstruct the accurate phylogenetic network. The algorithm developed is validated by comparing the results with those obtained by already existing method of network construction. A program is also coded in C language on the Intel Core i3 Dell inspiron machine to obtain the evolutionary network. The new approach developed also provides the fast solutions as there is no need of aligning the sequences.
基金We would like to thank the editor and referee for their very helpful comments and suggestions which improve this paper significantly. This research is supported by the National Natural Science Foundation of China （Nos. 11461053 and 11261043） （China）, the School Foundation of Ningxia University （No. ZR1315） （China）.
文摘This paper considers the finite-time consensus problem for a stochastic multi-species system. First, we give out a nonlinear consensus protocol for the multi-species system with Brownian motion, and propose the definition of finite-time consensus in probability. Second, we prove that the multi-species system can achieve finite-time consensus in probability with different proper protocols by use of graph theory, stochastic Lyapunov function method and probability theory. Finally, some simulations are provided to illustrate the effectiveness of the theoretical results.
