The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs

被引：27

作者：

Comellas, Francesc ^{[1
]}

Miralles, Alicia ^{[1
]}

Liu, Hongxiao ^{[2
]}

Zhang, Zhongzhi ^{[2
]}

机构：

[1] Univ Politecn Cataluna, EPSC, Dep Matemat Aplicada 4, E-08028 Barcelona, Catalonia, Spain

[2] Fudan Univ, Sch Comp Sci, Shanghai Key Lab Intelligent Informat Proc, Shanghai 200433, Peoples R China

来源：

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS | 2013年 / 392卷 / 12期

基金：

中国国家自然科学基金;

关键词：

Spanning trees; Tree entropy; Complex networks; Self-similarity; ENUMERATION;

D O I：

10.1016/j.physa.2012.10.047

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

In this paper we give an exact analytical expression for the number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. This number is an important graph invariant related to different topological and dynamic properties of the graph, such as its reliability, synchronization capability and diffusion properties. The calculation of the number of spanning trees is a demanding and difficult task, in particular for large graphs, and thus there is much interest in obtaining closed expressions for relevant infinite graph families. We have also calculated the spanning tree entropy of the graphs which we have compared with those for graphs with the same average degree. (c) 2013 Elsevier B.V. All rights reserved.

引用

页码：2803 / 2806

页数：4

共 20 条

[1]

[Anonymous], 2001, ALGEBRAIC GRAPH THEO, DOI DOI 10.1007/978-1-4613-0163-9

[2]

BRANDSTAEDT A, 1999, SIAM MONOGRAPHS DISC

[3] Topology of technology graphs: Small world patterns in electronic circuits [J].

Ferrer i Cancho, R. ;

Janssen, C. ;

Solé, R.V. .

Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 2001, 64 (4 II) :461191-461195

[4] Spanning trees on the Sierpinski gasket [J].

Chang, Shu-Chiuan ;

Chen, Lung-Chi ;

Yang, Wei-Shih .

JOURNAL OF STATISTICAL PHYSICS, 2007, 126 (03) :649-667

[5]

Colbourn Charles J, 1987, The combinatorics of network reliability

[6] Vertex labeling and routing in self-similar outerplanar unclustered graphs modeling complex networks [J].

Comellas, Francesc ;

Miralles, Alicia .

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2009, 42 (42)

[7] Modeling complex networks with self-similar outerplanar unclustered graphs [J].

Comellas, Francesc ;

Miralles, Alicia .

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2009, 388 (11) :2227-2233

[8] Light absorption spectrum of two-dimensional Mott insulators [J].

Itoh, H ;

Takahashi, A ;

Aihara, M .

PHYSICAL REVIEW B, 2006, 73 (07)

[9] LARGE-SCALE PROPERTIES AND COLLAPSE TRANSITION OF BRANCHED POLYMERS - EXACT RESULTS ON FRACTAL LATTICES [J].

KNEZEVIC, M ;

VANNIMENUS, J .

PHYSICAL REVIEW LETTERS, 1986, 56 (15) :1591-1594

[10] Asymptotic enumeration of spanning trees [J].

Lyons, R .

COMBINATORICS PROBABILITY & COMPUTING, 2005, 14 (04) :491-522

← 1 2 →