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.展开更多
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.展开更多
The atom-bond connectivity(ABC) index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC(G) =∑ uv∈E(G) √d u+dv-2 dudv,...The atom-bond connectivity(ABC) index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC(G) =∑ uv∈E(G) √d u+dv-2 dudv,where du denotes the degree of a vertex u in G.A chemical graph is a graph in which no vertex has degree greater than 4.In this paper,we obtain the sharp upper and lower bounds on ABC index of chemical bicyclic graphs.展开更多
It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper emb...It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper embeddable.This lower bound is tight.There are infinitely many 3 connected loopless multigraphs attaining this bound.展开更多
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.展开更多
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.展开更多
Based on the in-depth analysis of the interaction patterns between the components of software system in architecture, this paper illustrates that the association among them is complex and usually changeable during the...Based on the in-depth analysis of the interaction patterns between the components of software system in architecture, this paper illustrates that the association among them is complex and usually changeable during the running period. So we assume the interactions between two adjacency components are grouped into a single connector, which can be used to analyze the influence of components assembly on the survivability for software architecture. The survivability of the components assembly is mapped into the connectivity of graph model. We also bring forward a simplicity method to calculate and quantify the survivability of architecture that could provide a more usable model for designers to evaluate the architecture.展开更多
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.展开更多
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.展开更多
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.展开更多
Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-...Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|.展开更多
A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G(k,d,s)is undirected,simple graph with vertex set V={v...A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G(k,d,s)is undirected,simple graph with vertex set V={v|v=1()kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=(u1…uk)and v=(v1…vk)are adjacent if and only if us+i=vi or vs+i=ui(i=1,…,k-s).In particular G(k,d,1)is just an undirected de Bruijn graph.In this paper,we show that the diameter of G(k,d,s)is k s,the girth is 3.Finally,we prove that G(k,d,s)(s≥k/2)is super-λ.展开更多
文摘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.
文摘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.
基金Supported by the National Natural Science Foundation of China(11071272,10831001,11171279,11101087)the Young Talent Foundation of Fuzhou University(XRC-1154)
文摘The atom-bond connectivity(ABC) index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC(G) =∑ uv∈E(G) √d u+dv-2 dudv,where du denotes the degree of a vertex u in G.A chemical graph is a graph in which no vertex has degree greater than 4.In this paper,we obtain the sharp upper and lower bounds on ABC index of chemical bicyclic graphs.
文摘It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper embeddable.This lower bound is tight.There are infinitely many 3 connected loopless multigraphs attaining this bound.
基金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 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.
基金the National High Technology Research and Development Program of China (2007AA012420)
文摘Based on the in-depth analysis of the interaction patterns between the components of software system in architecture, this paper illustrates that the association among them is complex and usually changeable during the running period. So we assume the interactions between two adjacency components are grouped into a single connector, which can be used to analyze the influence of components assembly on the survivability for software architecture. The survivability of the components assembly is mapped into the connectivity of graph model. We also bring forward a simplicity method to calculate and quantify the survivability of architecture that could provide a more usable model for designers to evaluate the architecture.
文摘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.
文摘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.
文摘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.
文摘Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|.
文摘A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G(k,d,s)is undirected,simple graph with vertex set V={v|v=1()kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=(u1…uk)and v=(v1…vk)are adjacent if and only if us+i=vi or vs+i=ui(i=1,…,k-s).In particular G(k,d,1)is just an undirected de Bruijn graph.In this paper,we show that the diameter of G(k,d,s)is k s,the girth is 3.Finally,we prove that G(k,d,s)(s≥k/2)is super-λ.