Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered ...Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.展开更多
In this paper, we construct some families of strongly regular graphs on finite fields by using unions of cyclotomic classes and index 2 Gauss sums. New infinite families of strongly regular graphs are found.
The goal of the present paper is to provide a gallery of small directed strongly regular graphs.For each graph of order n≤12 and valency k<n/2,a diagram is depicted,its relation to other small directed strongly re...The goal of the present paper is to provide a gallery of small directed strongly regular graphs.For each graph of order n≤12 and valency k<n/2,a diagram is depicted,its relation to other small directed strongly regular graphs is revealed,the full group of automorphisms is described,and some other nice properties are given.To each graph a list of interesting subgraphs is provided as well.展开更多
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.展开更多
Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 ...Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 = x^2 ＋ y^2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k ＋ 1 orders.展开更多
We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility c...We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility conditions are deduced. Furthermore, we establish some relations between the classical Krein parameters and the generalized Krein parameters.展开更多
In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equi...In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equivalent condition of G being Laplacian integral is given. Also for the case of t = 3, if G is non-regular, it is found that G has diameter 2 and girth at most 5 if G is not a tree. Graph G is characterized in the case of its being triangle-free, bipartite and pentagon-free. In both cases, G is Laplacian integral.展开更多
Recently,linear codes with a few weights have been extensively studied due to their applications in secret sharing schemes,constant composition codes,strongly regular graphs and so on.In this paper,based on the Weil s...Recently,linear codes with a few weights have been extensively studied due to their applications in secret sharing schemes,constant composition codes,strongly regular graphs and so on.In this paper,based on the Weil sums,several classes of two-weight or three-weight linear codes are presented by choosing a proper defining set,and their weight enumerators and complete weight enumerators are determined.Furthermore,these codes are proven to be minimal.By puncturing these linear codes,two classes of two-weight projective codes are obtained,and the parameters of the corresponding strongly regular graph are given.This paper generalizes the results of[7].展开更多
The authors study the binary codes spanned by the adjacency matrices of the strongly regular graphs(SRGs)on at most two hundred vertices whose existence is unknown.The authors show that in length less than one hundred...The authors study the binary codes spanned by the adjacency matrices of the strongly regular graphs(SRGs)on at most two hundred vertices whose existence is unknown.The authors show that in length less than one hundred they cannot be cyclic,except for the exceptions of the SRGs of parameters(85,42,20,21)and(96,60,38,36).In particular,the adjacency code of a(85,42,20,21)is the zero-sum code.In the range[100,200]the authors find 29 SRGs that could possibly have a cyclic adjacency code.展开更多
A complete classification of the multivalued coset groups of order 3 is given.The proof is based on the classification of rank 3 groups having regular normal subgroups.
Using Galois rings and Galois fields, we construct several infinite classes of partial geometric difference sets, and partial geometric difference families, with new parameters. Furthermore, these partial geometric di...Using Galois rings and Galois fields, we construct several infinite classes of partial geometric difference sets, and partial geometric difference families, with new parameters. Furthermore, these partial geometric difference sets(and partial geometric difference families) correspond to new infinite families of directed strongly regular graphs. We also discuss some of the links between partially balanced designs, 2-adesigns(which were recently coined by Cunsheng Ding in "Codes from Difference Sets"(2015)), and partial geometric designs, and make an investigation into when a 2-adesign is a partial geometric design.展开更多
Let Г be a distance-regular graph of diameter 3 with strong regular graph Г_(3).The determination of the parameters Г_(3) over the intersection array of the graph Г is a direct problem.Finding an intersection arra...Let Г be a distance-regular graph of diameter 3 with strong regular graph Г_(3).The determination of the parameters Г_(3) over the intersection array of the graph Г is a direct problem.Finding an intersection array of the graph Г with respect to the parameters Г_(3) is an inverse problem.Previously,inverse problemswere solved for Г_(3) by Makhnev and Nirova.In this paper,we study the intersection arrays of distance-regular graph Г of diameter 3,for which the graph Г_(3) is a pseudo-geometric graph of the net PGm(n,m).New infinite series of admissible intersection arrays for these graphs are found.We also investigate the automorphisms of distance-regular graph with the intersection array{20,16,5;1,1,16}.展开更多
In the study of(partial)difference sets and their generalizations in groups G,the most widely used method is to translate their definition into an equation over group ring Z[G]and to investigate this equation by apply...In the study of(partial)difference sets and their generalizations in groups G,the most widely used method is to translate their definition into an equation over group ring Z[G]and to investigate this equation by applying complex representations of G.In this paper,we investigate the existence of(partial)difference sets in a different way.We project the group ring equations in Z[G]to Z[N]where N is a quotient group of G isomorphic to the additive group of a finite field,and then use polynomials over this finite field to derive some existence conditions.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.61502101 and 61170321)the Natural Science Foundation of Jiangsu Province,China(Grant No.BK20140651)the Research Fund for the Doctoral Program of Higher Education of China(Grant No.20110092110024)
文摘Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.
基金supported by National Natural Science Foundation of China (Grant Nos.10971250 and 11171150)
文摘In this paper, we construct some families of strongly regular graphs on finite fields by using unions of cyclotomic classes and index 2 Gauss sums. New infinite families of strongly regular graphs are found.
文摘The goal of the present paper is to provide a gallery of small directed strongly regular graphs.For each graph of order n≤12 and valency k<n/2,a diagram is depicted,its relation to other small directed strongly regular graphs is revealed,the full group of automorphisms is described,and some other nice properties are given.To each graph a list of interesting subgraphs is provided as well.
基金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.
文摘Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 = x^2 ＋ y^2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k ＋ 1 orders.
基金supported by the European Regional Development Fund through the program COMPETEby the Portuguese Government through the FCT—Fundacao para a Ciencia e a Tecnologia under the project PEst—C/MAT/UI0144/2013+1 种基金partially supported by Portuguese Funds trough CIDMA—Center for Research and development in Mathematics and Applications,Department of Mathematics,University of Aveiro,3810-193,Aveiro,Portugalthe Portuguese Foundation for Science and Technology(FCT-Fundacao para a Ciencia e Tecnologia),within Project PEst-OE/MAT/UI4106/2014
文摘We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility conditions are deduced. Furthermore, we establish some relations between the classical Krein parameters and the generalized Krein parameters.
基金Supported by the Anhui Provincial Natural Science Foundation(050460102)National Natural Science Foundation of China(10601001,10571163)+3 种基金NSF of Department of Education of Anhui Province(2004kj027,2005kj005zd)Foundation of Anhui Institute of Architecture and Industry(200510307)Foundation of Mathematics Innovation Team of Anhui UniversityFoundation of Talents Group Construction of Anhui University
文摘In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equivalent condition of G being Laplacian integral is given. Also for the case of t = 3, if G is non-regular, it is found that G has diameter 2 and girth at most 5 if G is not a tree. Graph G is characterized in the case of its being triangle-free, bipartite and pentagon-free. In both cases, G is Laplacian integral.
基金supported by the Natural Science Foundation of China (No.11901062)the Sichuan Natural Science Foundation (No.2024NSFSC0417)。
文摘Recently,linear codes with a few weights have been extensively studied due to their applications in secret sharing schemes,constant composition codes,strongly regular graphs and so on.In this paper,based on the Weil sums,several classes of two-weight or three-weight linear codes are presented by choosing a proper defining set,and their weight enumerators and complete weight enumerators are determined.Furthermore,these codes are proven to be minimal.By puncturing these linear codes,two classes of two-weight projective codes are obtained,and the parameters of the corresponding strongly regular graph are given.This paper generalizes the results of[7].
基金supported by the National Natural Science Foundation of China under Grant Nos. 120710012021 University Graduate Research Project under Grant Nos. Y020410077+1 种基金the National Natural Science Foundation of China under Grant No. 12201170the Natural Science Foundation of Anhui Province under Grant No. 2108085QA03
文摘The authors study the binary codes spanned by the adjacency matrices of the strongly regular graphs(SRGs)on at most two hundred vertices whose existence is unknown.The authors show that in length less than one hundred they cannot be cyclic,except for the exceptions of the SRGs of parameters(85,42,20,21)and(96,60,38,36).In particular,the adjacency code of a(85,42,20,21)is the zero-sum code.In the range[100,200]the authors find 29 SRGs that could possibly have a cyclic adjacency code.
基金supported by National Natural Science Foundation of China(Grant No.12361003)supported by the Sobolev Institute of Mathematics State Contract(Grant No.FWNF-2022-0002)National Natural Science Foundation of China(Grant No.12171126)。
文摘A complete classification of the multivalued coset groups of order 3 is given.The proof is based on the classification of rank 3 groups having regular normal subgroups.
文摘Using Galois rings and Galois fields, we construct several infinite classes of partial geometric difference sets, and partial geometric difference families, with new parameters. Furthermore, these partial geometric difference sets(and partial geometric difference families) correspond to new infinite families of directed strongly regular graphs. We also discuss some of the links between partially balanced designs, 2-adesigns(which were recently coined by Cunsheng Ding in "Codes from Difference Sets"(2015)), and partial geometric designs, and make an investigation into when a 2-adesign is a partial geometric design.
基金supported by RSF,project 14-11-00061-Пsupported by the NNSF of China(11771409).
文摘Let Г be a distance-regular graph of diameter 3 with strong regular graph Г_(3).The determination of the parameters Г_(3) over the intersection array of the graph Г is a direct problem.Finding an intersection array of the graph Г with respect to the parameters Г_(3) is an inverse problem.Previously,inverse problemswere solved for Г_(3) by Makhnev and Nirova.In this paper,we study the intersection arrays of distance-regular graph Г of diameter 3,for which the graph Г_(3) is a pseudo-geometric graph of the net PGm(n,m).New infinite series of admissible intersection arrays for these graphs are found.We also investigate the automorphisms of distance-regular graph with the intersection array{20,16,5;1,1,16}.
基金This work is partially supported by Natural Science Foundation of Hunan Province(No.2019JJ30030)Training Program for Excellent Young Innovators of Changsha(No.kql905052).
文摘In the study of(partial)difference sets and their generalizations in groups G,the most widely used method is to translate their definition into an equation over group ring Z[G]and to investigate this equation by applying complex representations of G.In this paper,we investigate the existence of(partial)difference sets in a different way.We project the group ring equations in Z[G]to Z[N]where N is a quotient group of G isomorphic to the additive group of a finite field,and then use polynomials over this finite field to derive some existence conditions.
