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