The number and degree distribution of spanning trees in the Tower of Hanoi graph

The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a ch...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-01, Vol.609, p.443-455
Main Authors: Zhang, Zhongzhi, Wu, Shunqi, Li, Mingyun, Comellas, Francesc
Format: Article
Language:English
Subjects:
Degree distribution
Entropy
Exact solutions
Fractal geometry
Graph theory
Graphs
Invariants
Mathematical analysis
Spanning trees
Synchronization
Tower of Hanoi graph
Towers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c373t-4b8fceee0620161c6b635295c190b8412084a01f41884ef34b076f74b50984923
cites cdi_FETCH-LOGICAL-c373t-4b8fceee0620161c6b635295c190b8412084a01f41884ef34b076f74b50984923
container_end_page 455
container_issue
container_start_page 443
container_title Theoretical computer science
container_volume 609
creator Zhang, Zhongzhi
Wu, Shunqi
Li, Mingyun
Comellas, Francesc
description The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the number and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the n-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.
doi_str_mv 10.1016/j.tcs.2015.10.032
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1778036004</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S030439751500938X</els_id><sourcerecordid>1778036004</sourcerecordid><originalsourceid>FETCH-LOGICAL-c373t-4b8fceee0620161c6b635295c190b8412084a01f41884ef34b076f74b50984923</originalsourceid><addsrcrecordid>eNp9kMFOwzAMhiMEEmPwANxy5NLiNGnTihOagCFNgsM4R2nqbpm2tCQpiLcn0zjji2X__iz7J-SWQc6AVfe7PJqQF8DKVOfAizMyY7VssqJoxDmZAQeR8UaWl-QqhB2kKGU1I-_rLVI3HVr0VLuOdrjxiLSzIXrbTtEOjg49DaN2zroNjUkN1DoaE7cevhOW5KV2g6Ubr8ftNbno9T7gzV-ek4_np_Vima3eXl4Xj6vMcMljJtq6N4gIVbq5YqZqK14WTWlYA20tWAG10MB6wepaYM9FC7LqpWhLaGrRFHxO7k57Rz98ThiiOthgcL_XDocpKCZlDbwCEGmUnUaNH0Lw2KvR24P2P4qBOrqndiq5p47uHVvJvcQ8nBhMP3xZ9CoYi85gZz2aqLrB_kP_Ajiddgs</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1778036004</pqid></control><display><type>article</type><title>The number and degree distribution of spanning trees in the Tower of Hanoi graph</title><source>ScienceDirect Freedom Collection</source><creator>Zhang, Zhongzhi ; Wu, Shunqi ; Li, Mingyun ; Comellas, Francesc</creator><creatorcontrib>Zhang, Zhongzhi ; Wu, Shunqi ; Li, Mingyun ; Comellas, Francesc</creatorcontrib><description>The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the number and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the n-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.</description><identifier>ISSN: 0304-3975</identifier><identifier>EISSN: 1879-2294</identifier><identifier>DOI: 10.1016/j.tcs.2015.10.032</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Degree distribution ; Entropy ; Exact solutions ; Fractal geometry ; Graph theory ; Graphs ; Invariants ; Mathematical analysis ; Spanning trees ; Synchronization ; Tower of Hanoi graph ; Towers</subject><ispartof>Theoretical computer science, 2016-01, Vol.609, p.443-455</ispartof><rights>2015 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c373t-4b8fceee0620161c6b635295c190b8412084a01f41884ef34b076f74b50984923</citedby><cites>FETCH-LOGICAL-c373t-4b8fceee0620161c6b635295c190b8412084a01f41884ef34b076f74b50984923</cites><orcidid>0000-0003-4523-0240</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Zhang, Zhongzhi</creatorcontrib><creatorcontrib>Wu, Shunqi</creatorcontrib><creatorcontrib>Li, Mingyun</creatorcontrib><creatorcontrib>Comellas, Francesc</creatorcontrib><title>The number and degree distribution of spanning trees in the Tower of Hanoi graph</title><title>Theoretical computer science</title><description>The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the number and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the n-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.</description><subject>Degree distribution</subject><subject>Entropy</subject><subject>Exact solutions</subject><subject>Fractal geometry</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Invariants</subject><subject>Mathematical analysis</subject><subject>Spanning trees</subject><subject>Synchronization</subject><subject>Tower of Hanoi graph</subject><subject>Towers</subject><issn>0304-3975</issn><issn>1879-2294</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><recordid>eNp9kMFOwzAMhiMEEmPwANxy5NLiNGnTihOagCFNgsM4R2nqbpm2tCQpiLcn0zjji2X__iz7J-SWQc6AVfe7PJqQF8DKVOfAizMyY7VssqJoxDmZAQeR8UaWl-QqhB2kKGU1I-_rLVI3HVr0VLuOdrjxiLSzIXrbTtEOjg49DaN2zroNjUkN1DoaE7cevhOW5KV2g6Ubr8ftNbno9T7gzV-ek4_np_Vima3eXl4Xj6vMcMljJtq6N4gIVbq5YqZqK14WTWlYA20tWAG10MB6wepaYM9FC7LqpWhLaGrRFHxO7k57Rz98ThiiOthgcL_XDocpKCZlDbwCEGmUnUaNH0Lw2KvR24P2P4qBOrqndiq5p47uHVvJvcQ8nBhMP3xZ9CoYi85gZz2aqLrB_kP_Ajiddgs</recordid><startdate>20160104</startdate><enddate>20160104</enddate><creator>Zhang, Zhongzhi</creator><creator>Wu, Shunqi</creator><creator>Li, Mingyun</creator><creator>Comellas, Francesc</creator><general>Elsevier B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0003-4523-0240</orcidid></search><sort><creationdate>20160104</creationdate><title>The number and degree distribution of spanning trees in the Tower of Hanoi graph</title><author>Zhang, Zhongzhi ; Wu, Shunqi ; Li, Mingyun ; Comellas, Francesc</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c373t-4b8fceee0620161c6b635295c190b8412084a01f41884ef34b076f74b50984923</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>Degree distribution</topic><topic>Entropy</topic><topic>Exact solutions</topic><topic>Fractal geometry</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Invariants</topic><topic>Mathematical analysis</topic><topic>Spanning trees</topic><topic>Synchronization</topic><topic>Tower of Hanoi graph</topic><topic>Towers</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Zhang, Zhongzhi</creatorcontrib><creatorcontrib>Wu, Shunqi</creatorcontrib><creatorcontrib>Li, Mingyun</creatorcontrib><creatorcontrib>Comellas, Francesc</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Zhang, Zhongzhi</au><au>Wu, Shunqi</au><au>Li, Mingyun</au><au>Comellas, Francesc</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The number and degree distribution of spanning trees in the Tower of Hanoi graph</atitle><jtitle>Theoretical computer science</jtitle><date>2016-01-04</date><risdate>2016</risdate><volume>609</volume><spage>443</spage><epage>455</epage><pages>443-455</pages><issn>0304-3975</issn><eissn>1879-2294</eissn><abstract>The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the number and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the n-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.tcs.2015.10.032</doi><tpages>13</tpages><orcidid>https://orcid.org/0000-0003-4523-0240</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0304-3975
ispartof Theoretical computer science, 2016-01, Vol.609, p.443-455
issn 0304-3975
1879-2294
language eng
recordid cdi_proquest_miscellaneous_1778036004
source ScienceDirect Freedom Collection
subjects Degree distribution
Entropy
Exact solutions
Fractal geometry
Graph theory
Graphs
Invariants
Mathematical analysis
Spanning trees
Synchronization
Tower of Hanoi graph
Towers
title The number and degree distribution of spanning trees in the Tower of Hanoi graph
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-06T19%3A46%3A46IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20number%20and%20degree%20distribution%20of%20spanning%20trees%20in%20the%20Tower%20of%20Hanoi%20graph&rft.jtitle=Theoretical%20computer%20science&rft.au=Zhang,%20Zhongzhi&rft.date=2016-01-04&rft.volume=609&rft.spage=443&rft.epage=455&rft.pages=443-455&rft.issn=0304-3975&rft.eissn=1879-2294&rft_id=info:doi/10.1016/j.tcs.2015.10.032&rft_dat=%3Cproquest_cross%3E1778036004%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c373t-4b8fceee0620161c6b635295c190b8412084a01f41884ef34b076f74b50984923%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1778036004&rft_id=info:pmid/&rfr_iscdi=true