Please wait a minute...
 北京大学期刊网　|　作者　　审稿人　　编委专家　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展 - 2016, Vol. 45(6): 817-839
 “纪念《数学进展》创刊六十周年”特约综述文章
 有向强正则图及其构造 Directed Strongly Regular Graphs and Their Constructions 冯荣权1, 曾丽伟2 FENG Rongquan1,ZENG Liwei2 1. 北京大学数学科学学院, 数学及其应用''教育部重点实验室, 北京, 100871; 2. 河北师范大学数学与信息科学学院, 石家庄, 河北, 050024 1. LMAM, School of Mathematical Sciences, Peking University, Beijing, 100871, P. R. China; 2. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang, Hebei, 050024, P. R. China 收稿日期: 2016-10-24 出版日期: 2016-11-10 2016, Vol. 45(6): 817-839 DOI: 10.11845/sxjz.2016005a
 PDF [297 KB] 795 下载 632 浏览 引用导出
0
/   /   推荐

Abstract

A directed strongly regular graph (DSRG in short) with parameters $(n,k,t,\lambda,\mu)$, denoted simply by DSRG$(n,k,t,\lambda,\mu)$, is a directed graph with $n$ vertices satisfying two conditions: each vertex has $k$ out-neighbors and $k$ in-neighbors, including $t$ neighbors counted as both in- and out-neighbors of the vertex, and for any two distinct vertices $x$ and $y$, the number of directed paths of length $2$ from $x$ to $y$ is $\lambda$ if $x\rightarrow y$ and $\mu$ otherwise. Directed strongly regular graphs are directed versions of strongly regular graphs, which was originally defined by Duval in 1988. In this paper, we collect some known properties and constructions of directed strongly regular graphs.

 PACS: O157.5
 [1]Adams, F., Gendreau, A., Olmez, O. and Song, S.Y., Construction of directed strongly regular graphs using block matrices, 2013, arXiv: 1311.0494v1.[2]Brouwer, A.E., Olmez, O. and Song, S.Y., Directed strongly regular graphs from $1\frac{1}{2 -designs, European J. Combin., 2012, 33(6): 1174-1177.[3]Chai, Z., Feng, R.Q. and Zeng, L.W., Constructions of$1 \frac{1}{2}$-designs from symplectic geometry over finite fields, Acta Math. Sin., Engl. Ser., 2015, 31(9): 1367-1378.[4]Chen, Y.C., Properties and constructions of directed strongly regular graphs, Master's Thesis, Beijing: Peking University, 2015 (in Chinese).[5]Comellas, F., Fiol, M.A., Gimbert, J. and Mitjana, M., Weakly distance-regular digraphs, J. Combin. Theory Ser. B}, 2004, 90(2): 233-255.[6]Duval, A.M., A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A}, 1988, 47(1): 71-100.[7]Duval, A.M. and Iourinski, D., Semidirect product constructions of directed strongly regular graphs, J. Combin. Theory Ser. A}, 2003, 104(1): 157-167.[8]Feng, R.Q., Zhao, M. and Zeng, L.W., Constructions of$1 \frac{1}{2}$-designs from orthogonal geometry over finite fields, Discrete Math., 2016, 339(1): 382-390.[9]Fiedler, F., Klin, M. and Muzychuk, M.H., Small vertex-transitive directed strongly regular graphs, Discrete Math., 2002, 255(1/2/3): 87-115.[10]Fiedler, F., Klin, M. and Pech, C., Directed strongly regular graphs as elements of coherent algebras, In: General Algebra and Discrete Mathematics (Denecke, K. and Vogel, H.-J. eds.), Aachen: Shaker Verlag, 1999: 69-87.Proceedings of the Conference on General Algebra and Discrete Mathematics, Potsdam 1998[11]Godsil, C.D., Hobart, S.A. and Martin, W.J., Representations of directed strongly regular graphs, European J. Combin., 2007, 28(7): 1980-1993.[12]Gy\"urki, \v{S}. and Klin, M., Sporadic examples of directed strongly regular graphs obtained by computer algebra experimentation, In: Computer Algebra in Scientific Computing (Gerdt, V.P.,Koepf, W., Seiler, W.M. and Vorozhtsov, E.V. eds.), Lecture Notes in Comput. Sci., Vol. 8660, Cham: Springer, 2014, 155-170.[13]Hobart, S.A., Parameters of directed strongly regular graphs, 2015, http://homepages.cwi.nl/\~{}aeb/math/dsrg\\/dsrg.html.[14]Hobart, S.A. and Shaw, T.J., A note on a family of directed strongly regular graphs, European J. Combin., 1999, 20(8): 819-820.[15]J{\o}rgensen, L.K., Directed strongly regular graphs with$\mu=\lambda$, Discrete Math., 2001, 231(1/2/3): 289-293.[16]J{\o}rgensen, L.K., Non-existence of directed strongly regular graphs, Discrete Math., 2003, 264(1/2/3): 111-126.[17]J{\o}rgensen, L.K., Directed strongly regular graphs with rank$5$, Linear Algebra Appl., 2015, 477: 102-111.[18] Klin, M., Munemasa, A., Muzychuk, M. and Zieschang, P.-H., Directed strongly regular graphs obtained from coherent algebras, Linear Algebra Appl., 2004, 377: 83-109.preprint Kyushu MPS-1997-12, Kyushu University, 1997. Maybe also preprint Ben Gurion University, 1997.[19] Mart\'{\i}nez, L. and Araluze, A., New tools for the construction of directed strongly regular graphs, difference digraphs and partial sum families, J. Combin. Theory Ser. B}, 2010, 100(6): 720-728.[20] Neumaier, A.,$t \frac{1}{2}$-designs, J. Combin. Theory Ser. A}, 1980, 28(3): 226-248.[21]Olmez, O., On highly regular digraphs, Ph.D. Thesis, Ames: Iowa State Univ., 2012.Graduate Theses and Dissertations, Paper 12626, http://lib.dr.iastate.edu/etd/12626[22] Olmez, O., Symmetric$1 \frac{1}{2 -designs and $1 \frac{1}{2 -difference sets, J. Combin. Des., 2014, 22(6): 252-269.[23] Olmez, O. and Song, S.Y., Construction of directed strongly regular graphs using finite incidence structures, 2010, arXiv: 1006-5395.[24] Olmez, O. and Song, S.Y., Some families of directed strongly regular graphs obtained from certain finite incidence structures, Graphs Combin., 2014, 30(6): 1529-1549.[25]Reid, K.B. and Brown, E., Doubly regular tournaments are equivalent to skew Hadamard matrices, J. Combin. Theory Ser. A}, 1972, 12(3): 332-338.[26]Van Dam, E.R. and Spence, E., Combinatorial designs with two singular values II, partial geometric designs, Linear Algebra Appl., 2005, 396: 303-316.[27]Wang, K.S. and Suzuki, H., Weakly distance-regular digraphs, Discrete Math., 2003, 264(1/2/3): 225-236.[28] Zeng, L.W., Constructions of$1 \frac{1}{2}$-designs based on geometry of classical groups over finite fields, Ph.D. Thesis, Beijing: Peking University, 2015 (in Chinese).  [1] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155. [2] 任秀秀,杨卫华. 几类特殊有向循环图的核[J]. 数学进展, 2019, 48(2): 137-144. [3] 石慧苓, 高云澍. 标准多重图中点不交的重边四边形[J]. 数学进展, 2018, 47(3): 348-362. [4] 卜月华, 叶飘飘. 围长至少为$\mathbf{5}$的平面图的$\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372. [5] 邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382. [6] 田方. 一类稀疏随机图的距离匹配数[J]. 数学进展, 2018, 47(2): 175-188. [7] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681. [8] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354. [9] 单治超. 有限随机图上的随机游动和传染病模型[J]. 数学进展, 2017, 46(1): 1-12. [10] 王力工, 孙丰妹. 单圈图的无符号拉普拉斯埃斯特拉达指数[J]. 数学进展, 2017, 46(1): 47-54. [11] 崔淑玉,田贵贤. 图的各类矩阵表示的谱半径的界[J]. 数学进展, 2016, 45(5): 711-720. [12] 李玉萍, 孟吉翔, 孙星红. 极大非正则图的边数[J]. 数学进展, 2016, 45(5): 721-726. [13] 单治超. 有限图上首达时等随机变量的极限定理[J]. 数学进展, 2016, 45(4): 481-490. [14] 李晓艳，陈敏，王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499. [15] 姚京京, 邵泽玲, 徐常青. \mbox{\boldmath$\Delta=3\$} 的图的邻和可区别全可选性[J]. 数学进展, 2016, 45(3): 343-348.
Viewed
Full text

Abstract

Cited

Discussed

 © 2015-2017 北京大学图书馆 .