Riordan有向图

汤思豪　王伟平

摘 要： 为了拓展Riordan阵与Riordan群理论，提出Riordan有向图的概念并研究其性质，由此建立整数序列、Riordan阵与图之间的联系。首先，基于Riordan阵，定义Riordan有向图，并利用Riordan阵的基本性质得到Riordan有向图的边集满足的条件。然后，给出Riordan有向图含有Hamilton路的一个充分条件以及Riordan有向图是本原有向图的一个充分条件。最后，通过Riordan群上的对角平移算子提出构造同构Riordan有向图的方法。结果表明：一些特殊的整数序列与有向图之间有良好的对应，且利用Riordan阵理论可以将一些整数序列的性质反映到有向图的性质上。

关键词： Riordan阵；Riordan有向图；整数序列；本原有向图；Hamilton路

中图分类号： O151.26 文献标志码： A 文章编号： 1673-3851 （2023） 03-0272-07

引文格式：汤思豪，王伟平.Riordan有向图［J］. 浙江理工大学学报（自然科学），2023，49（2）：272-278.

Reference Format： TANG Sihao， WANG Weiping. Riordan digraphs［J］. Journal of Zhejiang Sci-Tech University，2023，49（2）：272-278.

Riordan digraphs

TANG Sihao， WANG Weiping

（School of Science， Zhejiang Sci-Tech University， Hangzhou 310018， China）

Abstract：  In order to expand the theory of Riordan arrays and Riordan group， we introduce the concept of Riordan digraphs and study their properties. As a result， we establish the relations among integer sequences， Riordan arrays and graphs. Firstly， we define the Riordan digraphs on the basis of Riordan arrays， and obtain the conditions of the edge-sets of the Riordan digraphs by using the basic properties of Riordan arrays. Next， we conclude a sufficient condition for the existence of a Hamilton path in a Riordan digraph and a sufficient condition for a Riordan digraph to be primitive. Finally， we propose a method to construct isomorphic Riordan digraphs by using diagonal translation operator on the Riordan group. The results show that some special integer sequences are well related to digraphs， and some properties of integer sequences can be reflected to those of digraphs by using the theory of Riordan arrays.

Key words： Riordan arrays; Riordan digraphs; integer sequences; primitive digraph; Hamilton path

0 引 言

Riordan阵及Riordan群的研究是组合数学中的重要课题。Rogers［1］在1978年引入了Renewal阵的概念，Renewal阵可研究Pascal三角、Catalan三角和Motzkin三角等著名的组合矩阵及相关组合序列。1991年，Shapiro等［2］對Rogers的工作做了进一步推广，首次引入了Riordan阵和Riordan群的概念，介绍了Riordan阵基本定理，并给出了Riordan阵在组合恒等式、格路计数、反演关系中的许多应用。2008年，Wang等［3］提出了广义Riordan阵的概念，证明了广义Riordan群与广义Sheffer群同构，并研究了相应的反演关系问题及多项式序列的连接常数问题。2019年，张晨璐等［4］又给出了广义Riordan阵新的刻画，并由此研究了Riordan阵的分解及Lucas u序列、Lucas v序列等多项式序列之间的关系。

2 结 论

本文引入了Riordan有向图的概念，研究了Riordan有向图的边集、含Hamilton路的有向图、本原有向图，还利用Riordan阵与Riordan群理论，给出一种构造同构Riordan有向图的方法。后续可以在此基础上，利用图的群表示理论，研究Riordan有向图为可迁图的充分条件或必要条件。

参考文献：

［1］Rogers D G. Pascal triangles， Catalan numbers and renewal arrays［J］. Discrete Mathematics， 1978， 22（3）： 301-310.

［2］Shapiro L W， Getu S， Woan W J， et al. The Riordan group［J］. Discrete Applied Mathematics， 1991， 34（1/2/3）： 229-239.

［3］Wang W P， Wang T M. Generalized Riordan arrays［J］. Discrete Mathematics， 2008， 308（24）： 6466-6500.

［4］张晨璐， 王伟平. 与Riordan阵相关的若干多项式序列的关系研究［J］. 浙江理工大学学报（自然科学版）， 2019， 41（6）： 818-822.

［5］Barry P， Hennessy A， Pantelidis N. Algebraic properties of Riordan subgroups［J］. Journal of Algebraic Combinatorics， 2021， 53（4）： 1015-1036.

［6］He T X， Hsu L C， Shiue P J S. The Sheffer group and the Riordan group［J］. Discrete Applied Mathematics， 2007， 155（15）： 1895-1909.

［7］Luzn A， Merlini D， Morn M A， et al. Complementary Riordan arrays［J］. Discrete Applied Mathematics， 2014， 172： 75-87.

［8］Luzn A， Morn M A， Prieto-Martínez L F. The group generated by Riordan involutions［J］. Revista Matemtica Complutense， 2022， 35（1）： 199-217.

［9］Cheon G S， Kim H. The elements of finite order in the Riordan group over the complex field［J］. Linear Algebra and Its Applications， 2013， 439（12）： 4032-4046.

［10］Deo N， Quinn M J. Pascal graphs and their properties［J］. Fibonacci Quarterly， 1983， 21： 203-214.

［11］Cheon G S， Jung J H， Kitaev S， et al. Riordan graphs I： Structural properties［J］. Linear Algebra and Its Applications， 2019， 579： 89-135.

［12］Cheon G S， Jung J H， Kitaev S， et al. Riordan graphs Ⅱ： Structural properties［J］. Linear Algebra and Its Applications， 2019， 579： 174-215.

［13］徐俊明. 图论及其应用［M］. 4版. 合肥：中国科学技术大学出版社， 2018： 4-5.

［14］Rosenblatt D. On the graphs and asymptotic forms of finite boolean relation matrices and stochastic matrices ［J］. Naval Research Logistics Quarterly， 1957， 4（2）： 151-167.

［15］Dulmage A L， Mendelsohn N S. Graph and matrices［M］//Hararf F. Graph Theory and Theoretical Physics. London： Academic Press， 1967： 167-227.

（责任编辑：康 锋）

收稿日期： 2022-09-27网络出版日期：2022-12-05网络出版日期

基金项目： 国家自然科學基金项目（11671360）；浙江省自然科学基金项目（LY22A010018）

作者简介： 汤思豪（1998— ），男，浙江嘉兴人，硕士研究生，主要从事组合数学方面的研究。

通信作者： 王伟平，E-mail： wpingwang@zstu.edu.cn