湯思豪　王偉平

摘 要： 為了拓展Riordan陣與Riordan群理論，提出Riordan有向圖的概念并研究其性質(zhì)，由此建立整數(shù)序列、Riordan陣與圖之間的聯(lián)系。首先，基于Riordan陣，定義Riordan有向圖，并利用Riordan陣的基本性質(zhì)得到Riordan有向圖的邊集滿足的條件。然后，給出Riordan有向圖含有Hamilton路的一個(gè)充分條件以及Riordan有向圖是本原有向圖的一個(gè)充分條件。最后，通過Riordan群上的對(duì)角平移算子提出構(gòu)造同構(gòu)Riordan有向圖的方法。結(jié)果表明：一些特殊的整數(shù)序列與有向圖之間有良好的對(duì)應(yīng)，且利用Riordan陣?yán)碚摽梢詫⒁恍┱麛?shù)序列的性質(zhì)反映到有向圖的性質(zhì)上。

關(guān)鍵詞： Riordan陣；Riordan有向圖；整數(shù)序列；本原有向圖；Hamilton路

中圖分類號(hào)： O151.26 文獻(xiàn)標(biāo)志碼： A 文章編號(hào)： 1673-3851 （2023） 03-0272-07

引文格式：湯思豪，王偉平.Riordan有向圖［J］. 浙江理工大學(xué)學(xué)報(bào)（自然科學(xué)），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群的研究是組合數(shù)學(xué)中的重要課題。Rogers［1］在1978年引入了Renewal陣的概念，Renewal陣可研究Pascal三角、Catalan三角和Motzkin三角等著名的組合矩陣及相關(guān)組合序列。1991年，Shapiro等［2］對(duì)Rogers的工作做了進(jìn)一步推廣，首次引入了Riordan陣和Riordan群的概念，介紹了Riordan陣基本定理，并給出了Riordan陣在組合恒等式、格路計(jì)數(shù)、反演關(guān)系中的許多應(yīng)用。2008年，Wang等［3］提出了廣義Riordan陣的概念，證明了廣義Riordan群與廣義Sheffer群同構(gòu)，并研究了相應(yīng)的反演關(guān)系問題及多項(xiàng)式序列的連接常數(shù)問題。2019年，張晨璐等［4］又給出了廣義Riordan陣新的刻畫，并由此研究了Riordan陣的分解及Lucas u序列、Lucas v序列等多項(xiàng)式序列之間的關(guān)系。

2 結(jié) 論

本文引入了Riordan有向圖的概念，研究了Riordan有向圖的邊集、含Hamilton路的有向圖、本原有向圖，還利用Riordan陣與Riordan群理論，給出一種構(gòu)造同構(gòu)Riordan有向圖的方法。后續(xù)可以在此基礎(chǔ)上，利用圖的群表示理論，研究Riordan有向圖為可遷圖的充分條件或必要條件。

參考文獻(xiàn)：

［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陣相關(guān)的若干多項(xiàng)式序列的關(guān)系研究［J］. 浙江理工大學(xué)學(xué)報(bào)（自然科學(xué)版）， 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］徐俊明. 圖論及其應(yīng)用［M］. 4版. 合肥：中國科學(xué)技術(shù)大學(xué)出版社， 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.

（責(zé)任編輯：康 鋒）

收稿日期： 2022-09-27網(wǎng)絡(luò)出版日期：2022-12-05網(wǎng)絡(luò)出版日期

基金項(xiàng)目： 國家自然科學(xué)基金項(xiàng)目（11671360）；浙江省自然科學(xué)基金項(xiàng)目（LY22A010018）

作者簡介： 湯思豪（1998— ），男，浙江嘉興人，碩士研究生，主要從事組合數(shù)學(xué)方面的研究。

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