• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    Counting spanning binary trees of labelled undirected graphs

    Thumbnail
    View/Open
    201411046.pdf (333.9Kb)
    Date
    2016
    Author
    Gupta, Jitendra
    Metadata
    Show full item record
    Abstract
    The number of spanning binary trees of a connected labelled undirectedgraph is an important quantity which is closely related to the reliability of thegraph as a network. Many problems and their applications in mathematics andnetworking are based on spanning trees and binary trees of the graph. However,explicitly determining the number of spanning binary trees in networks is atheoretical challenge. Here we extend Prufer�s method of one to one correspondencebetween prufer sequences and spanning trees of complete graph to countthe spanning binary trees of arbitrary graphs. We follow a two step approach tocount the number of spanning binary trees of an arbitrary connected graph on0n0 vertices. We also exploit the technique of edge contraction and find some fastmethods for converting a simple connected graph into a complete graph whichenables us to count the spanning trees of the given graph.
    URI
    http://drsr.daiict.ac.in/handle/123456789/632
    Collections
    • M Tech Dissertations [923]

    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     


    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV