# On Subtree Number Index of Generalized Book Graphs, Fan Graphs, and Wheel Graphs

Authors: Daoqiang Sun; Zhengying Zhao; Xiaoxiao Li; Jiayi Cao; Yu Yang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

With generating function and structural analysis, this paper presents the subtree generating functions and the subtree number index of generalized book graphs, generalized fan graphs, and generalized wheel graphs, respectively. As an application, this paper also briefly studies the subtree number index and the asymptotic properties of the subtree densities in regular book graphs, regular fan graphs, and regular wheel graphs. The results provide the basis for studying novel structural properties of the graphs generated by generalized book graphs, fan graphs, and wheel graphs from the perspective of the subtree number index.


---

## Body

## 1. Introduction

The invariants of the graph and its topological indices have important significance in studying the properties of chemical molecular graphs and network graphs [1–4]. The Wiener index, for example, is defined as the sum of the distances of all disordered vertex pairs, and it can be used to estimate the boiling point of the alkanes [5, 6]. Therefore, new topological indices are constantly introduced by worldwide scholars in recent years.As a representative structural based index, the subtree number indexSTNG of a graph G (also known as ρ-index [7, 8]), which is defined as the number of nonempty labeled subtrees of G, plays an important role in areas such as biological reconstruction [9], reliable network construction [10], and machine learning [11] and therefore has attracted much attention in recent years.The subtree number problem was first proposed by Jamison, when studying the subtree average order of trees [12, 13]. Székely and Wang [8] characterized the extremal graph among all n vertices tree. Meanwhile, they presented the subtree number formula of good binary tree and relation between the Wiener index and subtree number index of trees. Yan and Yeh [14] proposed a linear algorithm for enumerating subtrees of trees and further characterized the trees with the second to fifth largest numbers of subtrees and the tree with the second minimum number of subtrees through graph transformation and generating function. With generating function and cycle contraction carrying weights technique, Yang et al. [15–17] solved the subtree enumeration problem and characterized the extremal graphs among all hexagonal, phenylene chains, and spiro, polyphenyl hexagonal chains of length n, respectively.Using the generating function method, more recently, Chin et al. [18] studied the enumeration problem of subtrees and spanning subtrees of complete graphs, complete bipartite graphs, and theta graphs. Yang et al. [17] studied the expected subtree number index in random polyphenylene and spiro chains. By introducing new “middle parts” of a tree, Li et al. [19] studied several extreme ratios of distance and subtree problems in binary trees. With the combinatorial technique, Kamiński and Prałat [20] provided the upper and lower bounds for the number of subtrees of random tree. Zhang et al. [21] presented the concepts of the eccentric subtree number and studied some extremal results with respect to this topological index in a tree.Wheel graphs, fan graphs, and book graphs are three representative cyclic graphs. Various properties of these graphs have been studied, for example, Lin et al. [22] studied the Laplacian spectral features of vertex extension of wheel graphs and multifan graphs. Daoud [23] studied the number of spanning trees of wheel graphs and complex graphs generated by wheel graphs. Yang et al. [24] studied the subtree problem of wheel graphs and multifan graphs with the generating functions. Barioli [25] studied the complete matrix of book graphs. Based on wheel graph and chicken swarm optimization, Yu et al. [26] proposed a novel hybrid localization scheme for deep mine. Liu et al. [27] proved that multifan graphs were determined by their Laplacian spectra.We first introduce related terminologies and notations in Section2. The subtree generating functions and subtree number indices of generalized book graphs Bnn≥2, fan graphs Fnn≥3, and wheel graphs Wnn≥3 are derived in Section 3. Some special cases are also discussed as immediate consequences. In Section 4, we analyze the asymptotic characteristics of the subtree densities of the aforementioned generalized graphs. We summarize our work in Section 5.


## 2. Terminology and Notation

LetG=VG,EG;f,g be a weighted graph with vertex set VG=v1,v2,…,vn, edge set EG=e1,e2,…,em, vertex weight function f, and edge weight function g. Unless otherwise stated, we specify f:VG⟶ℜ and g:EG⟶ℜ, where ℜ is a commutative ring with a unit element 1. In what follows, we list the symbols that will be used in later discussion.(i)
Denote byLG the leaf set of G.(ii)
Denote byG\X the graph obtained from G by removing X from G.(iii)
Denote bySG the set of all subtrees of G.(iv)
Denote byK1,n a star with n+1 vertices and Pn a path with n vertices.(v)
Denote bySG;X the set of subtrees of G containing X, where X can be a vertex or an edge set.(vi)
Denote bySG;v,Pn the set of subtrees of G containing both vertex v and path Pn.For any subtreeT∈SG, the weight of T is defined as(1)wT=∏v∈VT,e∈ETfvge,and the subtree generating function of G is defined as FG;f,g=∑Ts∈SGwTs. Similarly, we define FG;f,g;X=∑Ts∈SG;XwTs, the subtree generating function of G containing X, and FG;f,g;v,Pn=∑Ts∈SG;v,PnwTs, the subtree generating function of G containing both vertex v and path Pn.Letting vertex and edge weightf=g=1 in the above generating functions, we have the corresponding subtree number indices, namely, STNG=FG;1,1, STNG;X=FG;1,1;X, and STNG;v,Pn=FG;1,1;v,Pn.Next, we introduce some lemmas and definitions that will be used in our arguments. LetT=VT,ET;f,g be a weighted tree on n vertices, vi be a vertex of T, u≠vi be a pendant vertex, and e=u,v be the pendant edge of T. We define a weighted tree T′=VT′,ET′;f′,g′ from T as follows: VT′=VT\u, ET′=ET\e, and(2)f′vs=fvfuge+1,ifvs=v,fvs,otherwise,for any vs∈VT′, g′e=gee∈ET′.Lemma 1 (see [14]).
With the above notations, we have(3)FT;f,g;vi=FT′;f′,g′;vi,FT;f,g=FT′;f′,g′+fu.Definition 1.
If then pendant edges of the star K1,n are replaced by paths of length lii=1,2,…,n, the resulting tree is called a generalized star tree Kl1,l2,…,ln or simply Kn.Definition 2.
DefineBl0,l1,…,ln (or simply Bnn≥2) the n-page generalized book graph constructed by joining the end vertices ui and vi of the n+1 internally disjoint paths uiwi,1wi,2…wi,livi(i=0,1,…,n) of length li+1, where u0=u1=⋯=un=u and v0=v1=⋯=vn=v. Obviously, Bn has 2+∑i=0nli vertices and ∑i=0nli+1 edges.Definition 3.
DefineFl1,…,ln;m1,…,mn−1 (or simply Fnn≥3) the generalized fan graph obtained by firstly constructing a generalized star through identifying the end vertices vi,0i=1,2,…,n of the n internally disjoint paths vi,0vi,1vi,2…vi,licili≥0 together, where vi,0=c0 and then connecting vertex pair ci,ci+1 with path civi,1∗vi,2∗…vi,mi∗ci+1i=1,2,…,n−1 of length mi+1mi≥0, where vi,0=c0, li≥0i=1,2,…,n, and mi≥0i=1,2,…,n−1 (specifying that m0=0). For brevity, we abbreviate some notations.(i)
Denotee¯i,1=c0,vi,1, e¯i,j=vi,j−1,vi,j, e¯i,li+1=vi,li,cii=1,…,n;j=2,…,li.(ii)
Denoteei,1=ci,vi,1∗, ei,j=vi,j−1∗,vi,j∗, ei,mi+1=vi,mi∗,ci+1i=1,…,n−1;j=2,…,mi, specifying that e0,i=∅.Definition 4.
DefineWl1,…,ln;m1,…,mn (or simply Wnn≥3) the generalized wheel graph constructed from the generalized fan graph F(n) (see Definition 3) by joining vertices pair c1 and cn of the generalized fan graph Fn with a path vn,0∗vn,1∗…vn,mn∗vn,mn+1∗, where vn,0∗=cn and vn,mn+1∗=c1. Similarly, we abbreviate some notations for the brevity.(i)
Denotee˜i,1=c0,vi,1, e˜i,j=vi,j−1,vi,j, e˜i,li+1=vi,li,cii=1,…,n;j=2,…,li.(ii)
Denoteei,1∗=ci,vi,1∗, ei,j∗=vi,j−1∗,vi,j∗, ei,mi+1∗=vi,mi∗,ci+1, i=1,…,n;j=2,…,mi, specifying that e0,i∗=∅.


## 3. Subtree Generating Functions for Generalized Book Graphs, Fan Graphs, and Wheel Graphs

### 3.1. Subtree Generating Function for Generalized Book Graphs

Before deriving the subtree generating function for generalized book graphs, we first introduce some lemmas.Lemma 2 (see [14]).
LetPn=VPn,EPn;f,g be a weighted path on n vertices, with VPn=v0,v1,…,vn−1, EPn=vi,vi+1|i=0,1,…,n−2, fv=yv∈VPn and ge=ze∈EPn; then,(4)FPn;f,g=∑i=0n−1n−iyi+1zi,(5)FPn;f,g;v0=∑i=0n−1yi+1zi.Lemma 3 (see [15]).
LetG′=VG′,EG′;f,g be a weighted graph with the common edge u,v, fv=yv∈VG′, ge=ze∈EG′, VG′=VG1′∪VG2′, and EG′=EG1′∪EG2′, G1′∩G2′=u,v, where G1′, G2′ are two weighted graphs; then,(6)FG′;f,g=FG1′;f,g;u,vFG2′;f,g;u,vy2z+FG′\u,v;f,g.Lemma 4 (see [16]).
LetUn=VUn,EUn;f,g be a weighted unicyclic graph with VUn=v1,v2,…,vn, EUn=vi,vi+1|i=1,2,…,n(where vn+1=v1), fv=yv∈VUn, and ge=ze∈EUn, respectively; then, for any fixed vertex vi∈VUn and any continuous k edge set ∪j=1kvi+j−1,vi+jk=1,2,…,n−1, we have(7)FUn;f,g;vi=∑i=1niyizi−1,(8)FUn;f,g;∪j=1kvi+j−1,vi+j=∑i=1n−kiyi+kzi+k−1.The following Lemma follows from Lemmas1 and 2.Lemma 5.
LetKn=VKn,EKn;f,g be a weighted generalized star tree, with fv=yv∈VKn and ge=ze∈EKn; then,(9)FKn;f,g=1yn−1∏i=1n∑j=1li+1yjzj−1+∑i=1n∑j=1lili−j+1yjzj−1.Theorem 1.
LetBn=VBn,EBn;f,g be an n-page weighted generalized book graph, with fv=yv∈VBn and ge=ze∈EBn; then,(10)FBn;f,g=∑i=0nyli+2zli+11−n∑k=1li+1kyk+li+1zk+li∏j=0n∑k=1lj+1kyk+li+1zk+li+2yn∏i=0n∑j=1li+1yjzj−1+∑i=0n∑j=1lili−j+1yjzj−1.Proof.
We divide the subtrees of generalized book graphBn into four categories:(1)
Containingu but not v.(2)
Containingv but not u.(3)
Containing neitheru nor v.(4)
Containing bothu and v.
With structural analysis and Lemma5, we have the subtree generating function of cases (1) and (2) as(11)1yn∏i=0n∑j=1li+1yjzj−1.
With Lemma1, it is easy to see that the subtree generating function of case (3) is(12)∑i=0n∑j=1lili−j+1yjzj−1.
Denote byPuvi=uwi,1wi,2…wi,livi=0,1,2,…,n the path connecting the vertex pair u,v, and Uli+lj+2i,j=Puviwj,lj…wj,2wj,1uj≠i,j∈0,1,…,n an unicyclic graph. With structural analysis, equation (8) in Lemma 4, and Lemma 3, we have the subtree generating function of case (4) as(13)∑i=0n∏0≤j≠i≤nFUli+lj+2i,j;f,g;Puviyli+2zli+1n−1.
The theorem follows from equations (11)–(13).We can further obtain the subtree generating function of special generalized book graphs.Definition 5.
LetBl0,l1,…,ln be an n-page generalized book graph and k be a positive integer; we call Bl0,l1,…,ln an n-page k regular book graph, denoted by Bn,kn≥2, if the lengths of its n+1 internally disjoint paths are all equal to k(namely, li=ki=0,1,…,n). Obviously, Bn,kn≥2 has n+1k+2 vertices and n+1k+1 edges.With Theorem1, it is not difficult to obtain the following corollary.Corollary 1.
LetBn,k=VBn,k,EBn,k;f,g be an n-page k regular book graph, with fv=yv∈VBn,k and ge=ze∈EBn,k; then,(14)FBn,k;f,g=n+1∑i=0k−1k−iyi+1zi+2yn∑i=1k+1yizi−1n+1+n+1yk+2zk+1n−1∑i=1k+1iyi+k+1zi+kn.By substitutingy=1,z=1 into equations (10) and (14), we have the corresponding subtree number indices.Corollary 2.
The subtree number index of then-page generalized book graph Bn is(15)STNBn=2∏i=0nli+1+∑i=0n∑j=0li−1li−j+∑i=0n∏j=0nlj+1lj+22nli+1li+2.Corollary 3.
The subtree number index of then-page k regular book graph Bn,k is(16)STNBn,k=n+1kk+12+2k+1n+1+n+1k2+3k+2n2n.With Corollary3, we have the subtree number index of the Bn,k as illustrated in Table 1.Table 1
The subtree number indexSTNBn,k of the n-page k regular book graph Bn,kk=1,2,…,5;n=2,3,…,11.
nSTNBn,1STNBn,2STNBn,3STNBn,4STNBn,524617144695518003144103845361479039696447469815207825942598803251592481326082284587560245980086536633098770328107989069560092282471801622526348013112013676563301441206768086008215155937900524342230699219653404258897769198888100895088100020972123844531251007942921398312106536466654822631100083886746343251953235183479416354488112133968435462759012000335545041037975585938704203334360071504


### 3.2. Subtree Generating Function of Two-Tailed Generalized Fan Graph

Before solving the subtree generating functions of generalized fan graphs and generalized wheel graphs, we firstly introduce and solve the subtree generating function computing problem of the two-tailed generalized fan graphs. Firstly, we employ the convention that∪t=ije¯t,1=∅(j<i).Definition 6.
Denote byF¯n,ii=1,2,3,…,n the generalized fan graph of Fn\ei−1,mi−1+1∪∪j=1i−1e¯j,1 that contains c0 and ci; moreover, define Pci,cn the path tree of F¯n,i\∪r=ine¯r,lr+1 that contains vertex ci.With structural analysis and equations (9) and (13), we can obtain the following lemma.Lemma 6.
Keeping above symbols and definitions, we have(17)FF¯n,i;f,g;c0,Pci,cn=∑t=inyzlt+1+∑j=in−1mj+1yn−i−1∑p=1lt+1pypzp−1∏j=in∑p=1lj+1pypzp−1.Definition 7.
DefineF˜a,bili,…,ln;mi,…,mn−1(or simply F˜a,bn,ii=1,…,n) the two-tailed generalized fan graph obtained from F¯n,ii=1,2,3,…,n by attaching a path Pa+1′=v0′v1′v2′…va′ to vertex ci and path Pb+1″=vo″v1″v2″…vb″, to vertex cn, respectively, where ci=v0′ and cn=v0″ (see Figure 1 for an illustration).(i)
Denote byFa,bn,ii=1,2,…,n the k regular two-tailed generalized fan graph with li=mj=ki=1,…,n;j=1,…,n−1;k≥0.(ii)
Denote byT˜a,bn,i=F˜a,bn,i\c0 and Ta,bn,i=Fa,bn,i\c0i=1,2,3,…,n the two weighted trees.Figure 1
Two-tailed generalized fan graphF˜1,14,ii=1,2,3,4. (a) F˜1,14,1. (b) F˜1,14,2. (c) F˜1,14,3. (d) F˜1,14,4.
(a)(b)(c)(d)Lemma 7.
LetF˜a,bn,i=VF˜a,bn,i,EF˜a,bn,i;f,gi=1,2,…,n be a weighted two-tailed generalized fan graph, with fv=yv∈VF˜a,bn,i and ge=ze∈EF˜a,bn,i, respectively; then,(18)FF˜a,bn,i;f,g;c0=1y2∑t=in−1FF¯n,t+1;f,g;c0,Pct+1,cn∑j=t/n−1mtFF˜a,mt−jt,i;f,g;c0yzj⋅∑j=1b+1yjzj−1+∑k=1a+1yzk−1FF¯n,i;f,g;c0,Pci,cn∑k=1b+1yzk−1+FF˜a,mn−1n−1,i;f,g;c0∑k=1ln+b+2yzk−1,with FF¯n,i;f,g;c0,Pci,cn as in equation (17) and FF˜a,bi,i;f,g;c0=∑t=1li+1ytzt−1+ylizli+1∑t=1a+1ytzt−1∑t=1b+1ytzt−1.Proof.
We categorize the subtrees ofF˜a,bn,i containing c0 into four cases:(19)SF˜a,bn,i;c0=S¯1∪S¯2∪S¯3∪S¯4,where(i)
S¯1 is the set of subtrees in SF˜a,bn,i;c0 that does not contain edge en−1,mn−1+1.(ii)
S¯2 is the set of subtrees in SF˜a,bn,i;c0 that contains edge set ∪k=mn−1+1−jmn−1+1en−1,k, but not edge en−1,mn−1−jj=0,1,…,mn−1−1.(iii)
S¯3 is the set of subtrees in SF˜a,bn,i;c0 that contains edge set ∪k=n−pn−1∪j=1mk+1ek,j∪∪j=mn−1−p+2−qmn−1−p+1en−1−p,j, but not edge en−p−1,mn−1−p−q+1p=1,2,…,n−i−1;q=0,1,…,mn−p−1.(iv)
S¯4 is the set of subtrees in SF˜a,bn,i;c0 that contains edge set ∪k=in−1∪j=1mk+1ek,j.
For the caseS¯1, we define path tree P¯ln+b+2=c0vn,1vn,2…vn,lncnPb+1″, and it is not difficult to obtain(20)∑T1∈S¯1wT1=1yFP¯ln+b+2;f,g;c0×FF˜a,mn−1n−1,i;f,g;c0=FF˜a,mn−1n−1,i;f,g;c0∑j=1ln+b+2yzj−1.
For the caseS¯2, with structural analysis and equation (17), we obtain(21)∑T2∈S¯2wT2=1y2∑j=1mn−1FF˜a,mn−1−jn−1,i;f,g;c0FF¯n,n;f,g;c0,Pcn,cn∏k=1jfvn−1,mn−1−k+1∗gen−1,mn−1−k+2FPb+1″;f,g;cn1y2∑j=1mn−1FF˜a,mn−1−jn−1,i;f,g;c0yln+2zln+1yzj∑j=1b+1yjzj−1.
Similar to analysis of caseS¯2, we can obtain(22)∑T3∈S¯3wT3=1y2∑t=in−2FF¯n,t+1;f,g;c0,Pct+1,cn∑j=0mtFF˜a,mt−jt,i;f,g;c0∏p=1jfvt,mt−p+1∗get,mt−p+2FPb+1″;f,g;cn=1y2∑t=in−2FF¯n,t+1;f,g;c0,Pct+1,cn∑j=0mtyzjFF˜a,mt−jt,i;f,g;c0∑k=1b+1ykzk−1.
For the caseS¯4, with equations (5) and (17), we can get(23)∑T4∈S¯4wT4=FF¯n,i;f,g;c0,Pci,cnFPa+1′;f,g;ciFPb+1″;f,g;cny2=FF¯n,i;f,g;c0,Pci,cn∑k=1a+1yzk−1×∑k=1b+1yzk−1.
Clearly,F˜a,bi,i is a trivial tree, and by Lemma 1, we can get(24)∑T∈SF˜a,bi,i;c0=∑t=1li+1ytzt−1+ylizli+1×∑t=1a+1ytzt−1×∑t=1b+1ytzt−1.
Combining equations (20)–(24), we can obtain equation (18), and thus the lemma is proved.
With Lemmas1 and 7, we can obtain the subtree generating function of generalized fan graphs.Theorem 2.
LetFn=VFn,EFn;f,g be a weighted generalized fan graph, with fv=yv∈VFn and ge=ze∈EFn; then,(25)FFn;f,g=FF˜0,0n,1;f,g;c0+FT˜0,0n,1;f,g,with FF˜a,bn,i;f,g;c0a,b≥0;1≤i≤n as in equation (18).(26)FT˜a,bn,i;f,g=∑k=1b+1yzk∑k=1ln+1yzk−1FT˜a,mn−1n−1,i;f,g−FT˜a,mn−1−1n−1,i;f,g+FT˜a,mn−1n−1,i;f,g+∑k=1ln+b+1ln+b−k+2ykzk−1,and FT˜a,bi,i;f,g=∑k=0b−1b−kyk+1zk+∑k=0a−1a−kyk+1zk+∑k=0li−1li−kyk+1zk+∑k=1a+1yzk−1, ×∑k=1li+1ykzk−1×∑k=1b+1yzk−1a,b≥0;1≤i≤n.Next, we discuss some special cases of the generalized fan graphs.Definition 8.
LetFl1,…,ln;m1,…,mn−1 be a generalized fan graph and k be a positive integer; if li=mj=ki=1,…,n;j=1,…,n−1, then the generalized fan graph is called the k regular fan graph, denoted by Fn,kn≥3;k≥0. Obviously, Fn,k has 2n−1k+n+1 vertices and 2n−1k+1 edges.From Theorem2, the following corollaries follow as immediate consequences.Corollary 4.
LetFn,k=VFn,k,EFn,k;f,g be a weighted k regular fan graph, with fv=yv∈VFn,k and ge=ze∈EFn,k; then,(27)FFn,k;f,g=FF0,0n,1;f,g;c0+FT0,0n,1;f,g,with(28)FFa,bn,i;f,g;c0=∑t=in−1n−tyn−t∑j=t/n−1kFFa,k−jt,i;f,g;c0yzk+1n−t+j×∑j=1b+1yjzj−1∑j=1k+1jyjzj−1n−t+FFa,kn−1,i;f,g;c0∑j=1k+b+2yzj−1+n−i+1yn−i−1yzk+1n−i+1∑j=1k+1jyjzj−1n−i∑j=1a+1yzj−1∑j=1b+1yzj−1,and FFa,bi,i;f,g;c0=∑t=1k+1ytzt−1+ykzk+1∑t=1a+1ytzt−1∑t=1b+1ytzt−1a,b≥0;1≤i≤n.(29)FTa,bn,i;f,g=∑j=1b+1yzj∑j=1k+1yzj−1FTa,kn−1,i;f,g−FTa,k−1n−1,i;f,g+FTa,kn−1,i;f,g+∑j=1k+b+1k+b−j+2yjzj−1,and FTa,bi,i;f,g=∑j=0b−1b−jyj+1zj+∑j=0a−1a−jyj+1zj+∑j=0k−1k−jyj+1zj, +∑j=1a+1yzj−1∑j=1k+1yjzj−1∑j=1b+1yzj−1a,b≥0;1≤i≤n.By substitutingy=1,z=1 into equations (25) and (27), we have the corresponding subtree number indices.Corollary 5.
The subtree number index of the generalized fan graphFn is(30)STNFn=FFn;1,1=STNF˜0,0n,1;c0+STNT˜0,0n,1,with(31)STNF˜a,bn,i;c0=b+1∑t=in−1STNF¯n,t+1;c0,Pct+1,cn∑j=t/n−1mtSTNF˜a,mt−jt,i;c0+a+1STNF¯n,i;c0,Pci,cn+STNF˜a,mn−1n−1,i;c0ln+b+2,and STNF¯n,i;c0,Pci,cn=∑t=in∏j=inlj+1lj+2/2n−ilt+1lt+2, STNF˜a,bi,i;c0=a+1b+1+li+1a,b≥0;1≤i≤n.(32)STNT˜a,bn,i=b+1ln+1STNT˜a,mn−1n−1,i−STNT˜a,mn−1−1n−1,i+STNT˜a,mn−1n−1,i+12ln+b+1ln+b+2,and STNT˜a,bi,i=1/2aa+1+bb+1+lili+1+a+1b+1li+1a,b≥0;1≤i≤n.Corollary 6.
The subtree number index of thek regular fan graph Fn,k is(33)STNFn,k=FFn,k;1,1=STNF0,0n,1;c0+STNT0,0n,1,with(34)STNFa,bn,i;c0=b+1∑t=in−1n−t∑j=t/n−1kSTNFa,k−jt,i;c0k2+3k+2n−t2n−t+a+1n−i+1k2+3k+2n−i2n−i+STNFa,kn−1,i;c0k+b+2,and STNF˜a,bi,i;c0=a+1b+1+k+1a,b≥0;1≤i≤n.(35)STNTa,bn,i=b+1k+1STNTa,kn−1,i−STNTa,k−1n−1,i+STNTa,kn−1,i+12k+b+1k+b+2,and STNTa,bi,i=1/2aa+1+bb+1+kk+1+a+1b+1k+1a,b≥0;1≤i≤n.By Corollary6, we can get the number of subtrees in Fn,kn=3,4,…,12;k=0,1,…,4 as shown in Table 2.Table 2
The subtree number indexSTNFn,k of Fn,kn=3,…,12;k=0,…,4.
nSTNFn,0STNFn,1STNFn,2STNFn,3STNFn,43252379422590577547018781488968434229620520416416258651196301497938906616148251458335557021154421194660719011350654815245591659516014181330985558593212331656145107826248312035578780774946200918605112645497258312326551406527479494336192848875951058480102909280245984150402640949040340498144761187561024011183982940168983681860170621321192173807684958623326967706297601257902785893370743145726106717904347084697946210982683982668276977405


### 3.3. Subtree Generating Functions of Unicyclic Graphs

In order to solve the subtree generating function of the generalized wheel graphs, we first study the subtree generating function of the unicyclic graphs.Lemma 8 (see [14]).
LetT be a weighted tree with more than 2 vertices, u and v be its two distinct vertices, and Puv be a path of T connecting u and v with length l, vertex set VPuv=xi|i=1,2,…,l−1∪u,v, and EPuv=u,x1∪xi,xi+1|i=1,2,…,l−2∪xl−1,v; moreover, denote by Tu,Tv,Txii=1,2,…,l−1 the weighted tree of T\EPuv that contains u,v,xi, respectively. Then,(36)FT;f,g;u,v=fufv∏i=1l−1fxi∏e∈EPuvge,where fv˜=FTv˜;f,g;v˜v˜∈u,v,xii=1,…,l−1.Theorem 3.
LetUn=VUn,EUn;f,g be a weighted unicyclic graph with girth n, vertex set VUn=v1,v2,…,vn, vertex weight function fv=yv∈VUn, and edge weight function ge=ze∈EUn, having trees Tii=1,2,…,n attached to vertex vi on the cycle; then,(37)FUn;f,g=∑i=1n−1∑j=1n∏k=jj+iFTk;f,g;vk∏e∈EPvjvj+ige+∑i=1nFTi;f,g,where Pvjvj+i=vjvj+1vj+2…vj+i is the path connecting vj and vj+i; here we specify that Ti+n=Ti,vi+n=vi.Proof.
The theorem holds through dividing the subtrees ofUn into the following three categories:(1)
Containing no vertex and no edge on the cycle.(2)
Containing only one vertex and no edge on the cycle.(3)
Containing onlyi+1 vertices and i edges i=1,…,n−1 on the cycle.


### 3.4. Subtree Generating Function of the Generalized Wheel Graphs

Next, we consider the subtree generating function of the generalized wheel graphWn.Definition 9.
LetF¯p,qnp,q∈1,2,…,n be the generalized fan graph of Wnep−1,mp−1+1∗∪eq,1∗∪∪i=q+1p−1e˜i,1 that contains c0,cp,cq, and denote by Pcp,cq′ the path tree of F¯p,qn\∪i=pqe˜i,li+1 that contains cp,cq.With Lemma6, the following lemma follows immediately.Lemma 9.
Keeping above symbols and definitions, we have(38)FF¯p,qn;f,g;c0,Pcp,cq′=∑i=pxyzli+1+∑k=px−1mk+1yx−p−1∑j=1li+1jyjzj−1∏j=px∑k=1lj+1kykzk−1,with(39)x=q,ifq≥p,n+q,otherwise.Theorem 4.
LetWn=VWn,EWn;f,g be a weighted generalized wheel graph with vertex weight function fv=yv∈VWn and edge weight function ge=ze∈EWn (see Definition 4); then,(40)FWn;f,g=∑p=1n∑k=p/nmp1y∑i=1p−1∑j=0miyzk+jFF¯p+1,in;f,g;c0,Pcp+1,ci′×FF˜mi−j,mp−kp,i+1;f,g;c0+FF¯p+1,pn;f,g;c0,Pcp+1,cp′∑i=0mp−kyzk+i+∑i=1n∑j=i/nmiyzj∑k=0m1−jyzk1−i−1/nFT˜0,mi−ji,1;f,g−FT˜m1,mi−ji,2;f,g−∑k=0l1−1l1−kyk+1zki−1/n∏j=i+i−1/nn∑t=1lj+1ytzt−1∏j=i+1nymjzmj+1+FT˜0,mnn,1;f,g+FF˜0,mnn,1;f,g;c0,with FT˜a,bn,i;f,g;c0, FT˜a,bn,i;f,g, FF¯p,qn;f,g;c0,Pcp,cq′ as in equations (18), (26), and (38), respectively, and F¯i+n,qn=F¯i,qn1,2,…,n.Proof.
We first divide the subtrees of generalized wheel graph into two categories:(1)
Not containing the center vertexc0.(2)
Containing the center vertexc0.
Obviously,Wn\c0 is a unicyclic graph; with Theorem 3, we have the subtree generating function of case (1) as(41)FWn\c0;f,g=∑i=1n∑j=i/nmiyzjFT˜0,mi−ji,1;f,g−FT˜m1,mi−ji,2;f,g−∑k=0l1−1l1−kyk+1zki−1/n∑k=0m1−jyzk1−i−1/n∏j=i+1nymjzmj+1∏j=i+i−1/nn∑t=1lj+1ytzt−1+FT˜0,mnn,1;f,g.
We further partition the subtree of case (2) into four categories.(42)SWn;c0=S1∪S2∪S3∪S4,where(i)
S1 is the set of subtrees in SWn;c0 that does not contain edge en,mn+1∗.(ii)
S2 is the set of subtrees in SWn;c0 that contains edge set ∪j=mn+1−imn+1en,j∗, but not en,mn−i∗i=0,1,…,mn−1.(iii)
S3 is the set of subtrees in SWn;c0 that contains edge set ∪i=n−p+1n∪j=1mi+1ei,j∗∪∪j=mn−p+2−qmn−p+1en−p,j∗, but not en−p,mn−p−q+1∗p=1,2,…,n−2;q=0,1,…,mn−p.(iv)
S4 is the set of subtrees in SWn;c0 that contains edge set ∪i=2n∪j=1mi+1ei,j∗∪∪j=m1+2−qm1+1e1,j∗, but not e1,m1−q+1∗q=0,1,…,m1.With equation (18), we have the subtree generating function of case S1 as(43)∑T1∈S1wT1=FF˜0,mnn,1;f,g;c0.We further categorize the subtrees in setS2 into two cases:(44)S2=S2,1∪S2,2.(v)
S2,1 is the set of subtrees in S2 that contains edge set ∪i=1p−1∪j=1mi+1ei,j∗∪∪j=1q−1ep,j∗p=1,2,…,n−1;q=1,2,…,mp+1, but not ep,q∗.(vi)
S2,2 is the set of subtrees in S2 that contains edge set ∪i=1n−1∪j=1mi+1ei,j∗.
Then, we have(45)∑T2∈S2wT2=∑p=1mn∏j=1pfvn,mn−j+1∗gen,mn−j+2∗∑T2,1∈S2,1wT2,1+∑T2,2∈S2,2wT2,2=∑p=1mnyzpy∑j=1n−1FF¯1,jn;f,g;c0,Pc1,cj′∑i=0mjFF˜mj−i,mn−pn,j+1;f,g;c0∏s=1ifvj,s∗gej,s∗+FF¯1,nn;f,g;c0,Pc1,cn′×FPmn+1−p″;f,g;cn=∑p=1mnyp−1zp∑j=1n−1FF¯1,jn;f,g;c0,Pc1,cj′∑i=0mjyziFF˜mj−i,mn−pn,j+1;f,g;c0+FF¯1,nn;f,g;c0,Pc1,cn′∑q=1mn+1−pyqzq−1.
Similar to the analysis of caseS2, we have(46)∑T3∈S3wT3=1y∑p=2n−1∑k=0mp∏j1=1kfvp,mp−j1+1∗gep,mp−j1+2∗∑i=1p−1FF¯p+1,in;f,g;c0,Pcp+1,ci′∑j=0miFF˜mi−j,mp−kp,i+1;f,g;c0∏s=1jfvi,s∗gei,s∗+FF¯p+1,pn;f,g;c0,Pcp+1,cp′FPmp+1−k″;f,g;cp=∑p=2n−1∑k=0mpyk−1zk∑i=1p−1FF¯p+1,in;f,g;c0,Pcp+1,ci′∑j=0miFF˜mi−j,mp−kp,i+1;f,g;c0yzj+FF¯p+1,pn;f,g;c0,Pcp+1,cp′∑q=1mp+1−kyqzq−1,(47)∑T4∈S4wT4=1yFF¯2,1n;f,g;c0,Pc2,c1′∑p=0m1∏i=1pfv1,m1−i+1∗gv1,m1−i+2∗FPm1+1−p″;f,g;c1=FF¯2,1n;f,g;c0,Pc2,c1′∑p=0m1yp−1zp×∑j=1m1+1−pyjzj−1.
Equation (40) follows from equations (41) to (47).With Theorem4, we can also obtain the subtree generating functions of some special generalized wheel graphs.Definition 10.
LetWl1,…,ln;m1,…,mn be a generalized wheel graph and k be a positive integer; the generalized wheel graph is called k regular wheel graph, denoted by Wn,kn≥3;k≥0, if li=mi=ki=1,…,n. Clearly, Wn,k has n2k+1+1 vertices and 2nk+1 edges.Corollary 7.
LetWn,k=VWn,k,EWn,k;f,g be a weighted k regular wheel graph, with fv=yv∈VWn,k and ge=ze∈EWn,k; then,(48)FWn,k;f,g=FF0,kn,1;f,g;c0+ykzk+1n−1∑i=0k∑j=0k−iyzi+j∑j=1k+1yjzj−1n+∑p=1n∑t=p/nk∑i=1p−1n−p+iyn−p+i−1∑j=0kFFk−j,k−tp,i+1;f,g;c0yzk+1n−p+i+t+j×∑s=1k+1syszs−1n−p+i−1+nyznk+1yn−2∑s=1k+1syszs−1n−1∑i=0k−tyzt+i+∑i=2n∑j=i/nkyzjFT0,k−ji,1;f,g−FTk,k−ji,2;f,g−∑t=0k−1k−tyt+1zt×ykzk+1∑t=1k+1ytzt−1n−i+FT0,kn,1;f,g,with FFa,bn,i;f,g;c0 and FTa,bn,i;f,g as in equations (28) and (29), respectively.Substitutingy=1,z=1 into equations (40) and (48), we have the following corollaries.Corollary 8.
The subtree number index of generalized wheel graphWn is(49)STNWn=∑p=1n∑k=p/nmp∑i=1p−1∑j=0miSTNF¯p+1,in;c0,Pcp+1,ci′STNF˜mi−j,mp−kp,i+1;c0+STNF¯p+1,pn;c0,Pcp+1,cp′mp−k+1+STNT˜0,mnn,1+STNF˜0,mnn,1;c0+∑i=1n∑j=i/nmiSTNT˜0,mi−ji,1−STNT˜m1,mi−ji,2−l12l1+1i−1/n×m1−j+11−i−1/n∏j=i+i−1/nnlj+1,with STNF˜a,bn,i;c0, STNT˜a,bn,i as in equations (31) and (32), respectively, and STNF¯p+1,in;c0,Pcp+1,ci′=FF¯p+1,in;1,1;c0,Pcp+1,ci′ by substituting y=z=1 into equation (38).Corollary 9.
The subtree number index of thek regular wheel graph Wn,k is(50)STNWn,k;f,g=STNT0,kn,1+∑p=1n∑t=p/nk∑i=1p−1n−p+i∑j=0kSTNFk−j,k−tp,i+1;c0k2+3k+2n−p+i−12n−p+i−1+n2n−1k+1−tk2+3k+2n−1+∑i=2n∑j=i/nkSTNT0,k−ji,1−STNTk,k−ji,2−k2k+1k+1n−i+STNF0,kn,1;c0+k+22k+1n+1,with STNF˜a,bn,i;c0 and STNF˜a,bn,i as in equations (34) and (35), respectively.With Corollary9, we can get the subtree number index of the k regular wheel graph Wn,kn=3,…,10;k=0,…,4 as shown in Table 3.Table 3
The subtree number indexSTNWn,k of the k regular wheel graphs Wn,kn=3,…,10;k=0,1,…,4.
nSTNWn,0STNWn,1STNWn,2STNWn,3STNWn,4338854601225508808104112722110113971372833880805332642451784919207938841468288506100758266831779252607320008635278899573110531415356617160117710247828274109511640897044853396510083174375515947702112118120257811609304314433865141795306604401502471767646050875514697255510956434050782145319618608483343746094009778421908623666992075


## 3.1. Subtree Generating Function for Generalized Book Graphs

Before deriving the subtree generating function for generalized book graphs, we first introduce some lemmas.Lemma 2 (see [14]).
LetPn=VPn,EPn;f,g be a weighted path on n vertices, with VPn=v0,v1,…,vn−1, EPn=vi,vi+1|i=0,1,…,n−2, fv=yv∈VPn and ge=ze∈EPn; then,(4)FPn;f,g=∑i=0n−1n−iyi+1zi,(5)FPn;f,g;v0=∑i=0n−1yi+1zi.Lemma 3 (see [15]).
LetG′=VG′,EG′;f,g be a weighted graph with the common edge u,v, fv=yv∈VG′, ge=ze∈EG′, VG′=VG1′∪VG2′, and EG′=EG1′∪EG2′, G1′∩G2′=u,v, where G1′, G2′ are two weighted graphs; then,(6)FG′;f,g=FG1′;f,g;u,vFG2′;f,g;u,vy2z+FG′\u,v;f,g.Lemma 4 (see [16]).
LetUn=VUn,EUn;f,g be a weighted unicyclic graph with VUn=v1,v2,…,vn, EUn=vi,vi+1|i=1,2,…,n(where vn+1=v1), fv=yv∈VUn, and ge=ze∈EUn, respectively; then, for any fixed vertex vi∈VUn and any continuous k edge set ∪j=1kvi+j−1,vi+jk=1,2,…,n−1, we have(7)FUn;f,g;vi=∑i=1niyizi−1,(8)FUn;f,g;∪j=1kvi+j−1,vi+j=∑i=1n−kiyi+kzi+k−1.The following Lemma follows from Lemmas1 and 2.Lemma 5.
LetKn=VKn,EKn;f,g be a weighted generalized star tree, with fv=yv∈VKn and ge=ze∈EKn; then,(9)FKn;f,g=1yn−1∏i=1n∑j=1li+1yjzj−1+∑i=1n∑j=1lili−j+1yjzj−1.Theorem 1.
LetBn=VBn,EBn;f,g be an n-page weighted generalized book graph, with fv=yv∈VBn and ge=ze∈EBn; then,(10)FBn;f,g=∑i=0nyli+2zli+11−n∑k=1li+1kyk+li+1zk+li∏j=0n∑k=1lj+1kyk+li+1zk+li+2yn∏i=0n∑j=1li+1yjzj−1+∑i=0n∑j=1lili−j+1yjzj−1.Proof.
We divide the subtrees of generalized book graphBn into four categories:(1)
Containingu but not v.(2)
Containingv but not u.(3)
Containing neitheru nor v.(4)
Containing bothu and v.
With structural analysis and Lemma5, we have the subtree generating function of cases (1) and (2) as(11)1yn∏i=0n∑j=1li+1yjzj−1.
With Lemma1, it is easy to see that the subtree generating function of case (3) is(12)∑i=0n∑j=1lili−j+1yjzj−1.
Denote byPuvi=uwi,1wi,2…wi,livi=0,1,2,…,n the path connecting the vertex pair u,v, and Uli+lj+2i,j=Puviwj,lj…wj,2wj,1uj≠i,j∈0,1,…,n an unicyclic graph. With structural analysis, equation (8) in Lemma 4, and Lemma 3, we have the subtree generating function of case (4) as(13)∑i=0n∏0≤j≠i≤nFUli+lj+2i,j;f,g;Puviyli+2zli+1n−1.
The theorem follows from equations (11)–(13).We can further obtain the subtree generating function of special generalized book graphs.Definition 5.
LetBl0,l1,…,ln be an n-page generalized book graph and k be a positive integer; we call Bl0,l1,…,ln an n-page k regular book graph, denoted by Bn,kn≥2, if the lengths of its n+1 internally disjoint paths are all equal to k(namely, li=ki=0,1,…,n). Obviously, Bn,kn≥2 has n+1k+2 vertices and n+1k+1 edges.With Theorem1, it is not difficult to obtain the following corollary.Corollary 1.
LetBn,k=VBn,k,EBn,k;f,g be an n-page k regular book graph, with fv=yv∈VBn,k and ge=ze∈EBn,k; then,(14)FBn,k;f,g=n+1∑i=0k−1k−iyi+1zi+2yn∑i=1k+1yizi−1n+1+n+1yk+2zk+1n−1∑i=1k+1iyi+k+1zi+kn.By substitutingy=1,z=1 into equations (10) and (14), we have the corresponding subtree number indices.Corollary 2.
The subtree number index of then-page generalized book graph Bn is(15)STNBn=2∏i=0nli+1+∑i=0n∑j=0li−1li−j+∑i=0n∏j=0nlj+1lj+22nli+1li+2.Corollary 3.
The subtree number index of then-page k regular book graph Bn,k is(16)STNBn,k=n+1kk+12+2k+1n+1+n+1k2+3k+2n2n.With Corollary3, we have the subtree number index of the Bn,k as illustrated in Table 1.Table 1
The subtree number indexSTNBn,k of the n-page k regular book graph Bn,kk=1,2,…,5;n=2,3,…,11.
nSTNBn,1STNBn,2STNBn,3STNBn,4STNBn,524617144695518003144103845361479039696447469815207825942598803251592481326082284587560245980086536633098770328107989069560092282471801622526348013112013676563301441206768086008215155937900524342230699219653404258897769198888100895088100020972123844531251007942921398312106536466654822631100083886746343251953235183479416354488112133968435462759012000335545041037975585938704203334360071504


## 3.2. Subtree Generating Function of Two-Tailed Generalized Fan Graph

Before solving the subtree generating functions of generalized fan graphs and generalized wheel graphs, we firstly introduce and solve the subtree generating function computing problem of the two-tailed generalized fan graphs. Firstly, we employ the convention that∪t=ije¯t,1=∅(j<i).Definition 6.
Denote byF¯n,ii=1,2,3,…,n the generalized fan graph of Fn\ei−1,mi−1+1∪∪j=1i−1e¯j,1 that contains c0 and ci; moreover, define Pci,cn the path tree of F¯n,i\∪r=ine¯r,lr+1 that contains vertex ci.With structural analysis and equations (9) and (13), we can obtain the following lemma.Lemma 6.
Keeping above symbols and definitions, we have(17)FF¯n,i;f,g;c0,Pci,cn=∑t=inyzlt+1+∑j=in−1mj+1yn−i−1∑p=1lt+1pypzp−1∏j=in∑p=1lj+1pypzp−1.Definition 7.
DefineF˜a,bili,…,ln;mi,…,mn−1(or simply F˜a,bn,ii=1,…,n) the two-tailed generalized fan graph obtained from F¯n,ii=1,2,3,…,n by attaching a path Pa+1′=v0′v1′v2′…va′ to vertex ci and path Pb+1″=vo″v1″v2″…vb″, to vertex cn, respectively, where ci=v0′ and cn=v0″ (see Figure 1 for an illustration).(i)
Denote byFa,bn,ii=1,2,…,n the k regular two-tailed generalized fan graph with li=mj=ki=1,…,n;j=1,…,n−1;k≥0.(ii)
Denote byT˜a,bn,i=F˜a,bn,i\c0 and Ta,bn,i=Fa,bn,i\c0i=1,2,3,…,n the two weighted trees.Figure 1
Two-tailed generalized fan graphF˜1,14,ii=1,2,3,4. (a) F˜1,14,1. (b) F˜1,14,2. (c) F˜1,14,3. (d) F˜1,14,4.
(a)(b)(c)(d)Lemma 7.
LetF˜a,bn,i=VF˜a,bn,i,EF˜a,bn,i;f,gi=1,2,…,n be a weighted two-tailed generalized fan graph, with fv=yv∈VF˜a,bn,i and ge=ze∈EF˜a,bn,i, respectively; then,(18)FF˜a,bn,i;f,g;c0=1y2∑t=in−1FF¯n,t+1;f,g;c0,Pct+1,cn∑j=t/n−1mtFF˜a,mt−jt,i;f,g;c0yzj⋅∑j=1b+1yjzj−1+∑k=1a+1yzk−1FF¯n,i;f,g;c0,Pci,cn∑k=1b+1yzk−1+FF˜a,mn−1n−1,i;f,g;c0∑k=1ln+b+2yzk−1,with FF¯n,i;f,g;c0,Pci,cn as in equation (17) and FF˜a,bi,i;f,g;c0=∑t=1li+1ytzt−1+ylizli+1∑t=1a+1ytzt−1∑t=1b+1ytzt−1.Proof.
We categorize the subtrees ofF˜a,bn,i containing c0 into four cases:(19)SF˜a,bn,i;c0=S¯1∪S¯2∪S¯3∪S¯4,where(i)
S¯1 is the set of subtrees in SF˜a,bn,i;c0 that does not contain edge en−1,mn−1+1.(ii)
S¯2 is the set of subtrees in SF˜a,bn,i;c0 that contains edge set ∪k=mn−1+1−jmn−1+1en−1,k, but not edge en−1,mn−1−jj=0,1,…,mn−1−1.(iii)
S¯3 is the set of subtrees in SF˜a,bn,i;c0 that contains edge set ∪k=n−pn−1∪j=1mk+1ek,j∪∪j=mn−1−p+2−qmn−1−p+1en−1−p,j, but not edge en−p−1,mn−1−p−q+1p=1,2,…,n−i−1;q=0,1,…,mn−p−1.(iv)
S¯4 is the set of subtrees in SF˜a,bn,i;c0 that contains edge set ∪k=in−1∪j=1mk+1ek,j.
For the caseS¯1, we define path tree P¯ln+b+2=c0vn,1vn,2…vn,lncnPb+1″, and it is not difficult to obtain(20)∑T1∈S¯1wT1=1yFP¯ln+b+2;f,g;c0×FF˜a,mn−1n−1,i;f,g;c0=FF˜a,mn−1n−1,i;f,g;c0∑j=1ln+b+2yzj−1.
For the caseS¯2, with structural analysis and equation (17), we obtain(21)∑T2∈S¯2wT2=1y2∑j=1mn−1FF˜a,mn−1−jn−1,i;f,g;c0FF¯n,n;f,g;c0,Pcn,cn∏k=1jfvn−1,mn−1−k+1∗gen−1,mn−1−k+2FPb+1″;f,g;cn1y2∑j=1mn−1FF˜a,mn−1−jn−1,i;f,g;c0yln+2zln+1yzj∑j=1b+1yjzj−1.
Similar to analysis of caseS¯2, we can obtain(22)∑T3∈S¯3wT3=1y2∑t=in−2FF¯n,t+1;f,g;c0,Pct+1,cn∑j=0mtFF˜a,mt−jt,i;f,g;c0∏p=1jfvt,mt−p+1∗get,mt−p+2FPb+1″;f,g;cn=1y2∑t=in−2FF¯n,t+1;f,g;c0,Pct+1,cn∑j=0mtyzjFF˜a,mt−jt,i;f,g;c0∑k=1b+1ykzk−1.
For the caseS¯4, with equations (5) and (17), we can get(23)∑T4∈S¯4wT4=FF¯n,i;f,g;c0,Pci,cnFPa+1′;f,g;ciFPb+1″;f,g;cny2=FF¯n,i;f,g;c0,Pci,cn∑k=1a+1yzk−1×∑k=1b+1yzk−1.
Clearly,F˜a,bi,i is a trivial tree, and by Lemma 1, we can get(24)∑T∈SF˜a,bi,i;c0=∑t=1li+1ytzt−1+ylizli+1×∑t=1a+1ytzt−1×∑t=1b+1ytzt−1.
Combining equations (20)–(24), we can obtain equation (18), and thus the lemma is proved.
With Lemmas1 and 7, we can obtain the subtree generating function of generalized fan graphs.Theorem 2.
LetFn=VFn,EFn;f,g be a weighted generalized fan graph, with fv=yv∈VFn and ge=ze∈EFn; then,(25)FFn;f,g=FF˜0,0n,1;f,g;c0+FT˜0,0n,1;f,g,with FF˜a,bn,i;f,g;c0a,b≥0;1≤i≤n as in equation (18).(26)FT˜a,bn,i;f,g=∑k=1b+1yzk∑k=1ln+1yzk−1FT˜a,mn−1n−1,i;f,g−FT˜a,mn−1−1n−1,i;f,g+FT˜a,mn−1n−1,i;f,g+∑k=1ln+b+1ln+b−k+2ykzk−1,and FT˜a,bi,i;f,g=∑k=0b−1b−kyk+1zk+∑k=0a−1a−kyk+1zk+∑k=0li−1li−kyk+1zk+∑k=1a+1yzk−1, ×∑k=1li+1ykzk−1×∑k=1b+1yzk−1a,b≥0;1≤i≤n.Next, we discuss some special cases of the generalized fan graphs.Definition 8.
LetFl1,…,ln;m1,…,mn−1 be a generalized fan graph and k be a positive integer; if li=mj=ki=1,…,n;j=1,…,n−1, then the generalized fan graph is called the k regular fan graph, denoted by Fn,kn≥3;k≥0. Obviously, Fn,k has 2n−1k+n+1 vertices and 2n−1k+1 edges.From Theorem2, the following corollaries follow as immediate consequences.Corollary 4.
LetFn,k=VFn,k,EFn,k;f,g be a weighted k regular fan graph, with fv=yv∈VFn,k and ge=ze∈EFn,k; then,(27)FFn,k;f,g=FF0,0n,1;f,g;c0+FT0,0n,1;f,g,with(28)FFa,bn,i;f,g;c0=∑t=in−1n−tyn−t∑j=t/n−1kFFa,k−jt,i;f,g;c0yzk+1n−t+j×∑j=1b+1yjzj−1∑j=1k+1jyjzj−1n−t+FFa,kn−1,i;f,g;c0∑j=1k+b+2yzj−1+n−i+1yn−i−1yzk+1n−i+1∑j=1k+1jyjzj−1n−i∑j=1a+1yzj−1∑j=1b+1yzj−1,and FFa,bi,i;f,g;c0=∑t=1k+1ytzt−1+ykzk+1∑t=1a+1ytzt−1∑t=1b+1ytzt−1a,b≥0;1≤i≤n.(29)FTa,bn,i;f,g=∑j=1b+1yzj∑j=1k+1yzj−1FTa,kn−1,i;f,g−FTa,k−1n−1,i;f,g+FTa,kn−1,i;f,g+∑j=1k+b+1k+b−j+2yjzj−1,and FTa,bi,i;f,g=∑j=0b−1b−jyj+1zj+∑j=0a−1a−jyj+1zj+∑j=0k−1k−jyj+1zj, +∑j=1a+1yzj−1∑j=1k+1yjzj−1∑j=1b+1yzj−1a,b≥0;1≤i≤n.By substitutingy=1,z=1 into equations (25) and (27), we have the corresponding subtree number indices.Corollary 5.
The subtree number index of the generalized fan graphFn is(30)STNFn=FFn;1,1=STNF˜0,0n,1;c0+STNT˜0,0n,1,with(31)STNF˜a,bn,i;c0=b+1∑t=in−1STNF¯n,t+1;c0,Pct+1,cn∑j=t/n−1mtSTNF˜a,mt−jt,i;c0+a+1STNF¯n,i;c0,Pci,cn+STNF˜a,mn−1n−1,i;c0ln+b+2,and STNF¯n,i;c0,Pci,cn=∑t=in∏j=inlj+1lj+2/2n−ilt+1lt+2, STNF˜a,bi,i;c0=a+1b+1+li+1a,b≥0;1≤i≤n.(32)STNT˜a,bn,i=b+1ln+1STNT˜a,mn−1n−1,i−STNT˜a,mn−1−1n−1,i+STNT˜a,mn−1n−1,i+12ln+b+1ln+b+2,and STNT˜a,bi,i=1/2aa+1+bb+1+lili+1+a+1b+1li+1a,b≥0;1≤i≤n.Corollary 6.
The subtree number index of thek regular fan graph Fn,k is(33)STNFn,k=FFn,k;1,1=STNF0,0n,1;c0+STNT0,0n,1,with(34)STNFa,bn,i;c0=b+1∑t=in−1n−t∑j=t/n−1kSTNFa,k−jt,i;c0k2+3k+2n−t2n−t+a+1n−i+1k2+3k+2n−i2n−i+STNFa,kn−1,i;c0k+b+2,and STNF˜a,bi,i;c0=a+1b+1+k+1a,b≥0;1≤i≤n.(35)STNTa,bn,i=b+1k+1STNTa,kn−1,i−STNTa,k−1n−1,i+STNTa,kn−1,i+12k+b+1k+b+2,and STNTa,bi,i=1/2aa+1+bb+1+kk+1+a+1b+1k+1a,b≥0;1≤i≤n.By Corollary6, we can get the number of subtrees in Fn,kn=3,4,…,12;k=0,1,…,4 as shown in Table 2.Table 2
The subtree number indexSTNFn,k of Fn,kn=3,…,12;k=0,…,4.
nSTNFn,0STNFn,1STNFn,2STNFn,3STNFn,43252379422590577547018781488968434229620520416416258651196301497938906616148251458335557021154421194660719011350654815245591659516014181330985558593212331656145107826248312035578780774946200918605112645497258312326551406527479494336192848875951058480102909280245984150402640949040340498144761187561024011183982940168983681860170621321192173807684958623326967706297601257902785893370743145726106717904347084697946210982683982668276977405


## 3.3. Subtree Generating Functions of Unicyclic Graphs

In order to solve the subtree generating function of the generalized wheel graphs, we first study the subtree generating function of the unicyclic graphs.Lemma 8 (see [14]).
LetT be a weighted tree with more than 2 vertices, u and v be its two distinct vertices, and Puv be a path of T connecting u and v with length l, vertex set VPuv=xi|i=1,2,…,l−1∪u,v, and EPuv=u,x1∪xi,xi+1|i=1,2,…,l−2∪xl−1,v; moreover, denote by Tu,Tv,Txii=1,2,…,l−1 the weighted tree of T\EPuv that contains u,v,xi, respectively. Then,(36)FT;f,g;u,v=fufv∏i=1l−1fxi∏e∈EPuvge,where fv˜=FTv˜;f,g;v˜v˜∈u,v,xii=1,…,l−1.Theorem 3.
LetUn=VUn,EUn;f,g be a weighted unicyclic graph with girth n, vertex set VUn=v1,v2,…,vn, vertex weight function fv=yv∈VUn, and edge weight function ge=ze∈EUn, having trees Tii=1,2,…,n attached to vertex vi on the cycle; then,(37)FUn;f,g=∑i=1n−1∑j=1n∏k=jj+iFTk;f,g;vk∏e∈EPvjvj+ige+∑i=1nFTi;f,g,where Pvjvj+i=vjvj+1vj+2…vj+i is the path connecting vj and vj+i; here we specify that Ti+n=Ti,vi+n=vi.Proof.
The theorem holds through dividing the subtrees ofUn into the following three categories:(1)
Containing no vertex and no edge on the cycle.(2)
Containing only one vertex and no edge on the cycle.(3)
Containing onlyi+1 vertices and i edges i=1,…,n−1 on the cycle.


## 3.4. Subtree Generating Function of the Generalized Wheel Graphs

Next, we consider the subtree generating function of the generalized wheel graphWn.Definition 9.
LetF¯p,qnp,q∈1,2,…,n be the generalized fan graph of Wnep−1,mp−1+1∗∪eq,1∗∪∪i=q+1p−1e˜i,1 that contains c0,cp,cq, and denote by Pcp,cq′ the path tree of F¯p,qn\∪i=pqe˜i,li+1 that contains cp,cq.With Lemma6, the following lemma follows immediately.Lemma 9.
Keeping above symbols and definitions, we have(38)FF¯p,qn;f,g;c0,Pcp,cq′=∑i=pxyzli+1+∑k=px−1mk+1yx−p−1∑j=1li+1jyjzj−1∏j=px∑k=1lj+1kykzk−1,with(39)x=q,ifq≥p,n+q,otherwise.Theorem 4.
LetWn=VWn,EWn;f,g be a weighted generalized wheel graph with vertex weight function fv=yv∈VWn and edge weight function ge=ze∈EWn (see Definition 4); then,(40)FWn;f,g=∑p=1n∑k=p/nmp1y∑i=1p−1∑j=0miyzk+jFF¯p+1,in;f,g;c0,Pcp+1,ci′×FF˜mi−j,mp−kp,i+1;f,g;c0+FF¯p+1,pn;f,g;c0,Pcp+1,cp′∑i=0mp−kyzk+i+∑i=1n∑j=i/nmiyzj∑k=0m1−jyzk1−i−1/nFT˜0,mi−ji,1;f,g−FT˜m1,mi−ji,2;f,g−∑k=0l1−1l1−kyk+1zki−1/n∏j=i+i−1/nn∑t=1lj+1ytzt−1∏j=i+1nymjzmj+1+FT˜0,mnn,1;f,g+FF˜0,mnn,1;f,g;c0,with FT˜a,bn,i;f,g;c0, FT˜a,bn,i;f,g, FF¯p,qn;f,g;c0,Pcp,cq′ as in equations (18), (26), and (38), respectively, and F¯i+n,qn=F¯i,qn1,2,…,n.Proof.
We first divide the subtrees of generalized wheel graph into two categories:(1)
Not containing the center vertexc0.(2)
Containing the center vertexc0.
Obviously,Wn\c0 is a unicyclic graph; with Theorem 3, we have the subtree generating function of case (1) as(41)FWn\c0;f,g=∑i=1n∑j=i/nmiyzjFT˜0,mi−ji,1;f,g−FT˜m1,mi−ji,2;f,g−∑k=0l1−1l1−kyk+1zki−1/n∑k=0m1−jyzk1−i−1/n∏j=i+1nymjzmj+1∏j=i+i−1/nn∑t=1lj+1ytzt−1+FT˜0,mnn,1;f,g.
We further partition the subtree of case (2) into four categories.(42)SWn;c0=S1∪S2∪S3∪S4,where(i)
S1 is the set of subtrees in SWn;c0 that does not contain edge en,mn+1∗.(ii)
S2 is the set of subtrees in SWn;c0 that contains edge set ∪j=mn+1−imn+1en,j∗, but not en,mn−i∗i=0,1,…,mn−1.(iii)
S3 is the set of subtrees in SWn;c0 that contains edge set ∪i=n−p+1n∪j=1mi+1ei,j∗∪∪j=mn−p+2−qmn−p+1en−p,j∗, but not en−p,mn−p−q+1∗p=1,2,…,n−2;q=0,1,…,mn−p.(iv)
S4 is the set of subtrees in SWn;c0 that contains edge set ∪i=2n∪j=1mi+1ei,j∗∪∪j=m1+2−qm1+1e1,j∗, but not e1,m1−q+1∗q=0,1,…,m1.With equation (18), we have the subtree generating function of case S1 as(43)∑T1∈S1wT1=FF˜0,mnn,1;f,g;c0.We further categorize the subtrees in setS2 into two cases:(44)S2=S2,1∪S2,2.(v)
S2,1 is the set of subtrees in S2 that contains edge set ∪i=1p−1∪j=1mi+1ei,j∗∪∪j=1q−1ep,j∗p=1,2,…,n−1;q=1,2,…,mp+1, but not ep,q∗.(vi)
S2,2 is the set of subtrees in S2 that contains edge set ∪i=1n−1∪j=1mi+1ei,j∗.
Then, we have(45)∑T2∈S2wT2=∑p=1mn∏j=1pfvn,mn−j+1∗gen,mn−j+2∗∑T2,1∈S2,1wT2,1+∑T2,2∈S2,2wT2,2=∑p=1mnyzpy∑j=1n−1FF¯1,jn;f,g;c0,Pc1,cj′∑i=0mjFF˜mj−i,mn−pn,j+1;f,g;c0∏s=1ifvj,s∗gej,s∗+FF¯1,nn;f,g;c0,Pc1,cn′×FPmn+1−p″;f,g;cn=∑p=1mnyp−1zp∑j=1n−1FF¯1,jn;f,g;c0,Pc1,cj′∑i=0mjyziFF˜mj−i,mn−pn,j+1;f,g;c0+FF¯1,nn;f,g;c0,Pc1,cn′∑q=1mn+1−pyqzq−1.
Similar to the analysis of caseS2, we have(46)∑T3∈S3wT3=1y∑p=2n−1∑k=0mp∏j1=1kfvp,mp−j1+1∗gep,mp−j1+2∗∑i=1p−1FF¯p+1,in;f,g;c0,Pcp+1,ci′∑j=0miFF˜mi−j,mp−kp,i+1;f,g;c0∏s=1jfvi,s∗gei,s∗+FF¯p+1,pn;f,g;c0,Pcp+1,cp′FPmp+1−k″;f,g;cp=∑p=2n−1∑k=0mpyk−1zk∑i=1p−1FF¯p+1,in;f,g;c0,Pcp+1,ci′∑j=0miFF˜mi−j,mp−kp,i+1;f,g;c0yzj+FF¯p+1,pn;f,g;c0,Pcp+1,cp′∑q=1mp+1−kyqzq−1,(47)∑T4∈S4wT4=1yFF¯2,1n;f,g;c0,Pc2,c1′∑p=0m1∏i=1pfv1,m1−i+1∗gv1,m1−i+2∗FPm1+1−p″;f,g;c1=FF¯2,1n;f,g;c0,Pc2,c1′∑p=0m1yp−1zp×∑j=1m1+1−pyjzj−1.
Equation (40) follows from equations (41) to (47).With Theorem4, we can also obtain the subtree generating functions of some special generalized wheel graphs.Definition 10.
LetWl1,…,ln;m1,…,mn be a generalized wheel graph and k be a positive integer; the generalized wheel graph is called k regular wheel graph, denoted by Wn,kn≥3;k≥0, if li=mi=ki=1,…,n. Clearly, Wn,k has n2k+1+1 vertices and 2nk+1 edges.Corollary 7.
LetWn,k=VWn,k,EWn,k;f,g be a weighted k regular wheel graph, with fv=yv∈VWn,k and ge=ze∈EWn,k; then,(48)FWn,k;f,g=FF0,kn,1;f,g;c0+ykzk+1n−1∑i=0k∑j=0k−iyzi+j∑j=1k+1yjzj−1n+∑p=1n∑t=p/nk∑i=1p−1n−p+iyn−p+i−1∑j=0kFFk−j,k−tp,i+1;f,g;c0yzk+1n−p+i+t+j×∑s=1k+1syszs−1n−p+i−1+nyznk+1yn−2∑s=1k+1syszs−1n−1∑i=0k−tyzt+i+∑i=2n∑j=i/nkyzjFT0,k−ji,1;f,g−FTk,k−ji,2;f,g−∑t=0k−1k−tyt+1zt×ykzk+1∑t=1k+1ytzt−1n−i+FT0,kn,1;f,g,with FFa,bn,i;f,g;c0 and FTa,bn,i;f,g as in equations (28) and (29), respectively.Substitutingy=1,z=1 into equations (40) and (48), we have the following corollaries.Corollary 8.
The subtree number index of generalized wheel graphWn is(49)STNWn=∑p=1n∑k=p/nmp∑i=1p−1∑j=0miSTNF¯p+1,in;c0,Pcp+1,ci′STNF˜mi−j,mp−kp,i+1;c0+STNF¯p+1,pn;c0,Pcp+1,cp′mp−k+1+STNT˜0,mnn,1+STNF˜0,mnn,1;c0+∑i=1n∑j=i/nmiSTNT˜0,mi−ji,1−STNT˜m1,mi−ji,2−l12l1+1i−1/n×m1−j+11−i−1/n∏j=i+i−1/nnlj+1,with STNF˜a,bn,i;c0, STNT˜a,bn,i as in equations (31) and (32), respectively, and STNF¯p+1,in;c0,Pcp+1,ci′=FF¯p+1,in;1,1;c0,Pcp+1,ci′ by substituting y=z=1 into equation (38).Corollary 9.
The subtree number index of thek regular wheel graph Wn,k is(50)STNWn,k;f,g=STNT0,kn,1+∑p=1n∑t=p/nk∑i=1p−1n−p+i∑j=0kSTNFk−j,k−tp,i+1;c0k2+3k+2n−p+i−12n−p+i−1+n2n−1k+1−tk2+3k+2n−1+∑i=2n∑j=i/nkSTNT0,k−ji,1−STNTk,k−ji,2−k2k+1k+1n−i+STNF0,kn,1;c0+k+22k+1n+1,with STNF˜a,bn,i;c0 and STNF˜a,bn,i as in equations (34) and (35), respectively.With Corollary9, we can get the subtree number index of the k regular wheel graph Wn,kn=3,…,10;k=0,…,4 as shown in Table 3.Table 3
The subtree number indexSTNWn,k of the k regular wheel graphs Wn,kn=3,…,10;k=0,1,…,4.
nSTNWn,0STNWn,1STNWn,2STNWn,3STNWn,4338854601225508808104112722110113971372833880805332642451784919207938841468288506100758266831779252607320008635278899573110531415356617160117710247828274109511640897044853396510083174375515947702112118120257811609304314433865141795306604401502471767646050875514697255510956434050782145319618608483343746094009778421908623666992075


## 4. Subtree Density for Graphs

The subtree generating function can be used to reveal more structure information of the graph than just subtree numbers. Next, we study the asymptotic characteristics of the subtree density of three types of graphs, namely,k regular book graph Bn,k, k regular fan graph Fn,k, and k regular wheel graph Wn,k. The formal definition of the subtree density is given below.Definition 11.
(see [12]). Assume G is a graph with n vertices and k subtrees of order n1,n2,…,nk. Then, uG=1/k∑i=1kni denotes the average order of subtrees of G, and the subtree density of G is defined as DG=uG/n.By Definition11, the subtree density of G∗ is simply(51)DG∗=∂FG∗;y,1/∂y|y=1FG∗;1,1×nG∗,where FG∗;y,1 represents the vertex generating function of G∗, FG∗;1,1 represents the number of subtrees of G∗, and nG∗ represents the number of vertices of G∗.


### 4.1. Subtree Density of thek Regular Book Graph

According to definition ofk regular book graph, it is easy to know that the number of vertices in Bn,k is(52)nBn,2=nk+2.With Corollary1, we obtain the vertex generating function of Bn,k:(53)FBn,k;f,1=n+1∑i=0k−1k−iyi+1+2yn∑i=1k+1yin+1+n+1yk+2n−1∑i=1k+1iyi+k+1n.Together with equations (16) and (51), we can obtain the subtree densities of Bn,k as plotted in Figure 2, and the related data are listed in Table 4.Figure 2
Subtree densities ofBn,kn=2,3,…,101;k=1,2,…,100.Table 4
Related data forBn,kn=2,3,…,11;k=1,2,3.
nk=1k=2k=3PyBn,1DBn,1PyBn,2DBn,2PyBn,3DBn,3n=21600.6956529480.69298234340.699959n=36400.74074177380.745472476240.749937n=425240.760699634160.7570076674580.753912n=597520.7657045078940.75372290819800.746593n=6368800.76365639541240.7466541193769020.738012n=71367040.758792299779700.73933115217040160.730391n=84977160.7530862221030080.732726189076022660.724007n=917837680.74739216137304780.7270072300335545320.718704n=1063055120.742052115331357960.72210427501468007500.714269n=11220235840.737177812803580580.717896324006375343280.71052PyBn,k stands for ∂FBn,k;y,1/∂y|y=1n=2,3,…,11;k=1,2,3.Observing Table4 and Figure 2, we see that the B2,100 has the maximal subtree density among Bn,kn=2,3,…,101;k=1,2,…,100. On the whole, it appears that the subtree density of Bn,kn=2,3,…,101;k=1,2,…,100 decreases with the increase of n and k.


### 4.2. Subtree Density of thek Regular Fan Graph

Similarly, with Corollary4, we can obtain the vertex generation function of Fn,k, and combining the subtree density definition (see equation (51)), we can obtain the subtree densities of Fn,k as shown in Table 5 and Figures 3(a) and 3(b).Table 5
Related data forFn,kn=3,4,…,15;k=0,1,2.
nk=0k=1k=2PyFn,0DFn,0PyFn,1DFn,1PyFn,2DFn,2n=3700.714690.68870192300.699879n=42580.737143168040.7456512131120.753336n=59370.7655231886460.76610647703420.768465n=633750.78269920641310.7735121029634910.774643n=7120410.791754220396840.77703721574561120.778349n=8425100.7962462306299620.779261441982708710.780998n=91485590.79849023750472650.7808998899686671360.783027n=105144250.799691241483569520.782189176796911080120.784641n=1117671410.8004142430050626260.7832413474267918909240.785954n=1260287310.8009124246159584150.78411767668829275252530.787045PyFn,k stands for ∂FFn,k;y,/∂y|y=1n=3,4,…,12;k=0,1,2.Figure 3
Subtree densities ofFn,kn=3,4,…,15;k=0,1,…,15. (a) Subtree densities of Fn,kn=3,4,…,15;k=0,1,2. (b) Subtree densities of Fn,kn=3,4,…,15;k=0,1,…,15.
(a)(b)From Figure3(a), when k∈0,1,2 is fixed, we can observe that the subtree density of Fn,k3≤n≤15 gradually increases with the increase of n. As illustrated in Figure 3(b), when n∈3,4,5 is fixed, the subtree density of Fn,k0≤k≤15 also increases with the increase of k.


### 4.3. Subtree Density of thek Regular Wheel Graph

With Corollary7 and equations (50) and (51), we can also obtain the subtree density of Wn,k as shown in Table 6 and Figure 4; here, we skip the repetitive analysis details.Table 6
Related data forWn,kn=3,4,…,10;k=0,1,2.
nk=0k=1k=2PyWn,0DWn,0PyWn,1DWn,1PyWn,2DWn,2n=31160.76315865180.763232747600.777196n=44440.792857745970.79465917010590.800906n=516170.8117478251650.802752373556740.804942n=657890.82125188968440.8036397929918300.80494n=7205190.824719938664210.802885163937515160.804318n=8720640.8251359730311170.8019383322600561990.803706n=92508410.82429499454968740.80109966330828795240.803191n=108659230.8230641005092663450.8003971308556152020330.802768PyWn,k stands for ∂FWn,k;y,1/∂y|y=1n=3,4,…,10;k=0,1,2.Figure 4
Subtree densities ofWn,kn=3,4,…,10;k=0,1,…,12. (a) Subtree densities of Wn,kn=3,4,…,10;k=0,1,…,12. (b) Subtree densities of Wn,kn=3,4,5;k=0,1,…,12.
(a)(b)From Figure4(a), when k∈0,1,2 is fixed, we notice a very interesting observation: the subtree density of Wn,k3≤n≤10 gradually decreases with the increase of n. This trend needs to be further verified through combinatoric approaches. When n∈3,4,5 is fixed, by observing Figure 4(b), it appears that the subtree density of Wn,k0≤k≤12 increases with the increase of k.


## 4.1. Subtree Density of thek Regular Book Graph

According to definition ofk regular book graph, it is easy to know that the number of vertices in Bn,k is(52)nBn,2=nk+2.With Corollary1, we obtain the vertex generating function of Bn,k:(53)FBn,k;f,1=n+1∑i=0k−1k−iyi+1+2yn∑i=1k+1yin+1+n+1yk+2n−1∑i=1k+1iyi+k+1n.Together with equations (16) and (51), we can obtain the subtree densities of Bn,k as plotted in Figure 2, and the related data are listed in Table 4.Figure 2
Subtree densities ofBn,kn=2,3,…,101;k=1,2,…,100.Table 4
Related data forBn,kn=2,3,…,11;k=1,2,3.
nk=1k=2k=3PyBn,1DBn,1PyBn,2DBn,2PyBn,3DBn,3n=21600.6956529480.69298234340.699959n=36400.74074177380.745472476240.749937n=425240.760699634160.7570076674580.753912n=597520.7657045078940.75372290819800.746593n=6368800.76365639541240.7466541193769020.738012n=71367040.758792299779700.73933115217040160.730391n=84977160.7530862221030080.732726189076022660.724007n=917837680.74739216137304780.7270072300335545320.718704n=1063055120.742052115331357960.72210427501468007500.714269n=11220235840.737177812803580580.717896324006375343280.71052PyBn,k stands for ∂FBn,k;y,1/∂y|y=1n=2,3,…,11;k=1,2,3.Observing Table4 and Figure 2, we see that the B2,100 has the maximal subtree density among Bn,kn=2,3,…,101;k=1,2,…,100. On the whole, it appears that the subtree density of Bn,kn=2,3,…,101;k=1,2,…,100 decreases with the increase of n and k.


## 4.2. Subtree Density of thek Regular Fan Graph

Similarly, with Corollary4, we can obtain the vertex generation function of Fn,k, and combining the subtree density definition (see equation (51)), we can obtain the subtree densities of Fn,k as shown in Table 5 and Figures 3(a) and 3(b).Table 5
Related data forFn,kn=3,4,…,15;k=0,1,2.
nk=0k=1k=2PyFn,0DFn,0PyFn,1DFn,1PyFn,2DFn,2n=3700.714690.68870192300.699879n=42580.737143168040.7456512131120.753336n=59370.7655231886460.76610647703420.768465n=633750.78269920641310.7735121029634910.774643n=7120410.791754220396840.77703721574561120.778349n=8425100.7962462306299620.779261441982708710.780998n=91485590.79849023750472650.7808998899686671360.783027n=105144250.799691241483569520.782189176796911080120.784641n=1117671410.8004142430050626260.7832413474267918909240.785954n=1260287310.8009124246159584150.78411767668829275252530.787045PyFn,k stands for ∂FFn,k;y,/∂y|y=1n=3,4,…,12;k=0,1,2.Figure 3
Subtree densities ofFn,kn=3,4,…,15;k=0,1,…,15. (a) Subtree densities of Fn,kn=3,4,…,15;k=0,1,2. (b) Subtree densities of Fn,kn=3,4,…,15;k=0,1,…,15.
(a)(b)From Figure3(a), when k∈0,1,2 is fixed, we can observe that the subtree density of Fn,k3≤n≤15 gradually increases with the increase of n. As illustrated in Figure 3(b), when n∈3,4,5 is fixed, the subtree density of Fn,k0≤k≤15 also increases with the increase of k.


## 4.3. Subtree Density of thek Regular Wheel Graph

With Corollary7 and equations (50) and (51), we can also obtain the subtree density of Wn,k as shown in Table 6 and Figure 4; here, we skip the repetitive analysis details.Table 6
Related data forWn,kn=3,4,…,10;k=0,1,2.
nk=0k=1k=2PyWn,0DWn,0PyWn,1DWn,1PyWn,2DWn,2n=31160.76315865180.763232747600.777196n=44440.792857745970.79465917010590.800906n=516170.8117478251650.802752373556740.804942n=657890.82125188968440.8036397929918300.80494n=7205190.824719938664210.802885163937515160.804318n=8720640.8251359730311170.8019383322600561990.803706n=92508410.82429499454968740.80109966330828795240.803191n=108659230.8230641005092663450.8003971308556152020330.802768PyWn,k stands for ∂FWn,k;y,1/∂y|y=1n=3,4,…,10;k=0,1,2.Figure 4
Subtree densities ofWn,kn=3,4,…,10;k=0,1,…,12. (a) Subtree densities of Wn,kn=3,4,…,10;k=0,1,…,12. (b) Subtree densities of Wn,kn=3,4,5;k=0,1,…,12.
(a)(b)From Figure4(a), when k∈0,1,2 is fixed, we notice a very interesting observation: the subtree density of Wn,k3≤n≤10 gradually decreases with the increase of n. This trend needs to be further verified through combinatoric approaches. When n∈3,4,5 is fixed, by observing Figure 4(b), it appears that the subtree density of Wn,k0≤k≤12 increases with the increase of k.


## 5. Conclusion

As an important topological index of graphs and networks, the subtree number index is closely related to the analysis of the hybrid local reliable network and discovery of new properties of compounds. We present the subtree generating functions and subtree number indices of the generalized book graphBnn≥2, generalized fan graph Fnn≥3, and generalized wheel graph Wnn≥3. Furthermore, we also briefly discuss the subtree density asymptotic characteristics of the k regular cases of these three graphs: Bn,k, Fn,k, and Wn,k. Our study provides some basis for exploring hidden properties of complex cyclic graphs and chemical compounds from a new metric.



---

*Source: 5511214-2021-04-10.xml*