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 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.展开更多
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.展开更多
Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index （AZI index） of a graph G, which is defined asAZI（G） = ∑uv∈E...Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index （AZI index） of a graph G, which is defined asAZI（G） = ∑uv∈E（G）（dudv/du＋du-2）3,where E（G） is the edge set of G, d~ and d~ are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest （resp., the first two smallest） AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.展开更多
Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d_(1), d_(2),..., d_(n)}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)^(3). Usin...Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d_(1), d_(2),..., d_(n)}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)^(3). Using the properties of inequality, we investigate the bounds of AZI for connected graphs, in particular unicyclic graphs in this paper, some useful conclusions are obtained.展开更多
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.展开更多
In this paper,the authors study the problem of distributed Nash equilibrium seeking of N-player games with high-order integrator dynamics subject to disturbances generated by an uncertain exosystem.Similar problems ha...In this paper,the authors study the problem of distributed Nash equilibrium seeking of N-player games with high-order integrator dynamics subject to disturbances generated by an uncertain exosystem.Similar problems have been studied for disturbances with an exactly known exosystem.Compared with the existing results of high-order integrator dynamics,which can only handle sinusoidal disturbances with known frequencies,this paper aims to handle multi-tone disturbances with unknown frequencies by introducing an adaptive control technique to estimate the unknown frequencies.Technically,when the exosystem is known,the disturbance can be dealt with by the Luenburger observer.In contrast,the Luenburger observer cannot deal with an uncertain exosystem.The authors combine the internal model design and some adaptive control technique to solve the proposed problem.Further,the authors also establish the sufficient condition to guarantee the convergence of the estimated unknown frequencies to the actual values of these frequencies.Two examples are given to verify the proposed algorithm.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
The atom-bond connectivity（ABC） index of a graph G, introduced by Estrada,Torres, Rodr′？guez and Gutman in 1998, is defined as the sum of the weights√1/di＋1/dj-2/didj of all edges vivj of G, where di denotes th...The atom-bond connectivity（ABC） index of a graph G, introduced by Estrada,Torres, Rodr′？guez and Gutman in 1998, is defined as the sum of the weights√1/di＋1/dj-2/didj of all edges vivj of G, where di denotes the degree of the vertex vi in G. In this paper, we give an upper bound of the ABC index of a two-tree G with n vertices, that is, ABC（G） ≤（2n- 4）√2/2＋√2n-4/n-1. We also determine the two-trees with the maximum and the second maximum ABC index.展开更多
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-λ.展开更多
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.展开更多
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.展开更多
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|.展开更多
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.展开更多
文摘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 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.
文摘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(Grant No.11326221)
文摘Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index （AZI index） of a graph G, which is defined asAZI（G） = ∑uv∈E（G）（dudv/du＋du-2）3,where E（G） is the edge set of G, d~ and d~ are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest （resp., the first two smallest） AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.
基金Supported by the National Natural Science Foundation of China (Grant No. 61672356)the Teaching Reform Research Project of Shaoyang University (Grant No. 2017JG19)。
文摘Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d_(1), d_(2),..., d_(n)}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)^(3). Using the properties of inequality, we investigate the bounds of AZI for connected graphs, in particular unicyclic graphs in this paper, some useful conclusions are obtained.
文摘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.
基金supported in part by the Research Grants Council of the Hong Kong Special Administration Region under Grant No.14201420in part by the National Natural Science Foundation of China under GrantNo.61973260.
文摘In this paper,the authors study the problem of distributed Nash equilibrium seeking of N-player games with high-order integrator dynamics subject to disturbances generated by an uncertain exosystem.Similar problems have been studied for disturbances with an exactly known exosystem.Compared with the existing results of high-order integrator dynamics,which can only handle sinusoidal disturbances with known frequencies,this paper aims to handle multi-tone disturbances with unknown frequencies by introducing an adaptive control technique to estimate the unknown frequencies.Technically,when the exosystem is known,the disturbance can be dealt with by the Luenburger observer.In contrast,the Luenburger observer cannot deal with an uncertain exosystem.The authors combine the internal model design and some adaptive control technique to solve the proposed problem.Further,the authors also establish the sufficient condition to guarantee the convergence of the estimated unknown frequencies to the actual values of these frequencies.Two examples are given to verify the proposed algorithm.
基金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.
文摘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.
基金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.
基金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.
基金Supported by the National Natural Science Foundation of China(Grant Nos.6116400561440005+6 种基金11161037)the Program for Changjiang Scholars and Innovative Research Team in Universities(Grant No.IRT-15R40)Key Laboratory of Tibetan Information Processing of Ministry of Education of Chinathe Research Fund for the Chunhui Program of Ministry of Education of China(Grant No.Z2014022)the Nature Science Foundation of Qinghai Province(Grant Nos.2013-Z-Y172014-ZJ-9072014-ZJ-721)
文摘The atom-bond connectivity（ABC） index of a graph G, introduced by Estrada,Torres, Rodr′？guez and Gutman in 1998, is defined as the sum of the weights√1/di＋1/dj-2/didj of all edges vivj of G, where di denotes the degree of the vertex vi in G. In this paper, we give an upper bound of the ABC index of a two-tree G with n vertices, that is, ABC（G） ≤（2n- 4）√2/2＋√2n-4/n-1. We also determine the two-trees with the maximum and the second maximum ABC index.
文摘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-λ.
文摘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.
基金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.
文摘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|.
基金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.
