{"corpus_id":204784515,"paper_sha":"9ed24a2cb2c6fe22ea9464cff6fd88a5a98b090e","doi":"10.1007/s10878-021-00724-2","arxiv_id":"2103.02307","pmid":null,"pmcid":null,"mag_id":3136758443,"dblp_id":"journals/jco/DarabiAKD21","acl_id":null,"title":"On the relation between Wiener index and eccentricity of a graph","year":2021,"publication_date":"2021-03-03","venue":"Journal of combinatorial optimization","journal":{"name":"Journal of Combinatorial Optimization","pages":"817 - 829","volume":"41"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":42,"citation_count":18,"influential_citation_count":2,"is_open_access":false,"arxiv_categories":["math.CO"],"arxiv_license":"http://creativecommons.org/licenses/by/4.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"The relation between the Wiener index W(G) and the eccentricity ε(G)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$\\varepsilon (G)$$\\end{document} of a graph G is studied. Lower and upper bounds on W(G) in terms of ε(G)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$\\varepsilon (G)$$\\end{document} are proved and extremal graphs characterized. A Nordhaus–Gaddum type result on W(G) involving ε(G)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$\\varepsilon (G)$$\\end{document} is given. A sharp upper bound on the Wiener index of a tree in terms of its eccentricity is proved. It is shown that in the class of trees of the same order, the difference W(T)-ε(T)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$W(T) - \\varepsilon (T)$$\\end{document} is minimized on caterpillars. An exact formula for W(T)-ε(T)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$W(T) - \\varepsilon (T)$$\\end{document} in terms of the radius of a tree T is obtained. A lower bound on the eccentricity of a tree in terms of its radius is also given. Two conjectures are proposed. The first asserts that the difference W(G)-ε(G)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$W(G) - \\varepsilon (G)$$\\end{document} does not increase after contracting an edge of G. The second conjecture asserts that the difference between the Wiener index of a graph and its eccentricity is largest on paths.","claims":[{"public_id":"cl_e14a83a703825746b1670129a23109c2","status":"active","text":"A Nordhaus–Gaddum type result on the Wiener index involving eccentricity is given.","confidence":0.9,"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_e14a83a703825746b1670129a23109c2"},{"public_id":"cl_4cc231eb47bb91316457d4425087aae7","status":"active","text":"A sharp upper bound on the Wiener index of a tree in terms of its eccentricity is proved.","confidence":0.95,"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_4cc231eb47bb91316457d4425087aae7"},{"public_id":"cl_0ce64c6858657258dce53a5f21cc0017","status":"active","text":"An exact formula for W(T) − ε(T) in terms of the radius of a tree T is obtained.","confidence":0.9,"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_0ce64c6858657258dce53a5f21cc0017"},{"public_id":"cl_9e1b7389c52bd9603aa1ebfbaeb4432c","status":"active","text":"In the class of trees of the same order, the difference W(T) − ε(T) is minimized on caterpillars.","confidence":0.9,"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_9e1b7389c52bd9603aa1ebfbaeb4432c"},{"public_id":"cl_87846f61c5ccb37904a4a9502db398ab","status":"active","text":"Lower and upper bounds on the Wiener index W(G) in terms of eccentricity ε(G) are proved and extremal graphs characterized.","confidence":0.95,"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_87846f61c5ccb37904a4a9502db398ab"}],"concepts":[{"public_id":"co_6ce52f1f59ace716f042dd85c839ef5c","status":"active","name":"Nordhaus–Gaddum type result","description":"A result that gives bounds on the sum or product of a graph invariant and its complement, here involving Wiener index and eccentricity.","types":["theorem type"],"aliases":[],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_6ce52f1f59ace716f042dd85c839ef5c"},{"public_id":"co_875a26033615e27fd6dd694dcd89d5ab","status":"active","name":"caterpillars","description":"Trees in which all vertices are within distance 1 of a central path; they minimize W(T) − ε(T) among trees of the same order.","types":["graph class"],"aliases":[],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_875a26033615e27fd6dd694dcd89d5ab"},{"public_id":"co_8b1e73114630ea2aa8ab0fb040acb94c","status":"active","name":"eccentricity of a tree","description":"The eccentricity ε(T) of a tree T, defined as the maximum distance from any vertex to any other vertex in the tree.","types":["graph invariant"],"aliases":["ε(T)"],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_8b1e73114630ea2aa8ab0fb040acb94c"},{"public_id":"co_98edafdac14ca1450493f080ef7a48c2","status":"active","name":"eccentricity","description":"The maximum distance from a vertex to any other vertex in the graph; ε(G) denotes the eccentricity of a graph.","types":["graph invariant"],"aliases":["ε(G)"],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_98edafdac14ca1450493f080ef7a48c2"},{"public_id":"co_a5020029d7c135c3189fcba2a262120e","status":"active","name":"radius","description":"The minimum eccentricity among all vertices of a graph; used in the exact formula for W(T) − ε(T).","types":["graph invariant"],"aliases":[],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_a5020029d7c135c3189fcba2a262120e"},{"public_id":"co_e49dad405139a087284a04112cc14fd1","status":"active","name":"extremal graphs","description":"Graphs that achieve the bounds in the inequalities relating Wiener index and eccentricity.","types":["graph class"],"aliases":[],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_e49dad405139a087284a04112cc14fd1"},{"public_id":"co_f7deb57fed4b8a2640b176b245bbba50","status":"active","name":"tree","description":"A connected acyclic graph; the paper studies Wiener index and eccentricity bounds specifically for trees.","types":["graph class"],"aliases":[],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_f7deb57fed4b8a2640b176b245bbba50"},{"public_id":"co_fe0c90f3bfcd88f29ac5a4eb73cee245","status":"active","name":"Wiener index","description":"A graph invariant defined as the sum of distances between all unordered pairs of vertices in a graph.","types":["graph invariant"],"aliases":["W(G)"],"contributors":[{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["extraction"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_fe0c90f3bfcd88f29ac5a4eb73cee245"}],"external_ids":{"DOI":"10.1007/s10878-021-00724-2","ArXiv":"2103.02307","PubMed":null,"PubMedCentral":null,"MAG":3136758443,"DBLP":"journals/jco/DarabiAKD21","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://arxiv.org/pdf/2103.02307","landing_url":"https://arxiv.org/abs/2103.02307","source":"arxiv","pdf_url_source":"derived_arxiv","license":"http://creativecommons.org/licenses/by/4.0/","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":633153,"paper_uid":"519dfb7a-e3df-4f31-8183-c7a65f5327c1","canonical_identity":{"paper_id":633153,"paper_uid":"519dfb7a-e3df-4f31-8183-c7a65f5327c1","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/204784515"}