Sharp bounds for the Randić index of graphs with given minimum and maximum degree

The Randić index of a graph G, written R(G), is the sum of 1d(u)d(v) over all edges uv in E(G). Let d and D be positive integers d

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-10, Vol.247, p.111-115
Main Authors: O, Suil, Shi, Yongtang
Format: Article
Language:English
Subjects:
Branch & bound algorithms
Combinatorics
Generalized linear models
Graph theory
Integers
Maximum degree
Maximum likelihood method
Minimum degree
Randic index
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-c325t-9e0786f11bfc1928277eeacf8fc6d4cbb383f3af62641f11f4fd533de2fb49cc3
cites cdi_FETCH-LOGICAL-c325t-9e0786f11bfc1928277eeacf8fc6d4cbb383f3af62641f11f4fd533de2fb49cc3
container_end_page 115
container_issue
container_start_page 111
container_title Discrete Applied Mathematics
container_volume 247
creator O, Suil
Shi, Yongtang
description The Randić index of a graph G, written R(G), is the sum of 1d(u)d(v) over all edges uv in E(G). Let d and D be positive integers d
doi_str_mv 10.1016/j.dam.2018.03.064
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2114218920</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0166218X1830163X</els_id><sourcerecordid>2114218920</sourcerecordid><originalsourceid>FETCH-LOGICAL-c325t-9e0786f11bfc1928277eeacf8fc6d4cbb383f3af62641f11f4fd533de2fb49cc3</originalsourceid><addsrcrecordid>eNp9kMtKxDAUhoMoOI4-gLuA69ZcOmmLKxm8wYAwKrgLaXIyTbHtmLTj-AS-mA9mxnHtKifw_efyIXROSUoJFZdNalSbMkKLlPCUiOwATWiRs0TkOT1Ek8iIhNHi9RidhNAQQmj8TdDyqVZ-jat-7EzAtvd4qAEvVWfc9xd2nYEt7i1eebWuA_5wQ41XbgMdbl3n2rHFkcSt2v7WBlYe4BQdWfUW4OzvnaKX25vn-X2yeLx7mF8vEs3ZbEhKIHkhLKWV1bRkBctzAKVtYbUwma4qXnDLlRVMZDRiNrNmxrkBZqus1JpP0cW-79r37yOEQTb96Ls4UjJKs3heyUik6J7Svg_Bg5Vr71rlPyUlcqdONjKqkzt1knAZ1cXM1T4Dcf2NAy-DdtBpMM6DHqTp3T_pHxR5d6I</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2114218920</pqid></control><display><type>article</type><title>Sharp bounds for the Randić index of graphs with given minimum and maximum degree</title><source>ScienceDirect Journals</source><creator>O, Suil ; Shi, Yongtang</creator><creatorcontrib>O, Suil ; Shi, Yongtang</creatorcontrib><description>The Randić index of a graph G, written R(G), is the sum of 1d(u)d(v) over all edges uv in E(G). Let d and D be positive integers d&lt;D. In this paper, we prove that if G is a graph with minimum degree d and maximum degree D, then R(G)≥dDd+Dn; equality holds only when G is an n-vertex (d,D)-biregular. Furthermore, we show that if G is an n-vertex connected graph with minimum degree d and maximum degree D, then R(G)≤n2−∑i=dD−1121i−1i+12; it is sharp for infinitely many n, and we characterize when equality holds in the bound.</description><identifier>ISSN: 0166-218X</identifier><identifier>EISSN: 1872-6771</identifier><identifier>DOI: 10.1016/j.dam.2018.03.064</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Branch &amp; bound algorithms ; Combinatorics ; Generalized linear models ; Graph theory ; Integers ; Maximum degree ; Maximum likelihood method ; Minimum degree ; Randic index</subject><ispartof>Discrete Applied Mathematics, 2018-10, Vol.247, p.111-115</ispartof><rights>2018 Elsevier B.V.</rights><rights>Copyright Elsevier BV Oct 1, 2018</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c325t-9e0786f11bfc1928277eeacf8fc6d4cbb383f3af62641f11f4fd533de2fb49cc3</citedby><cites>FETCH-LOGICAL-c325t-9e0786f11bfc1928277eeacf8fc6d4cbb383f3af62641f11f4fd533de2fb49cc3</cites><orcidid>0000-0001-9406-7967 ; 0000-0002-2182-6237</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>O, Suil</creatorcontrib><creatorcontrib>Shi, Yongtang</creatorcontrib><title>Sharp bounds for the Randić index of graphs with given minimum and maximum degree</title><title>Discrete Applied Mathematics</title><description>The Randić index of a graph G, written R(G), is the sum of 1d(u)d(v) over all edges uv in E(G). Let d and D be positive integers d&lt;D. In this paper, we prove that if G is a graph with minimum degree d and maximum degree D, then R(G)≥dDd+Dn; equality holds only when G is an n-vertex (d,D)-biregular. Furthermore, we show that if G is an n-vertex connected graph with minimum degree d and maximum degree D, then R(G)≤n2−∑i=dD−1121i−1i+12; it is sharp for infinitely many n, and we characterize when equality holds in the bound.</description><subject>Branch &amp; bound algorithms</subject><subject>Combinatorics</subject><subject>Generalized linear models</subject><subject>Graph theory</subject><subject>Integers</subject><subject>Maximum degree</subject><subject>Maximum likelihood method</subject><subject>Minimum degree</subject><subject>Randic index</subject><issn>0166-218X</issn><issn>1872-6771</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNp9kMtKxDAUhoMoOI4-gLuA69ZcOmmLKxm8wYAwKrgLaXIyTbHtmLTj-AS-mA9mxnHtKifw_efyIXROSUoJFZdNalSbMkKLlPCUiOwATWiRs0TkOT1Ek8iIhNHi9RidhNAQQmj8TdDyqVZ-jat-7EzAtvd4qAEvVWfc9xd2nYEt7i1eebWuA_5wQ41XbgMdbl3n2rHFkcSt2v7WBlYe4BQdWfUW4OzvnaKX25vn-X2yeLx7mF8vEs3ZbEhKIHkhLKWV1bRkBctzAKVtYbUwma4qXnDLlRVMZDRiNrNmxrkBZqus1JpP0cW-79r37yOEQTb96Ls4UjJKs3heyUik6J7Svg_Bg5Vr71rlPyUlcqdONjKqkzt1knAZ1cXM1T4Dcf2NAy-DdtBpMM6DHqTp3T_pHxR5d6I</recordid><startdate>20181001</startdate><enddate>20181001</enddate><creator>O, Suil</creator><creator>Shi, Yongtang</creator><general>Elsevier B.V</general><general>Elsevier BV</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-0001-9406-7967</orcidid><orcidid>https://orcid.org/0000-0002-2182-6237</orcidid></search><sort><creationdate>20181001</creationdate><title>Sharp bounds for the Randić index of graphs with given minimum and maximum degree</title><author>O, Suil ; Shi, Yongtang</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c325t-9e0786f11bfc1928277eeacf8fc6d4cbb383f3af62641f11f4fd533de2fb49cc3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Branch &amp; bound algorithms</topic><topic>Combinatorics</topic><topic>Generalized linear models</topic><topic>Graph theory</topic><topic>Integers</topic><topic>Maximum degree</topic><topic>Maximum likelihood method</topic><topic>Minimum degree</topic><topic>Randic index</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>O, Suil</creatorcontrib><creatorcontrib>Shi, Yongtang</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>Discrete Applied Mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>O, Suil</au><au>Shi, Yongtang</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Sharp bounds for the Randić index of graphs with given minimum and maximum degree</atitle><jtitle>Discrete Applied Mathematics</jtitle><date>2018-10-01</date><risdate>2018</risdate><volume>247</volume><spage>111</spage><epage>115</epage><pages>111-115</pages><issn>0166-218X</issn><eissn>1872-6771</eissn><abstract>The Randić index of a graph G, written R(G), is the sum of 1d(u)d(v) over all edges uv in E(G). Let d and D be positive integers d&lt;D. In this paper, we prove that if G is a graph with minimum degree d and maximum degree D, then R(G)≥dDd+Dn; equality holds only when G is an n-vertex (d,D)-biregular. Furthermore, we show that if G is an n-vertex connected graph with minimum degree d and maximum degree D, then R(G)≤n2−∑i=dD−1121i−1i+12; it is sharp for infinitely many n, and we characterize when equality holds in the bound.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/j.dam.2018.03.064</doi><tpages>5</tpages><orcidid>https://orcid.org/0000-0001-9406-7967</orcidid><orcidid>https://orcid.org/0000-0002-2182-6237</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0166-218X
ispartof Discrete Applied Mathematics, 2018-10, Vol.247, p.111-115
issn 0166-218X
1872-6771
language eng
recordid cdi_proquest_journals_2114218920
source ScienceDirect Journals
subjects Branch & bound algorithms
Combinatorics
Generalized linear models
Graph theory
Integers
Maximum degree
Maximum likelihood method
Minimum degree
Randic index
title Sharp bounds for the Randić index of graphs with given minimum and maximum degree
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T21%3A39%3A05IST&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=Sharp%20bounds%20for%20the%20Randi%C4%87%20index%20of%20graphs%20with%20given%20minimum%20and%20maximum%20degree&rft.jtitle=Discrete%20Applied%20Mathematics&rft.au=O,%20Suil&rft.date=2018-10-01&rft.volume=247&rft.spage=111&rft.epage=115&rft.pages=111-115&rft.issn=0166-218X&rft.eissn=1872-6771&rft_id=info:doi/10.1016/j.dam.2018.03.064&rft_dat=%3Cproquest_cross%3E2114218920%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c325t-9e0786f11bfc1928277eeacf8fc6d4cbb383f3af62641f11f4fd533de2fb49cc3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2114218920&rft_id=info:pmid/&rfr_iscdi=true