In this paper, we propose a new perspective to discuss the N-order fixed point theory of set-valued and single-valued mappings. There are two aspects in our work: we first define a product metric space with a graph fo...In this paper, we propose a new perspective to discuss the N-order fixed point theory of set-valued and single-valued mappings. There are two aspects in our work: we first define a product metric space with a graph for the single-valued mapping whose conversion makes the results and proofs concise and straightforward, and then we propose an <em>SG</em>-contraction definition for set-valued mapping which is more general than some recent contraction’s definition. The results obtained in this paper extend and unify some recent results of other authors. Our method to discuss the N-order fixed point unifies <em>N</em>-order fixed point theory of set-valued and single-valued mappings.展开更多
In this paper, we use a combinatorial analysis method. In the complete graph K N with edges colored arbitrarily by red or blue, we consider the proposition of the subgraph of the red graph or blue graph induced by t...In this paper, we use a combinatorial analysis method. In the complete graph K N with edges colored arbitrarily by red or blue, we consider the proposition of the subgraph of the red graph or blue graph induced by the neighborhood of some vertex in V(K N). Inspired by the main results of Jayawardene and Rousseau (Ars Combinatoria, 2000, 163-173), we determine the Ramsey numbers of r(K 1, 4, G), where G is the three-partite graph of order six without isolate vertex.展开更多
The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the comple...The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.展开更多
In the past few decades, the study of collective motion phase transition process has made great progress. It is also important for the description of the spatial distribution of particles. In this work, we propose a n...In the past few decades, the study of collective motion phase transition process has made great progress. It is also important for the description of the spatial distribution of particles. In this work, we propose a new order parameter φ to quantify the degree of order in the spatial distribution of particles. The results show that the spatial distribution order parameter can effectively describe the transition from a disorderly moving phase to a phase with a coherent motion of the particle distribution and the same conclusion could be obtained for systems with different sizes. Furthermore, we develop a powerful molecular dynamic graph network(MDGNet) model to realize the long-term prediction of the self-propelled collective system solely from the initial particle positions and movement angles. Employing this model, we successfully predict the order parameters of the specified time step. And the model can also be applied to analyze other types of complex systems with local interactions.展开更多
A connected graph G=(V,E)is called a quasi-tree graph if there exists a vertex v0∈V(G)such that G-v0 is a tree.In this paper,we determine all quasi-tree graphs of order n with the second largest signless Laplacian ei...A connected graph G=(V,E)is called a quasi-tree graph if there exists a vertex v0∈V(G)such that G-v0 is a tree.In this paper,we determine all quasi-tree graphs of order n with the second largest signless Laplacian eigenvalue greater than or equal to n-3.As an application,we determine all quasi-tree graphs of order n with the sum of the two largest signless Laplacian eigenvalues greater than to 2 n-5/4.展开更多
Discovering publication hierarchically-ordered contexts is the main task in context-based searching paradigm. The proposed techniques to discover publication contexts relies on the availability of domain-specific inpu...Discovering publication hierarchically-ordered contexts is the main task in context-based searching paradigm. The proposed techniques to discover publication contexts relies on the availability of domain-specific inputs, namely a pre-specified ontology terms. A problem with this technique is that the needed domain-specific inputs may not be available in some scientific disciplines. In this paper, we propose utilizing a powerful input that is naturally available in any scientific discipline to discover the hierarchically-ordered contexts of it, namely paper citation and co-authorship graphs. More specifically, we propose a set of domain-specific bibliometry-aware features that are automatically computable instead of domain-specific inputs that need experts’ efforts to prepare. Another benefit behind considering bibliometric-features to adapt to the special characteristics of the literature environment being targeted, which in turn facilitates contexts membership decision making. One key advantage of our proposal is that it considers temporal changes of the targeted publication set.展开更多
Dear Editor,This letter proposes the graph tensor alliance attention network(GT-A^(2)T)to represent a dynamic graph(DG)precisely.Its main idea includes 1)Establishing a unified spatio-temporal message propagation fram...Dear Editor,This letter proposes the graph tensor alliance attention network(GT-A^(2)T)to represent a dynamic graph(DG)precisely.Its main idea includes 1)Establishing a unified spatio-temporal message propagation framework on a DG via the tensor product for capturing the complex cohesive spatio-temporal interdependencies precisely and 2)Acquiring the alliance attention scores by node features and favorable high-order structural correlations.展开更多
Ordering based search methods have advantages over graph based search methods for structure learning of Bayesian networks in terms on the efficiency. With the aim of further increasing the accuracy of ordering based s...Ordering based search methods have advantages over graph based search methods for structure learning of Bayesian networks in terms on the efficiency. With the aim of further increasing the accuracy of ordering based search methods, we first propose to increase the search space, which can facilitate escaping from the local optima. We present our search operators with majorizations, which are easy to implement. Experiments show that the proposed algorithm can obtain significantly more accurate results. With regard to the problem of the decrease on efficiency due to the increase of the search space, we then propose to add path priors as constraints into the swap process. We analyze the coefficient which may influence the performance of the proposed algorithm, the experiments show that the constraints can enhance the efficiency greatly, while has little effect on the accuracy. The final experiments show that, compared to other competitive methods, the proposed algorithm can find better solutions while holding high efficiency at the same time on both synthetic and real data sets.展开更多
We deal with a consensus control problem for a group of third order agents which are networked by digraphs.Assuming that the control input of each agent is constructed based on weighted difference between its states a...We deal with a consensus control problem for a group of third order agents which are networked by digraphs.Assuming that the control input of each agent is constructed based on weighted difference between its states and those of its neighbor agents, we aim to propose an algorithm on computing the weighting coefficients in the control input. The problem is reduced to designing Hurwitz polynomials with real or complex coefficients. We show that by using Hurwitz polynomials with complex coefficients, a necessary and sufficient condition can be obtained for designing the consensus algorithm. Since the condition is both necessary and sufficient, we provide a kind of parametrization for all the weighting coefficients achieving consensus. Moreover, the condition is a natural extension to second order consensus, and is reasonable and practical due to its comparatively decreased computation burden. The result is also extended to the case where communication delay exists in the control input.展开更多
For any group G, denote byπe(G) the set of orders of elements in G. Given a finite group G, let h(πe (G)) be the number of isomorphism classes of finite groups with the same set πe(G) of element orders. A group G i...For any group G, denote byπe(G) the set of orders of elements in G. Given a finite group G, let h(πe (G)) be the number of isomorphism classes of finite groups with the same set πe(G) of element orders. A group G is called k-recognizable if h(πe(G)) = k <∞, otherwise G is called non-recognizable. Also a 1-recognizable group is called a recognizable (or characterizable) group. In this paper the authors show that the simple groups PSL(3,q), where 3 < q≡±2 (mod 5) and (6, (q-1)/2) = 1, are recognizable.展开更多
The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decis...The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.展开更多
This paper deals with the consensus problem of multi-agent systems with second-order dynamics. The objective is to design algorithms such that all agents will have same positions and velocities. First, a reference mod...This paper deals with the consensus problem of multi-agent systems with second-order dynamics. The objective is to design algorithms such that all agents will have same positions and velocities. First, a reference model based consensus algorithm is proposed. It is proved that the consensus can be achieved if the communication graph has a spanning tree. Different from most of the consensus algorithms proposed in the literature, the parameters of the control laws are different among agents. Therefore, each agent can design its control law independently. Secondly, it gives a consensus algorithm for the case that the velocities of the agents are not available. Thirdly, the effectiveness of the input delay and the communication delay is considered. It shows that consensus can be achieved if the input delay of every agent is smaller than a bound related to parameters in its control law. Finally, some numerical examples are given to illustrate the proposed results.展开更多
In this paper, we mainly deal with a class of higher-order coupled Kirch-hoff-type equations. At first, we take advantage of Hadamard’s graph to get the equivalent form of the original equations. Then, the inertial m...In this paper, we mainly deal with a class of higher-order coupled Kirch-hoff-type equations. At first, we take advantage of Hadamard’s graph to get the equivalent form of the original equations. Then, the inertial manifolds are proved by using spectral gap condition. The main result we gained is that the inertial manifolds are established under the proper assumptions of M(s) and gi(u,v), i=1, 2.展开更多
For a simple graph G, the energy E（G） is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un...For a simple graph G, the energy E（G） is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un｜ d（x） = r for any vertex x ∈ V（Cl）}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39（2, 2, 2） ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.展开更多
The design of large disk array architectures leads to interesting combinatorial problems. Minimizing the number of disk operations when writing to consecutive disks leads to the concept of “cluttered orderings” whic...The design of large disk array architectures leads to interesting combinatorial problems. Minimizing the number of disk operations when writing to consecutive disks leads to the concept of “cluttered orderings” which were introduced for the complete graph by Cohen et al. (2001). Mueller et al. (2005) adapted the concept of wrapped Δ-labellings to the complete bipartite case. In this paper, we give some sequence in order to generate wrapped Δ-labellings as cluttered orderings for the complete bipartite graph. New sequence we give is different from the sequences Mueller et al. gave, though the same graphs in which these sequences are labeled.展开更多
If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutati...If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both the graph and its complement have transitive orientations. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. We show that only the caterpillars are permutation graphs among the trees. A simple method of constructing permutation graphs is also presented here.展开更多
文摘In this paper, we propose a new perspective to discuss the N-order fixed point theory of set-valued and single-valued mappings. There are two aspects in our work: we first define a product metric space with a graph for the single-valued mapping whose conversion makes the results and proofs concise and straightforward, and then we propose an <em>SG</em>-contraction definition for set-valued mapping which is more general than some recent contraction’s definition. The results obtained in this paper extend and unify some recent results of other authors. Our method to discuss the N-order fixed point unifies <em>N</em>-order fixed point theory of set-valued and single-valued mappings.
文摘In this paper, we use a combinatorial analysis method. In the complete graph K N with edges colored arbitrarily by red or blue, we consider the proposition of the subgraph of the red graph or blue graph induced by the neighborhood of some vertex in V(K N). Inspired by the main results of Jayawardene and Rousseau (Ars Combinatoria, 2000, 163-173), we determine the Ramsey numbers of r(K 1, 4, G), where G is the three-partite graph of order six without isolate vertex.
基金Supported by the National Natural Science Foundation of China(11861011,11501133,11661010)。
文摘The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.
基金the National Natural Science Foundation of China (Grant No. 11702289)Key core technology and generic technology research and development project of Shanxi Province of China (Grant No. 2020XXX013)the National Key Research and Development Project of China。
文摘In the past few decades, the study of collective motion phase transition process has made great progress. It is also important for the description of the spatial distribution of particles. In this work, we propose a new order parameter φ to quantify the degree of order in the spatial distribution of particles. The results show that the spatial distribution order parameter can effectively describe the transition from a disorderly moving phase to a phase with a coherent motion of the particle distribution and the same conclusion could be obtained for systems with different sizes. Furthermore, we develop a powerful molecular dynamic graph network(MDGNet) model to realize the long-term prediction of the self-propelled collective system solely from the initial particle positions and movement angles. Employing this model, we successfully predict the order parameters of the specified time step. And the model can also be applied to analyze other types of complex systems with local interactions.
基金Supported by the National Natural Science Foundation of China(Grant No.11771443)the Fundamental Research Funds for the Central Universities(Grant No.2018BSCXB24)the Postgraduate Research&Practice Innovation Program of Jiangsu Province(Grant No.KYCX18JL980).
文摘A connected graph G=(V,E)is called a quasi-tree graph if there exists a vertex v0∈V(G)such that G-v0 is a tree.In this paper,we determine all quasi-tree graphs of order n with the second largest signless Laplacian eigenvalue greater than or equal to n-3.As an application,we determine all quasi-tree graphs of order n with the sum of the two largest signless Laplacian eigenvalues greater than to 2 n-5/4.
文摘Discovering publication hierarchically-ordered contexts is the main task in context-based searching paradigm. The proposed techniques to discover publication contexts relies on the availability of domain-specific inputs, namely a pre-specified ontology terms. A problem with this technique is that the needed domain-specific inputs may not be available in some scientific disciplines. In this paper, we propose utilizing a powerful input that is naturally available in any scientific discipline to discover the hierarchically-ordered contexts of it, namely paper citation and co-authorship graphs. More specifically, we propose a set of domain-specific bibliometry-aware features that are automatically computable instead of domain-specific inputs that need experts’ efforts to prepare. Another benefit behind considering bibliometric-features to adapt to the special characteristics of the literature environment being targeted, which in turn facilitates contexts membership decision making. One key advantage of our proposal is that it considers temporal changes of the targeted publication set.
基金supported in part by the National Natural Science Foundation of China(62372385).
文摘Dear Editor,This letter proposes the graph tensor alliance attention network(GT-A^(2)T)to represent a dynamic graph(DG)precisely.Its main idea includes 1)Establishing a unified spatio-temporal message propagation framework on a DG via the tensor product for capturing the complex cohesive spatio-temporal interdependencies precisely and 2)Acquiring the alliance attention scores by node features and favorable high-order structural correlations.
基金supported by the National Natural Science Fundation of China(61573285)the Doctoral Fundation of China(2013ZC53037)
文摘Ordering based search methods have advantages over graph based search methods for structure learning of Bayesian networks in terms on the efficiency. With the aim of further increasing the accuracy of ordering based search methods, we first propose to increase the search space, which can facilitate escaping from the local optima. We present our search operators with majorizations, which are easy to implement. Experiments show that the proposed algorithm can obtain significantly more accurate results. With regard to the problem of the decrease on efficiency due to the increase of the search space, we then propose to add path priors as constraints into the swap process. We analyze the coefficient which may influence the performance of the proposed algorithm, the experiments show that the constraints can enhance the efficiency greatly, while has little effect on the accuracy. The final experiments show that, compared to other competitive methods, the proposed algorithm can find better solutions while holding high efficiency at the same time on both synthetic and real data sets.
基金supported by Japan Ministry of Education,Sciences and Culture(C21560471)the National Natural Science Foundation of China(61603268)+1 种基金the Research Project Supported by Shanxi Scholarship Council of China(2015-044)the Fundamental Research Project of Shanxi Province(2015021085)
文摘We deal with a consensus control problem for a group of third order agents which are networked by digraphs.Assuming that the control input of each agent is constructed based on weighted difference between its states and those of its neighbor agents, we aim to propose an algorithm on computing the weighting coefficients in the control input. The problem is reduced to designing Hurwitz polynomials with real or complex coefficients. We show that by using Hurwitz polynomials with complex coefficients, a necessary and sufficient condition can be obtained for designing the consensus algorithm. Since the condition is both necessary and sufficient, we provide a kind of parametrization for all the weighting coefficients achieving consensus. Moreover, the condition is a natural extension to second order consensus, and is reasonable and practical due to its comparatively decreased computation burden. The result is also extended to the case where communication delay exists in the control input.
基金This work has been supported by the Research Institute for Fundamental Sciences Tabriz,Iran.
文摘For any group G, denote byπe(G) the set of orders of elements in G. Given a finite group G, let h(πe (G)) be the number of isomorphism classes of finite groups with the same set πe(G) of element orders. A group G is called k-recognizable if h(πe(G)) = k <∞, otherwise G is called non-recognizable. Also a 1-recognizable group is called a recognizable (or characterizable) group. In this paper the authors show that the simple groups PSL(3,q), where 3 < q≡±2 (mod 5) and (6, (q-1)/2) = 1, are recognizable.
文摘The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.
基金supported by the National Natural Science Foundation of China (Grant No. 60904022)
文摘This paper deals with the consensus problem of multi-agent systems with second-order dynamics. The objective is to design algorithms such that all agents will have same positions and velocities. First, a reference model based consensus algorithm is proposed. It is proved that the consensus can be achieved if the communication graph has a spanning tree. Different from most of the consensus algorithms proposed in the literature, the parameters of the control laws are different among agents. Therefore, each agent can design its control law independently. Secondly, it gives a consensus algorithm for the case that the velocities of the agents are not available. Thirdly, the effectiveness of the input delay and the communication delay is considered. It shows that consensus can be achieved if the input delay of every agent is smaller than a bound related to parameters in its control law. Finally, some numerical examples are given to illustrate the proposed results.
文摘In this paper, we mainly deal with a class of higher-order coupled Kirch-hoff-type equations. At first, we take advantage of Hadamard’s graph to get the equivalent form of the original equations. Then, the inertial manifolds are proved by using spectral gap condition. The main result we gained is that the inertial manifolds are established under the proper assumptions of M(s) and gi(u,v), i=1, 2.
基金Supported by the National Natural Science Foundation of China(Grant No.11326216)the Docter Foundationof Shandong University of Technology(Grant No.413010)
文摘For a simple graph G, the energy E（G） is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un｜ d（x） = r for any vertex x ∈ V（Cl）}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39（2, 2, 2） ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.
文摘The design of large disk array architectures leads to interesting combinatorial problems. Minimizing the number of disk operations when writing to consecutive disks leads to the concept of “cluttered orderings” which were introduced for the complete graph by Cohen et al. (2001). Mueller et al. (2005) adapted the concept of wrapped Δ-labellings to the complete bipartite case. In this paper, we give some sequence in order to generate wrapped Δ-labellings as cluttered orderings for the complete bipartite graph. New sequence we give is different from the sequences Mueller et al. gave, though the same graphs in which these sequences are labeled.
文摘If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both the graph and its complement have transitive orientations. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. We show that only the caterpillars are permutation graphs among the trees. A simple method of constructing permutation graphs is also presented here.
