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
    /   /   推荐

摘要 

将参数为$(n,k,t,\lambda,\mu)$的有向强正则图(简称DSRG)记作DSRG$(n,k,t,\lambda,\mu)$, 它是有$n$个顶点且满足以下两个条件的有向图: 每个顶点都有$k$个出邻点和$k$个入邻点,且其中有$t$个为既出又入的邻点; 对任意两个不同顶点$x$和$y$, 若$x\rightarrow y$, 则从$x$到$y$的长为$2$的有向路的个数为$\lambda$, 否则为$\mu$. 有向强正则图是强正则图的有向版本, 最初由Duval在1988 年定义.本文整理了有向强正则图的一些已知性质和构造.

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   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


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