Abstract
Quasi-strongly regular digraphs are a combinatorial generalization of strongly regular digraphs and quasi-strongly regular graphs. A quasi-strongly regular digraph \(\Gamma\) with parameters \((n,k,t,a;c_{1},c_{2},\ldots ,c_{p})\) is a k-regular digraph on n vertices such that each vertex is incident with t undirected edges, for any two distinct vertices x, y the number of paths of length 2 from x to y is a if \(x\rightarrow y\) and \(c_{i}\) otherwise, and for each \(c_{i}\) there exist two distinct vertices \(x\nrightarrow y\) such that the number of paths of length 2 from x to y is \(c_{i}\), where \(i\in \{1,2,\ldots ,p\}\). We call p the grade of \(\Gamma\). In this paper, we first study quasi-strongly regular digraphs of grade 2 and obtain some constraints between the parameters. Moreover, we present some constructions of quasi-strongly regular digraphs from different combinatorial objects. Finally, we introduce a variation of quasi-strongly regular digraphs and provide some constructions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alajbegovi\(\acute{{\rm c}}\), H., Huskanovi\(\acute{{\rm c}}\), A., Miklavi\(\check{{\rm c}}\), \(\check{{\rm S}}\)., \(\check{{\rm S}}\)parl. P.: On the extendability of quasi-strongly regular graphs with diameter 2. Graphs Combin. 34, 711–726 (2018)
Bang-Jensen, J., Gutin, G.: Digraphs—Theory. Algorithms and Applications. Springer, New York (2010)
Bannai, E., Ito, T.: Algebraic Combinatorics I: Association Schemes. Benjamin/Cummings, London (1984)
Brouwer, A.A., Olmez, O., Song, S.: Directed strongly regular graphs from 1\(\frac{1}{2}\)-designs. Eur. J. Combin. 33(6), 1174–1177 (2012)
Comellas, F., Fiol, M.A., Gimbert, J., Mitjana, M.: Weakly distance-regular digraphs. J. Combin. Theory Ser. B 90, 233–255 (2004)
Duval, A.M.: A directed version of strongly regular graphs. J. Combin. Theory Ser. A 47, 71–100 (1988)
Duval, A.M., Iourinski, D.: Semidirect product constructions of directed strongly regular graphs. J. Combin. Theory Ser. A 104, 157–167 (2003)
Feng, R., Zeng, L.: Directed strongly regular graphs and their constructions. Adv. Math. (China) 45(6), 817–839 (2016)
Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001)
Goldberg, F.: On quasi-strongly regular graphs. Linear Multilinear Algebra 54(6), 437–451 (2006)
Golightly, W., Haynworth, W., Sarvate, D.G.: A family of connected quasi-strongly regular graph. Congr. Numer. 124, 89–95 (1997)
Hanaki, A., Miyamoto, I.: Classification of association schemes of small order. Discrete Math. 264, 75–80 (2003)
Hobart, S.A., Shaw, T.J.: A note on a family of directed strongly regular graphs. Eur. J. Combin. 20, 77–90 (1999)
Jia, D., Yuan, L., Zhang, G.: On generalized strongly regular graphs. Graphs Combin. 34, 555–570 (2018)
Jørgensen, L.K.: Normally regular digraphs. Electron. J. Combin. 22(4), P4.21 (2015)
Klin, M., Munemasa, A., Muzychuk, M., Zieschang, P.H.: Directed strongly regular graphs obtained from coherent algebras. Linear Algebra Appl. 377(1), 83–109 (2004)
Martínez, L., Araluze, A.: New tools for the construction of directed strongly regular graphs: difference digraphs and partial sum families. J. Combin. Theory Ser. B 99(6), 720–728 (2010)
Olmez, O., Song, S.Y.: Some families of directed strongly regular graphs obtained from certain finite incidence structures. Graphs Combin. 30(6), 1529–1549 (2014)
Wang, K., Suzuki, H.: Weakly distance-regular digraphs. Discrete Math. 264, 225–236 (2003)
Xie, J., Jia, D., Zhang, G.: On quasi-strongly regular graphs with parameters \((n, k, a;k-1, c_{2})\). Discrete Math. 344(3), 112237 (2021)
Zheng, D.: Two Generalizations of Quasi-strongly Regular Graphs, M.S. Thesis. Beijing Normal University, Beijing (2008)
Acknowledgements
This research is partially supported by Natural Science Foundation of Hebei Province (F2019205147 and A2020208010), Natural Science Foundation of Hebei Education Department (QN2021062) and Innovation Program of School of Mathematical Sciences of Hebei Normal University(2021sxbs001). The authors would like to thank the referees and editors for their valuable suggestions which have helped improve this paper.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Guo, Z., Jia, D. & Zhang, G. Some Constructions of Quasi-strongly Regular Digraphs. Graphs and Combinatorics 38, 15 (2022). https://doi.org/10.1007/s00373-021-02441-3
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-021-02441-3