A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a...A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.展开更多
Urban air pollution has brought great troubles to physical and mental health,economic development,environmental protection,and other aspects.Predicting the changes and trends of air pollution can provide a scientific ...Urban air pollution has brought great troubles to physical and mental health,economic development,environmental protection,and other aspects.Predicting the changes and trends of air pollution can provide a scientific basis for governance and prevention efforts.In this paper,we propose an interval prediction method that considers the spatio-temporal characteristic information of PM_(2.5)signals from multiple stations.K-nearest neighbor(KNN)algorithm interpolates the lost signals in the process of collection,transmission,and storage to ensure the continuity of data.Graph generative network(GGN)is used to process time-series meteorological data with complex structures.The graph U-Nets framework is introduced into the GGN model to enhance its controllability to the graph generation process,which is beneficial to improve the efficiency and robustness of the model.In addition,sparse Bayesian regression is incorporated to improve the dimensional disaster defect of traditional kernel density estimation(KDE)interval prediction.With the support of sparse strategy,sparse Bayesian regression kernel density estimation(SBR-KDE)is very efficient in processing high-dimensional large-scale data.The PM_(2.5)data of spring,summer,autumn,and winter from 34 air quality monitoring sites in Beijing verified the accuracy,generalization,and superiority of the proposed model in interval prediction.展开更多
In this paper we prove that the generalized permutation graph G（n, k） is upper embeddable if it has at most two odd subcycles, and that the maximum genus of G（n, k） is more than 「β（G（n,k））/3」 in most cases.
We introduce Tribonacci cordial labeling as an extension of Fibonacci cordial labeling, a well-known form of vertex-labelings. A graph that admits Tribonacci cordial labeling is called Tribonacci cordial graph. In thi...We introduce Tribonacci cordial labeling as an extension of Fibonacci cordial labeling, a well-known form of vertex-labelings. A graph that admits Tribonacci cordial labeling is called Tribonacci cordial graph. In this paper we investigate whether some well-known graphs are Tribonacci cordial.展开更多
Recently,so-called tree-based phylogenetic networks have attracted considerable attention.These networks can be constructed from a phylogenetic tree,called the base tree,by adding additional edges.The primary aim of t...Recently,so-called tree-based phylogenetic networks have attracted considerable attention.These networks can be constructed from a phylogenetic tree,called the base tree,by adding additional edges.The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures.Even though it is generally known that determining whether a network is tree-based is an NP-complete problem,one of these criteria,namely edge-basedness,can be verified in linear time.Surprisingly,the class of edgebased networks is closely related to a well-known family of graphs,namely,the class of generalized series-parallel graphs,and we explore this relationship in full detail.Additionally,we introduce further classes of tree-based networks and analyze their relationships.展开更多
Breeze/architecture description language（ADL）, is an eX tensible markup language（XML） based architecture description language which is used to model software systems at the architecture level. Though Breeze/ADL pr...Breeze/architecture description language（ADL）, is an eX tensible markup language（XML） based architecture description language which is used to model software systems at the architecture level. Though Breeze/ADL provides an appropriate basis for architecture modelling, it can neither analyse nor evaluate the architecture reliability. In this paper, we propose a Breeze/ADL based strategy which, by combining generalized stochastic Petri net（GSPN） and tools for reliability analysis, supports architecture reliability modelling and evaluation. This work expands the idea in three directions： Firstly, we give a Breeze/ADL reliability model in which we add error attributes to Breeze/ADL error model for capturing architecture error information, and at the same time perform the system error state transition through the Breeze/ADL production. Secondly, we present how to map a Breeze/ADL reliability model to a GSPN model, which in turn can be used for reliability analysis. The other task is to develop a Breeze/ADL reliability analysis modelling tool–EXGSPN（Breeze/ADL reliability analysis modelling tool）, and combine it with platform independent petri net editor 2（PIPE2） to carry out a reliability assessment.Abstract： Breeze/architecture description language （ADL）, is an eXtensible markup language （XML） based architecture description language which is used to model software systems at the architecture level. Though Breeze/ADL provides an appropriate basis for architecture modelling, it can neither analyse nor evaluate the architecture reliability. In this paper, we propose a Breeze/ADL based strategy which, by combining generalized stochastic Petri net （GSPN） and tools for reliability analysis, supports architecture reliability modelling and evaluation. This work expands the idea in three directions： Firstly, we give a Breeze/ADL reliability model in which we add error attributes to Breeze/ADL error model for capturing architecture error information, and at the same time perform the system error state transition through the Breeze/ADL production. Secondly, we present how to map a Breeze/ADL reliability model to a GSPN model, which in turn can be used for reliability analysis. The other task is to develop a Breeze/ADL reliability analysis modelling tool-EXGSPN （Breeze/ADL reliability analysis modelling tool）, and combine it with platform independent petri net editor 2 （PIPE2） to carry out a reliability assessment.展开更多
Generalized Petersen graphs iare an important class of commonly used in-terconnection networks and have been studied by various researchers. In this paper, weshow that the diameter of generalized Petersen graph P(m, 2...Generalized Petersen graphs iare an important class of commonly used in-terconnection networks and have been studied by various researchers. In this paper, weshow that the diameter of generalized Petersen graph P(m, 2) is O(m/4) and the 3-widediameter of P(m, 2) is O(m/3).展开更多
Let Fq be a finite field of odd characteristic, m, v the integers with 1 ≤ m ≤ v and K a 2v × 2v nonsingular alternate matrix over Fq. In this paper, the generalized symplectic graph GSp2v（q, m） relative to K...Let Fq be a finite field of odd characteristic, m, v the integers with 1 ≤ m ≤ v and K a 2v × 2v nonsingular alternate matrix over Fq. In this paper, the generalized symplectic graph GSp2v（q, m） relative to K over Fq is introduced. It is the graph with m-dimensional totally isotropic subspaces of the 2v-dimensional symplectic space Fq（2v） as its vertices and two vertices P and Q are adjacent if and only if the rank of PKQw is 1 and the dimension of P ∩ Q is m - 1. It is proved that the full automorphism group of the graph GSp2v（q, m） is the projective semilinear symplectic group P∑p（2v, q）.展开更多
A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the qual...A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.展开更多
An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the...An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.展开更多
The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P（4k, k） and hence a lower bound for ...The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P（4k, k） and hence a lower bound for the crossing number of P（4k, k）. In addition, an upper bound for the crossing number of P（4k, k） is also given.展开更多
The spectra of generalized Cayley graphs of finite abelian groups are investigated in this paper.For a generalized Cayley graph X of a finite group G,the canonical double covering of X is the direct product X×K_(...The spectra of generalized Cayley graphs of finite abelian groups are investigated in this paper.For a generalized Cayley graph X of a finite group G,the canonical double covering of X is the direct product X×K_(2).In this paper,integral generalized Cayley graphs on finite abelian groups are characterized,using the characterization of the spectra of integral Cayley graphs.As an application,the integral generalized Cayley graphs on Z_(p)×Z_(q) and Z2n are investigated,where p and q are odd prime numbers.展开更多
Generalized random graphs are considered where the presence or absence of an edge de- pends on the weights of its nodes. Our main interest is to investigate large deviations for the number of edges per node in such a ...Generalized random graphs are considered where the presence or absence of an edge de- pends on the weights of its nodes. Our main interest is to investigate large deviations for the number of edges per node in such a generalized random graph, where the node weights are deterministic under some regularity conditions, as well as chosen i.i.d, from a finite set with positive components. When the node weights are random variables, obstacles arise because the independence among edges no longer exists, our main tools are some results of large deviations for mixtures. After calculating, our results show that the corresponding rate functions for the deterministic case and the random case are very different.展开更多
In this paper, we consider the family of generalized Petersen graphs P（n,4）. We prove that the metric dimension of P（n, 4） is 3 when n = 0 （mod 4）, and is 4 when n = 4k ＋ 3 （k is even）.For n = 1,2 （mod 4） a...In this paper, we consider the family of generalized Petersen graphs P（n,4）. We prove that the metric dimension of P（n, 4） is 3 when n = 0 （mod 4）, and is 4 when n = 4k ＋ 3 （k is even）.For n = 1,2 （mod 4） and n = 4k ＋ 3 （k is odd）, we prove that the metric dimension of P（n,4） is bounded above by 4. This shows that each graph of the family of generalized Petersen graphs P（n, 4） has constant metric dimension.展开更多
A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent ...A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values.For any vertex u of a generalized strongly regular graph of grade 2 with parameters(n,k;a_(1),a_(2);c_(1),c_(2)),if the number of the vertices that are adjacent to u and share ai(i=1,2)common neighbours with u,or are non-adjacent to u and share c,(i=1,2)common neighbours with is independent of the choice of the vertex u,then the generalized strongly regular graph of grade 2 is free.In this paper,we investigate the generalized strongly regular graph of grade 2 with parameters(n,k;k-1,a_(2);k-1,c_(2))and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.展开更多
Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C（2n ＋ 1; {1, n}） on the projective plane ar...Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C（2n ＋ 1; {1, n}） on the projective plane are described, the number of embeddings of C（2n ＋ 1; {1, n}） on the projective plane follows, then the number of embeddings of the generalized Petersen graph P（2n ＋ 1, n） on the projective plane is deduced from that of C（2n ＋ 1; {1, n}）, because C（2n ＋ 1; {1, n}） is a minor of P（2n ＋ 1, n）, their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P（2n, 2） on the projective plane is also obtained.展开更多
It is shown that the generalized Baumslag-Solitar graphs which have soluble fundamental groups can be constructed from four simple types of graph by a process of decoration. The method of proof is elementary and emplo...It is shown that the generalized Baumslag-Solitar graphs which have soluble fundamental groups can be constructed from four simple types of graph by a process of decoration. The method of proof is elementary and employs the operations of pinching and contracting edges of graphs.展开更多
The exponent of a primitive digraph has been generalized in [2].In this paper we obtain new parameters on generalized exponent of primitive simple graphs (symmetric primitive (0,1)matrices with zero trace) completely.
基金Ming Chen was supported by National Key Research and Development Program of China(No.2024YFA1013900)。
文摘A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.
基金Project(2020YFC2008605)supported by the National Key Research and Development Project of ChinaProject(52072412)supported by the National Natural Science Foundation of ChinaProject(2021JJ30359)supported by the Natural Science Foundation of Hunan Province,China。
文摘Urban air pollution has brought great troubles to physical and mental health,economic development,environmental protection,and other aspects.Predicting the changes and trends of air pollution can provide a scientific basis for governance and prevention efforts.In this paper,we propose an interval prediction method that considers the spatio-temporal characteristic information of PM_(2.5)signals from multiple stations.K-nearest neighbor(KNN)algorithm interpolates the lost signals in the process of collection,transmission,and storage to ensure the continuity of data.Graph generative network(GGN)is used to process time-series meteorological data with complex structures.The graph U-Nets framework is introduced into the GGN model to enhance its controllability to the graph generation process,which is beneficial to improve the efficiency and robustness of the model.In addition,sparse Bayesian regression is incorporated to improve the dimensional disaster defect of traditional kernel density estimation(KDE)interval prediction.With the support of sparse strategy,sparse Bayesian regression kernel density estimation(SBR-KDE)is very efficient in processing high-dimensional large-scale data.The PM_(2.5)data of spring,summer,autumn,and winter from 34 air quality monitoring sites in Beijing verified the accuracy,generalization,and superiority of the proposed model in interval prediction.
基金The NSF (10671073) of Chinathe Scientific Fund (03080045) of the Gathered Talents by Nantong UniversityNSF (07KJB110090) of Jiangsu University.
文摘In this paper we prove that the generalized permutation graph G（n, k） is upper embeddable if it has at most two odd subcycles, and that the maximum genus of G（n, k） is more than 「β（G（n,k））/3」 in most cases.
基金Supported by the National Natural Science Foundation of China (Grant No. 10961023)National Natural Science Foundation of China for Young Scholars (Grant No. 11101232)+1 种基金Natural Science Foundation of Qinghai Province for Young Scholars (Grant No. 2011-Z-929Q)Scientific Research Innovation Program of Qinghai Normal University
文摘In the paper, we prove that all generalized cocktail-party graphs with order at least 23 are determined by their adjacency spectra.
文摘We introduce Tribonacci cordial labeling as an extension of Fibonacci cordial labeling, a well-known form of vertex-labelings. A graph that admits Tribonacci cordial labeling is called Tribonacci cordial graph. In this paper we investigate whether some well-known graphs are Tribonacci cordial.
基金funded by the state Mecklenburg-Western Pomerania by the Landesgraduierten-Studentshipfunded by the University of Greifswald by the Bogislaw-Studentshipfunded by the German Academic Scholarship Foundation by a studentship.
文摘Recently,so-called tree-based phylogenetic networks have attracted considerable attention.These networks can be constructed from a phylogenetic tree,called the base tree,by adding additional edges.The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures.Even though it is generally known that determining whether a network is tree-based is an NP-complete problem,one of these criteria,namely edge-basedness,can be verified in linear time.Surprisingly,the class of edgebased networks is closely related to a well-known family of graphs,namely,the class of generalized series-parallel graphs,and we explore this relationship in full detail.Additionally,we introduce further classes of tree-based networks and analyze their relationships.
基金supported by Jilin Province Science Foundation for Youths(No.20150520060JH)
文摘Breeze/architecture description language（ADL）, is an eX tensible markup language（XML） based architecture description language which is used to model software systems at the architecture level. Though Breeze/ADL provides an appropriate basis for architecture modelling, it can neither analyse nor evaluate the architecture reliability. In this paper, we propose a Breeze/ADL based strategy which, by combining generalized stochastic Petri net（GSPN） and tools for reliability analysis, supports architecture reliability modelling and evaluation. This work expands the idea in three directions： Firstly, we give a Breeze/ADL reliability model in which we add error attributes to Breeze/ADL error model for capturing architecture error information, and at the same time perform the system error state transition through the Breeze/ADL production. Secondly, we present how to map a Breeze/ADL reliability model to a GSPN model, which in turn can be used for reliability analysis. The other task is to develop a Breeze/ADL reliability analysis modelling tool–EXGSPN（Breeze/ADL reliability analysis modelling tool）, and combine it with platform independent petri net editor 2（PIPE2） to carry out a reliability assessment.Abstract： Breeze/architecture description language （ADL）, is an eXtensible markup language （XML） based architecture description language which is used to model software systems at the architecture level. Though Breeze/ADL provides an appropriate basis for architecture modelling, it can neither analyse nor evaluate the architecture reliability. In this paper, we propose a Breeze/ADL based strategy which, by combining generalized stochastic Petri net （GSPN） and tools for reliability analysis, supports architecture reliability modelling and evaluation. This work expands the idea in three directions： Firstly, we give a Breeze/ADL reliability model in which we add error attributes to Breeze/ADL error model for capturing architecture error information, and at the same time perform the system error state transition through the Breeze/ADL production. Secondly, we present how to map a Breeze/ADL reliability model to a GSPN model, which in turn can be used for reliability analysis. The other task is to develop a Breeze/ADL reliability analysis modelling tool-EXGSPN （Breeze/ADL reliability analysis modelling tool）, and combine it with platform independent petri net editor 2 （PIPE2） to carry out a reliability assessment.
基金Supported by NNSF of China(10271114)and(INNSF of China (10301031)
文摘Generalized Petersen graphs iare an important class of commonly used in-terconnection networks and have been studied by various researchers. In this paper, weshow that the diameter of generalized Petersen graph P(m, 2) is O(m/4) and the 3-widediameter of P(m, 2) is O(m/3).
基金supported by National Natural Science Foundation of China(Grant Nos.10990011,11271004 and 61071221)the Doctoral Program of Higher Education of China(Grant No.20100001110007)the Natural Science Foundation of Hebei Province(Grant No.A2009000253)
文摘Let Fq be a finite field of odd characteristic, m, v the integers with 1 ≤ m ≤ v and K a 2v × 2v nonsingular alternate matrix over Fq. In this paper, the generalized symplectic graph GSp2v（q, m） relative to K over Fq is introduced. It is the graph with m-dimensional totally isotropic subspaces of the 2v-dimensional symplectic space Fq（2v） as its vertices and two vertices P and Q are adjacent if and only if the rank of PKQw is 1 and the dimension of P ∩ Q is m - 1. It is proved that the full automorphism group of the graph GSp2v（q, m） is the projective semilinear symplectic group P∑p（2v, q）.
基金supported by the National Natural Science Foundation of China(Nos.11531010,11401510,11501487)the Key Laboratory Project of Xinjiang(No.2015KL019)the Doctoral Fund of Xinjiang University(No.BS150208)
文摘A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.
文摘An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.
文摘The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P（4k, k） and hence a lower bound for the crossing number of P（4k, k）. In addition, an upper bound for the crossing number of P（4k, k） is also given.
基金Acknowledgements This work was Foundation of China （Grant Nos. 11371335, supported by the National Natural Science 11371121）, the International Joint Research Fund Between NSFC-RFBR （Grant No. 11211120148）, and the Natural Science Foundation of Hebei Province （Grant No. 2013205073）.
文摘We determine the automorphism group of the generalized orthogonal graph GO2v＋δ（q, m, G） over Fq of characteristic 2, where 1 〈 m 〈 v.
基金supported by the National Natural Science Foundation of China(No.12271311,12101410,12201414)Taishan Scholars Program of Shandong Province.
文摘The spectra of generalized Cayley graphs of finite abelian groups are investigated in this paper.For a generalized Cayley graph X of a finite group G,the canonical double covering of X is the direct product X×K_(2).In this paper,integral generalized Cayley graphs on finite abelian groups are characterized,using the characterization of the spectra of integral Cayley graphs.As an application,the integral generalized Cayley graphs on Z_(p)×Z_(q) and Z2n are investigated,where p and q are odd prime numbers.
基金Supported by National Natural Science Foundation of China(Grant Nos.11371169 and 11671168)
文摘Generalized random graphs are considered where the presence or absence of an edge de- pends on the weights of its nodes. Our main interest is to investigate large deviations for the number of edges per node in such a generalized random graph, where the node weights are deterministic under some regularity conditions, as well as chosen i.i.d, from a finite set with positive components. When the node weights are random variables, obstacles arise because the independence among edges no longer exists, our main tools are some results of large deviations for mixtures. After calculating, our results show that the corresponding rate functions for the deterministic case and the random case are very different.
文摘In this paper, we consider the family of generalized Petersen graphs P（n,4）. We prove that the metric dimension of P（n, 4） is 3 when n = 0 （mod 4）, and is 4 when n = 4k ＋ 3 （k is even）.For n = 1,2 （mod 4） and n = 4k ＋ 3 （k is odd）, we prove that the metric dimension of P（n,4） is bounded above by 4. This shows that each graph of the family of generalized Petersen graphs P（n, 4） has constant metric dimension.
基金supported by National Natural Science Foundation of China(No.11571091)Natural Science Foundation of Hebei Province,China(No.F2019205147)Innovation Program of Hebei Normal University,China(No.CXZZSS2020050).
文摘A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values.For any vertex u of a generalized strongly regular graph of grade 2 with parameters(n,k;a_(1),a_(2);c_(1),c_(2)),if the number of the vertices that are adjacent to u and share ai(i=1,2)common neighbours with u,or are non-adjacent to u and share c,(i=1,2)common neighbours with is independent of the choice of the vertex u,then the generalized strongly regular graph of grade 2 is free.In this paper,we investigate the generalized strongly regular graph of grade 2 with parameters(n,k;k-1,a_(2);k-1,c_(2))and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.
文摘Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C（2n ＋ 1; {1, n}） on the projective plane are described, the number of embeddings of C（2n ＋ 1; {1, n}） on the projective plane follows, then the number of embeddings of the generalized Petersen graph P（2n ＋ 1, n） on the projective plane is deduced from that of C（2n ＋ 1; {1, n}）, because C（2n ＋ 1; {1, n}） is a minor of P（2n ＋ 1, n）, their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P（2n, 2） on the projective plane is also obtained.
文摘It is shown that the generalized Baumslag-Solitar graphs which have soluble fundamental groups can be constructed from four simple types of graph by a process of decoration. The method of proof is elementary and employs the operations of pinching and contracting edges of graphs.
文摘The exponent of a primitive digraph has been generalized in [2].In this paper we obtain new parameters on generalized exponent of primitive simple graphs (symmetric primitive (0,1)matrices with zero trace) completely.
