Gromov Hyperbolicity in Mycielskian Graphs

Since the characterization of Gromov hyperbolic graphs seems a too ambitious task, there are many papers studying the hyperbolicity of several classes of graphs. In this paper, it is proven that every Mycielskian graph GM is hyperbolic and that δ(GM) is comparable to diam(GM) . Furthermore, we study...

Full description

Saved in:
Bibliographic Details
Published in:Symmetry (Basel) 2017-08, Vol.9 (8), p.131
Main Authors: Granados, Ana, Pestana, Domingo, Portilla, Ana, Rodríguez, José
Format: Article
Language:English
Subjects:
extremal problems on graphs
geodesics
Graphs
Gromov hyperbolicity
Mycielskian graphs
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-c361t-ec26853c0e92310801e0de87059f459873518d8b7b10c3a1e38c532dba175b223
cites cdi_FETCH-LOGICAL-c361t-ec26853c0e92310801e0de87059f459873518d8b7b10c3a1e38c532dba175b223
container_end_page
container_issue 8
container_start_page 131
container_title Symmetry (Basel)
container_volume 9
creator Granados, Ana
Pestana, Domingo
Portilla, Ana
Rodríguez, José
description Since the characterization of Gromov hyperbolic graphs seems a too ambitious task, there are many papers studying the hyperbolicity of several classes of graphs. In this paper, it is proven that every Mycielskian graph GM is hyperbolic and that δ(GM) is comparable to diam(GM) . Furthermore, we study the extremal problems of finding the smallest and largest hyperbolicity constants of such graphs; in fact, it is shown that 5/4≤δ(GM)≤5/2 . Graphs G whose Mycielskian have hyperbolicity constant 5/4 or 5/2 are characterized. The hyperbolicity constants of the Mycielskian of path, cycle, complete and complete bipartite graphs are calculated explicitly. Finally, information on δ(G) just in terms of δ(GM) is obtained.
doi_str_mv 10.3390/sym9080131
format article
fullrecord <record><control><sourceid>proquest_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_a2853f0785fc4c478718f56d2cf535b4</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_a2853f0785fc4c478718f56d2cf535b4</doaj_id><sourcerecordid>1939737170</sourcerecordid><originalsourceid>FETCH-LOGICAL-c361t-ec26853c0e92310801e0de87059f459873518d8b7b10c3a1e38c532dba175b223</originalsourceid><addsrcrecordid>eNpNkEFLAzEQhYMoWGov_oIFb4XVSWazSY5StBUqXvQcstmspm6bNdkK--_dWlHnMsPw-N7jEXJJ4RpRwU0atgokUKQnZMJAYC6VKk7_3edkltIGxuHAixImZL6MYRs-s9XQuViF1lvfD5nfZY-D9a5N797ssmU03Vu6IGeNaZOb_ewpebm_e16s8vXT8mFxu84tlrTPnWWl5GjBKYb0kMdB7aQArpqCKymQU1nLSlQULBrqUFqOrK4MFbxiDKfk4citg9noLvqtiYMOxuvvR4iv2sTe29Zpw0anBoTkjS1sIaSgsuFlzWzDkVfFyLo6sroYPvYu9XoT9nE3xtdUoRIoqIBRNT-qbAwpRdf8ulLQh2r1X7X4BU7maHU</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1939737170</pqid></control><display><type>article</type><title>Gromov Hyperbolicity in Mycielskian Graphs</title><source>Publicly Available Content Database</source><creator>Granados, Ana ; Pestana, Domingo ; Portilla, Ana ; Rodríguez, José</creator><creatorcontrib>Granados, Ana ; Pestana, Domingo ; Portilla, Ana ; Rodríguez, José</creatorcontrib><description>Since the characterization of Gromov hyperbolic graphs seems a too ambitious task, there are many papers studying the hyperbolicity of several classes of graphs. In this paper, it is proven that every Mycielskian graph GM is hyperbolic and that δ(GM) is comparable to diam(GM) . Furthermore, we study the extremal problems of finding the smallest and largest hyperbolicity constants of such graphs; in fact, it is shown that 5/4≤δ(GM)≤5/2 . Graphs G whose Mycielskian have hyperbolicity constant 5/4 or 5/2 are characterized. The hyperbolicity constants of the Mycielskian of path, cycle, complete and complete bipartite graphs are calculated explicitly. Finally, information on δ(G) just in terms of δ(GM) is obtained.</description><identifier>ISSN: 2073-8994</identifier><identifier>EISSN: 2073-8994</identifier><identifier>DOI: 10.3390/sym9080131</identifier><language>eng</language><publisher>Basel: MDPI AG</publisher><subject>extremal problems on graphs ; geodesics ; Graphs ; Gromov hyperbolicity ; Mycielskian graphs</subject><ispartof>Symmetry (Basel), 2017-08, Vol.9 (8), p.131</ispartof><rights>Copyright MDPI AG 2017</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c361t-ec26853c0e92310801e0de87059f459873518d8b7b10c3a1e38c532dba175b223</citedby><cites>FETCH-LOGICAL-c361t-ec26853c0e92310801e0de87059f459873518d8b7b10c3a1e38c532dba175b223</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/1939737170/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/1939737170?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>314,780,784,25753,27924,27925,37012,44590,74998</link.rule.ids></links><search><creatorcontrib>Granados, Ana</creatorcontrib><creatorcontrib>Pestana, Domingo</creatorcontrib><creatorcontrib>Portilla, Ana</creatorcontrib><creatorcontrib>Rodríguez, José</creatorcontrib><title>Gromov Hyperbolicity in Mycielskian Graphs</title><title>Symmetry (Basel)</title><description>Since the characterization of Gromov hyperbolic graphs seems a too ambitious task, there are many papers studying the hyperbolicity of several classes of graphs. In this paper, it is proven that every Mycielskian graph GM is hyperbolic and that δ(GM) is comparable to diam(GM) . Furthermore, we study the extremal problems of finding the smallest and largest hyperbolicity constants of such graphs; in fact, it is shown that 5/4≤δ(GM)≤5/2 . Graphs G whose Mycielskian have hyperbolicity constant 5/4 or 5/2 are characterized. The hyperbolicity constants of the Mycielskian of path, cycle, complete and complete bipartite graphs are calculated explicitly. Finally, information on δ(G) just in terms of δ(GM) is obtained.</description><subject>extremal problems on graphs</subject><subject>geodesics</subject><subject>Graphs</subject><subject>Gromov hyperbolicity</subject><subject>Mycielskian graphs</subject><issn>2073-8994</issn><issn>2073-8994</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><sourceid>DOA</sourceid><recordid>eNpNkEFLAzEQhYMoWGov_oIFb4XVSWazSY5StBUqXvQcstmspm6bNdkK--_dWlHnMsPw-N7jEXJJ4RpRwU0atgokUKQnZMJAYC6VKk7_3edkltIGxuHAixImZL6MYRs-s9XQuViF1lvfD5nfZY-D9a5N797ssmU03Vu6IGeNaZOb_ewpebm_e16s8vXT8mFxu84tlrTPnWWl5GjBKYb0kMdB7aQArpqCKymQU1nLSlQULBrqUFqOrK4MFbxiDKfk4citg9noLvqtiYMOxuvvR4iv2sTe29Zpw0anBoTkjS1sIaSgsuFlzWzDkVfFyLo6sroYPvYu9XoT9nE3xtdUoRIoqIBRNT-qbAwpRdf8ulLQh2r1X7X4BU7maHU</recordid><startdate>20170801</startdate><enddate>20170801</enddate><creator>Granados, Ana</creator><creator>Pestana, Domingo</creator><creator>Portilla, Ana</creator><creator>Rodríguez, José</creator><general>MDPI AG</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SR</scope><scope>7U5</scope><scope>8BQ</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>H8D</scope><scope>HCIFZ</scope><scope>JG9</scope><scope>JQ2</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>DOA</scope></search><sort><creationdate>20170801</creationdate><title>Gromov Hyperbolicity in Mycielskian Graphs</title><author>Granados, Ana ; Pestana, Domingo ; Portilla, Ana ; Rodríguez, José</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c361t-ec26853c0e92310801e0de87059f459873518d8b7b10c3a1e38c532dba175b223</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>extremal problems on graphs</topic><topic>geodesics</topic><topic>Graphs</topic><topic>Gromov hyperbolicity</topic><topic>Mycielskian graphs</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Granados, Ana</creatorcontrib><creatorcontrib>Pestana, Domingo</creatorcontrib><creatorcontrib>Portilla, Ana</creatorcontrib><creatorcontrib>Rodríguez, José</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Engineered Materials Abstracts</collection><collection>Solid State and Superconductivity Abstracts</collection><collection>METADEX</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni Edition)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Aerospace Database</collection><collection>SciTech Premium Collection</collection><collection>Materials Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Engineering 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><collection>Engineering Database</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection><collection>DOAJ Directory of Open Access Journals</collection><jtitle>Symmetry (Basel)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Granados, Ana</au><au>Pestana, Domingo</au><au>Portilla, Ana</au><au>Rodríguez, José</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Gromov Hyperbolicity in Mycielskian Graphs</atitle><jtitle>Symmetry (Basel)</jtitle><date>2017-08-01</date><risdate>2017</risdate><volume>9</volume><issue>8</issue><spage>131</spage><pages>131-</pages><issn>2073-8994</issn><eissn>2073-8994</eissn><abstract>Since the characterization of Gromov hyperbolic graphs seems a too ambitious task, there are many papers studying the hyperbolicity of several classes of graphs. In this paper, it is proven that every Mycielskian graph GM is hyperbolic and that δ(GM) is comparable to diam(GM) . Furthermore, we study the extremal problems of finding the smallest and largest hyperbolicity constants of such graphs; in fact, it is shown that 5/4≤δ(GM)≤5/2 . Graphs G whose Mycielskian have hyperbolicity constant 5/4 or 5/2 are characterized. The hyperbolicity constants of the Mycielskian of path, cycle, complete and complete bipartite graphs are calculated explicitly. Finally, information on δ(G) just in terms of δ(GM) is obtained.</abstract><cop>Basel</cop><pub>MDPI AG</pub><doi>10.3390/sym9080131</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2073-8994
ispartof Symmetry (Basel), 2017-08, Vol.9 (8), p.131
issn 2073-8994
2073-8994
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_a2853f0785fc4c478718f56d2cf535b4
source Publicly Available Content Database
subjects extremal problems on graphs
geodesics
Graphs
Gromov hyperbolicity
Mycielskian graphs
title Gromov Hyperbolicity in Mycielskian Graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T05%3A16%3A37IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Gromov%20Hyperbolicity%20in%20Mycielskian%20Graphs&rft.jtitle=Symmetry%20(Basel)&rft.au=Granados,%20Ana&rft.date=2017-08-01&rft.volume=9&rft.issue=8&rft.spage=131&rft.pages=131-&rft.issn=2073-8994&rft.eissn=2073-8994&rft_id=info:doi/10.3390/sym9080131&rft_dat=%3Cproquest_doaj_%3E1939737170%3C/proquest_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c361t-ec26853c0e92310801e0de87059f459873518d8b7b10c3a1e38c532dba175b223%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1939737170&rft_id=info:pmid/&rfr_iscdi=true