Loading…
A note on diameter and the degree sequence of a graph
In this note, we use a technique introduced by Dankelmann and Entringer [P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees, J. Graph Theory 33 (2000) 1–13] to obtain a strengthening of an old classical theorem by Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. P...
Saved in:
| Published in: | Applied mathematics letters 2012-02, Vol.25 (2), p.175-178 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Subjects: | |
| 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-c359t-5f729a49b18c66afb0684c64aea5b5adf13882a230877ded30483591b475bded3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c359t-5f729a49b18c66afb0684c64aea5b5adf13882a230877ded30483591b475bded3 |
| container_end_page | 178 |
| container_issue | 2 |
| container_start_page | 175 |
| container_title | Applied mathematics letters |
| container_volume | 25 |
| creator | Mukwembi, Simon |
| description | In this note, we use a technique introduced by Dankelmann and Entringer [P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees, J. Graph Theory 33 (2000) 1–13] to obtain a strengthening of an old classical theorem by Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 73–79] on diameter and minimum degree. To be precise, we will prove that if
G
is a connected graph of order
n
and minimum degree
δ
, then its diameter does not exceed
3
(
n
−
t
)
δ
+
1
+
O
(
1
)
,
where
t
is the number of distinct terms of the degree sequence of
G
. The featured parameter,
t
, is attractive in nature and promising; more discoveries on it in relation to other graph parameters are envisaged. |
| doi_str_mv | 10.1016/j.aml.2011.08.010 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_926321990</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0893965911003739</els_id><sourcerecordid>926321990</sourcerecordid><originalsourceid>FETCH-LOGICAL-c359t-5f729a49b18c66afb0684c64aea5b5adf13882a230877ded30483591b475bded3</originalsourceid><addsrcrecordid>eNp9kE1Lw0AQhhdRsFZ_gLe9iKfE2Ww22cVTKX5BwYuel8lm0qakSd1NBf-9G1o8ehoGnnc-HsZuBaQCRPGwTXHXpRkIkYJOQcAZmwldykTlKjtnM9BGJqZQ5pJdhbAFAGmknjG14P0wEh96Xre4o5E8x77m44Z4TWtPxAN9Hah3kWk48rXH_eaaXTTYBbo51Tn7fH76WL4mq_eXt-VilTipzJiopswM5qYS2hUFNhUUOndFjoSqUlg3QmqdYSZBl2VNtYRcx6Co8lJVUz9n98e5ez_EI8Jod21w1HXY03AI1mSFzIQxEElxJJ0fQvDU2L1vd-h_rAA7GbJbGw3ZyZAFbaOhmLk7TcfgsGs89q4Nf8EsXlGAkpF7PHIUX_1uydvg2slI3Xpyo62H9p8tv9YbeTY</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>926321990</pqid></control><display><type>article</type><title>A note on diameter and the degree sequence of a graph</title><source>Elsevier</source><creator>Mukwembi, Simon</creator><creatorcontrib>Mukwembi, Simon</creatorcontrib><description>In this note, we use a technique introduced by Dankelmann and Entringer [P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees, J. Graph Theory 33 (2000) 1–13] to obtain a strengthening of an old classical theorem by Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 73–79] on diameter and minimum degree. To be precise, we will prove that if
G
is a connected graph of order
n
and minimum degree
δ
, then its diameter does not exceed
3
(
n
−
t
)
δ
+
1
+
O
(
1
)
,
where
t
is the number of distinct terms of the degree sequence of
G
. The featured parameter,
t
, is attractive in nature and promising; more discoveries on it in relation to other graph parameters are envisaged.</description><identifier>ISSN: 0893-9659</identifier><identifier>EISSN: 1873-5452</identifier><identifier>DOI: 10.1016/j.aml.2011.08.010</identifier><language>eng</language><publisher>Kidlington: Elsevier Ltd</publisher><subject>Combinatorics ; Combinatorics. Ordered structures ; Degree sequence ; Deltas ; Diameter ; Exact sciences and technology ; Graph theory ; Graphs ; Mathematical analysis ; Mathematics ; Minimum degree ; Numerical analysis ; Numerical analysis. Scientific computation ; Pollack ; Sciences and techniques of general use ; Strengthening ; Trees</subject><ispartof>Applied mathematics letters, 2012-02, Vol.25 (2), p.175-178</ispartof><rights>2011 Elsevier Ltd</rights><rights>2015 INIST-CNRS</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c359t-5f729a49b18c66afb0684c64aea5b5adf13882a230877ded30483591b475bded3</citedby><cites>FETCH-LOGICAL-c359t-5f729a49b18c66afb0684c64aea5b5adf13882a230877ded30483591b475bded3</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><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=24756053$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Mukwembi, Simon</creatorcontrib><title>A note on diameter and the degree sequence of a graph</title><title>Applied mathematics letters</title><description>In this note, we use a technique introduced by Dankelmann and Entringer [P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees, J. Graph Theory 33 (2000) 1–13] to obtain a strengthening of an old classical theorem by Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 73–79] on diameter and minimum degree. To be precise, we will prove that if
G
is a connected graph of order
n
and minimum degree
δ
, then its diameter does not exceed
3
(
n
−
t
)
δ
+
1
+
O
(
1
)
,
where
t
is the number of distinct terms of the degree sequence of
G
. The featured parameter,
t
, is attractive in nature and promising; more discoveries on it in relation to other graph parameters are envisaged.</description><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Degree sequence</subject><subject>Deltas</subject><subject>Diameter</subject><subject>Exact sciences and technology</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Mathematical analysis</subject><subject>Mathematics</subject><subject>Minimum degree</subject><subject>Numerical analysis</subject><subject>Numerical analysis. Scientific computation</subject><subject>Pollack</subject><subject>Sciences and techniques of general use</subject><subject>Strengthening</subject><subject>Trees</subject><issn>0893-9659</issn><issn>1873-5452</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2012</creationdate><recordtype>article</recordtype><recordid>eNp9kE1Lw0AQhhdRsFZ_gLe9iKfE2Ww22cVTKX5BwYuel8lm0qakSd1NBf-9G1o8ehoGnnc-HsZuBaQCRPGwTXHXpRkIkYJOQcAZmwldykTlKjtnM9BGJqZQ5pJdhbAFAGmknjG14P0wEh96Xre4o5E8x77m44Z4TWtPxAN9Hah3kWk48rXH_eaaXTTYBbo51Tn7fH76WL4mq_eXt-VilTipzJiopswM5qYS2hUFNhUUOndFjoSqUlg3QmqdYSZBl2VNtYRcx6Co8lJVUz9n98e5ez_EI8Jod21w1HXY03AI1mSFzIQxEElxJJ0fQvDU2L1vd-h_rAA7GbJbGw3ZyZAFbaOhmLk7TcfgsGs89q4Nf8EsXlGAkpF7PHIUX_1uydvg2slI3Xpyo62H9p8tv9YbeTY</recordid><startdate>20120201</startdate><enddate>20120201</enddate><creator>Mukwembi, Simon</creator><general>Elsevier Ltd</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JQ2</scope><scope>KR7</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20120201</creationdate><title>A note on diameter and the degree sequence of a graph</title><author>Mukwembi, Simon</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c359t-5f729a49b18c66afb0684c64aea5b5adf13882a230877ded30483591b475bded3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2012</creationdate><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Degree sequence</topic><topic>Deltas</topic><topic>Diameter</topic><topic>Exact sciences and technology</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Mathematical analysis</topic><topic>Mathematics</topic><topic>Minimum degree</topic><topic>Numerical analysis</topic><topic>Numerical analysis. Scientific computation</topic><topic>Pollack</topic><topic>Sciences and techniques of general use</topic><topic>Strengthening</topic><topic>Trees</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mukwembi, Simon</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Civil Engineering Abstracts</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>Applied mathematics letters</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>A note on diameter and the degree sequence of a graph</atitle><jtitle>Applied mathematics letters</jtitle><date>2012-02-01</date><risdate>2012</risdate><volume>25</volume><issue>2</issue><spage>175</spage><epage>178</epage><pages>175-178</pages><issn>0893-9659</issn><eissn>1873-5452</eissn><abstract>In this note, we use a technique introduced by Dankelmann and Entringer [P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees, J. Graph Theory 33 (2000) 1–13] to obtain a strengthening of an old classical theorem by Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 73–79] on diameter and minimum degree. To be precise, we will prove that if
G
is a connected graph of order
n
and minimum degree
δ
, then its diameter does not exceed
3
(
n
−
t
)
δ
+
1
+
O
(
1
)
,
where
t
is the number of distinct terms of the degree sequence of
G
. The featured parameter,
t
, is attractive in nature and promising; more discoveries on it in relation to other graph parameters are envisaged.</abstract><cop>Kidlington</cop><pub>Elsevier Ltd</pub><doi>10.1016/j.aml.2011.08.010</doi><tpages>4</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0893-9659 |
| ispartof | Applied mathematics letters, 2012-02, Vol.25 (2), p.175-178 |
| issn | 0893-9659 1873-5452 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_926321990 |
| source | Elsevier |
| subjects | Combinatorics Combinatorics. Ordered structures Degree sequence Deltas Diameter Exact sciences and technology Graph theory Graphs Mathematical analysis Mathematics Minimum degree Numerical analysis Numerical analysis. Scientific computation Pollack Sciences and techniques of general use Strengthening Trees |
| title | A note on diameter and the degree sequence of a graph |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-10T02%3A46%3A36IST&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=A%20note%20on%20diameter%20and%20the%20degree%20sequence%20of%20a%20graph&rft.jtitle=Applied%20mathematics%20letters&rft.au=Mukwembi,%20Simon&rft.date=2012-02-01&rft.volume=25&rft.issue=2&rft.spage=175&rft.epage=178&rft.pages=175-178&rft.issn=0893-9659&rft.eissn=1873-5452&rft_id=info:doi/10.1016/j.aml.2011.08.010&rft_dat=%3Cproquest_cross%3E926321990%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c359t-5f729a49b18c66afb0684c64aea5b5adf13882a230877ded30483591b475bded3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=926321990&rft_id=info:pmid/&rfr_iscdi=true |