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.展开更多
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.展开更多
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, we study the connectedness of the invariant sets of a graph-directed iterated function system（IFS）. For a graph-directed IFS with N states, we construct N graphs. We prove that all the invariant sets ...In this paper, we study the connectedness of the invariant sets of a graph-directed iterated function system（IFS）. For a graph-directed IFS with N states, we construct N graphs. We prove that all the invariant sets are connected, if and only if all the N graphs are connected; in this case, the invariant sets are all locally connected and path connected. Our result extends the results on the connectedness of the self-similar sets.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
文摘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.
文摘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.
文摘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 Teaching Research Project of Hubei Province(2013469)the 12th Five-Year Project of Education Plan of Hubei Province(2014B379)
文摘In this paper, we study the connectedness of the invariant sets of a graph-directed iterated function system（IFS）. For a graph-directed IFS with N states, we construct N graphs. We prove that all the invariant sets are connected, if and only if all the N graphs are connected; in this case, the invariant sets are all locally connected and path connected. Our result extends the results on the connectedness of the self-similar sets.
基金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.
文摘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 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.
基金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.
