Average Distance, Independence Number, and Spanning Trees

Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most 23α, if n≤2α−1, and at most α+2, if n>2α−1. As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in t...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2014-07, Vol.76 (3), p.194-199
Main Author: Mukwembi, Simon
Format: Article
Language:English
Subjects:
average distance
independence number
spanning trees
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-c3358-d0e434ee5f06a56388c210998020a83b875d60e5dbd1fd1068d6cdcb2558dca23
cites cdi_FETCH-LOGICAL-c3358-d0e434ee5f06a56388c210998020a83b875d60e5dbd1fd1068d6cdcb2558dca23
container_end_page 199
container_issue 3
container_start_page 194
container_title Journal of graph theory
container_volume 76
creator Mukwembi, Simon
description Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most 23α, if n≤2α−1, and at most α+2, if n>2α−1. As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.
doi_str_mv 10.1002/jgt.21758
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_1518090427</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>3281411681</sourcerecordid><originalsourceid>FETCH-LOGICAL-c3358-d0e434ee5f06a56388c210998020a83b875d60e5dbd1fd1068d6cdcb2558dca23</originalsourceid><addsrcrecordid>eNp1kFFPwjAQxxujiYg--A2W-GTi4NquW_dIQBGCGAXjY9OtNzKEMVtQ-fZWp7750ksvv__d5UfIOYUOBWDd5WLbYTQR8oC0KKRJCJTKQ9ICHkdhCiw6JifOLcG3BcgWSXtvaPUCg0HptrrK8SoYVQZr9I__BdPdOkN7FejKBLNaV1VZLYK5RXSn5KjQK4dnP7VNnm6u5_3bcHI_HPV7kzDnXMjQAEY8QhQFxFrEXMqc-cNSCQy05JlMhIkBhckMLQyFWJo4N3nGhJAm14y3yUUzt7ab1x26rVpudrbyKxUVVEIKEUs8ddlQud04Z7FQtS3X2u4VBfVlRnkz6tuMZ7sN-16ucP8_qMbD-W8ibBJeEn78JbR9UXHCE6Gep0PFH-_GswGT6oF_Agxwcfs</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1518090427</pqid></control><display><type>article</type><title>Average Distance, Independence Number, and Spanning Trees</title><source>Wiley-Blackwell Read &amp; Publish Collection</source><creator>Mukwembi, Simon</creator><creatorcontrib>Mukwembi, Simon</creatorcontrib><description>Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most 23α, if n≤2α−1, and at most α+2, if n&gt;2α−1. As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.</description><identifier>ISSN: 0364-9024</identifier><identifier>EISSN: 1097-0118</identifier><identifier>DOI: 10.1002/jgt.21758</identifier><identifier>CODEN: JGTHDO</identifier><language>eng</language><publisher>Hoboken: Blackwell Publishing Ltd</publisher><subject>average distance ; independence number ; spanning trees</subject><ispartof>Journal of graph theory, 2014-07, Vol.76 (3), p.194-199</ispartof><rights>2013 Wiley Periodicals, Inc.</rights><rights>Copyright © 2014 Wiley Periodicals, Inc.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c3358-d0e434ee5f06a56388c210998020a83b875d60e5dbd1fd1068d6cdcb2558dca23</citedby><cites>FETCH-LOGICAL-c3358-d0e434ee5f06a56388c210998020a83b875d60e5dbd1fd1068d6cdcb2558dca23</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Mukwembi, Simon</creatorcontrib><title>Average Distance, Independence Number, and Spanning Trees</title><title>Journal of graph theory</title><addtitle>J. Graph Theory</addtitle><description>Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most 23α, if n≤2α−1, and at most α+2, if n&gt;2α−1. As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.</description><subject>average distance</subject><subject>independence number</subject><subject>spanning trees</subject><issn>0364-9024</issn><issn>1097-0118</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2014</creationdate><recordtype>article</recordtype><recordid>eNp1kFFPwjAQxxujiYg--A2W-GTi4NquW_dIQBGCGAXjY9OtNzKEMVtQ-fZWp7750ksvv__d5UfIOYUOBWDd5WLbYTQR8oC0KKRJCJTKQ9ICHkdhCiw6JifOLcG3BcgWSXtvaPUCg0HptrrK8SoYVQZr9I__BdPdOkN7FejKBLNaV1VZLYK5RXSn5KjQK4dnP7VNnm6u5_3bcHI_HPV7kzDnXMjQAEY8QhQFxFrEXMqc-cNSCQy05JlMhIkBhckMLQyFWJo4N3nGhJAm14y3yUUzt7ab1x26rVpudrbyKxUVVEIKEUs8ddlQud04Z7FQtS3X2u4VBfVlRnkz6tuMZ7sN-16ucP8_qMbD-W8ibBJeEn78JbR9UXHCE6Gep0PFH-_GswGT6oF_Agxwcfs</recordid><startdate>201407</startdate><enddate>201407</enddate><creator>Mukwembi, Simon</creator><general>Blackwell Publishing Ltd</general><general>Wiley Subscription Services, Inc</general><scope>BSCLL</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>201407</creationdate><title>Average Distance, Independence Number, and Spanning Trees</title><author>Mukwembi, Simon</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c3358-d0e434ee5f06a56388c210998020a83b875d60e5dbd1fd1068d6cdcb2558dca23</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2014</creationdate><topic>average distance</topic><topic>independence number</topic><topic>spanning trees</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mukwembi, Simon</creatorcontrib><collection>Istex</collection><collection>CrossRef</collection><jtitle>Journal of graph theory</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mukwembi, Simon</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Average Distance, Independence Number, and Spanning Trees</atitle><jtitle>Journal of graph theory</jtitle><addtitle>J. Graph Theory</addtitle><date>2014-07</date><risdate>2014</risdate><volume>76</volume><issue>3</issue><spage>194</spage><epage>199</epage><pages>194-199</pages><issn>0364-9024</issn><eissn>1097-0118</eissn><coden>JGTHDO</coden><abstract>Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most 23α, if n≤2α−1, and at most α+2, if n&gt;2α−1. As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.</abstract><cop>Hoboken</cop><pub>Blackwell Publishing Ltd</pub><doi>10.1002/jgt.21758</doi><tpages>6</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0364-9024
ispartof Journal of graph theory, 2014-07, Vol.76 (3), p.194-199
issn 0364-9024
1097-0118
language eng
recordid cdi_proquest_journals_1518090427
source Wiley-Blackwell Read & Publish Collection
subjects average distance
independence number
spanning trees
title Average Distance, Independence Number, and Spanning Trees
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-09T08%3A06%3A18IST&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=Average%20Distance,%20Independence%20Number,%20and%20Spanning%20Trees&rft.jtitle=Journal%20of%20graph%20theory&rft.au=Mukwembi,%20Simon&rft.date=2014-07&rft.volume=76&rft.issue=3&rft.spage=194&rft.epage=199&rft.pages=194-199&rft.issn=0364-9024&rft.eissn=1097-0118&rft.coden=JGTHDO&rft_id=info:doi/10.1002/jgt.21758&rft_dat=%3Cproquest_cross%3E3281411681%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c3358-d0e434ee5f06a56388c210998020a83b875d60e5dbd1fd1068d6cdcb2558dca23%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1518090427&rft_id=info:pmid/&rfr_iscdi=true