On the independence number of random cubic graphs

We show that as n→∞, the independence number α(G), for almost all 3‐regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ϵ)n, for any constant ϵ>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 1994-12, Vol.5 (5), p.649-664
Main Authors: Frieze, Alan, Suen, Stephen
Format: Article
Language:English
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-c3934-8fa79fe8bdab7dd09ca883a5503f7c80dca8ed3e21ae67a4de443e0dbacddc573
cites cdi_FETCH-LOGICAL-c3934-8fa79fe8bdab7dd09ca883a5503f7c80dca8ed3e21ae67a4de443e0dbacddc573
container_end_page 664
container_issue 5
container_start_page 649
container_title Random structures & algorithms
container_volume 5
creator Frieze, Alan
Suen, Stephen
description We show that as n→∞, the independence number α(G), for almost all 3‐regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ϵ)n, for any constant ϵ>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.
doi_str_mv 10.1002/rsa.3240050504
format article
fullrecord <record><control><sourceid>istex_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1002_rsa_3240050504</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>ark_67375_WNG_PQK4Q7SS_L</sourcerecordid><originalsourceid>FETCH-LOGICAL-c3934-8fa79fe8bdab7dd09ca883a5503f7c80dca8ed3e21ae67a4de443e0dbacddc573</originalsourceid><addsrcrecordid>eNqFj8FKAzEQhoMoWKtXz3mBrZNMtskeS9EqFqtW8RiyyaxdbbcladG-vVsqiicZmPkH5hv4GDsX0BMA8iIm10OpAPK21AHrCChMJpUwh7usZFYYlMfsJKU3ANAoscPEpOHrGfG6CbSitjWeeLNZlBT5suLRNWG54H5T1p6_RreapVN2VLl5orPv2WXPV5dPw-tsPBndDAfjzGOBKjOV00VFpgyu1CFA4Z0x6PIcsNLeQGh3CkhSOOprpwIphQShdD4En2vsst7-r4_LlCJVdhXrhYtbK8DuhG0rbH-FW6DYAx_1nLb_XNvH6eAPm-3ZOq3p84d18d32NercvtyN7P3DrXrQ06kd4xcRemnH</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>On the independence number of random cubic graphs</title><source>Wiley Online Library Mathematics Backfiles</source><creator>Frieze, Alan ; Suen, Stephen</creator><creatorcontrib>Frieze, Alan ; Suen, Stephen</creatorcontrib><description>We show that as n→∞, the independence number α(G), for almost all 3‐regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ϵ)n, for any constant ϵ&gt;0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley &amp; Sons, Inc.</description><identifier>ISSN: 1042-9832</identifier><identifier>EISSN: 1098-2418</identifier><identifier>DOI: 10.1002/rsa.3240050504</identifier><language>eng</language><publisher>New York: Wiley Subscription Services, Inc., A Wiley Company</publisher><ispartof>Random structures &amp; algorithms, 1994-12, Vol.5 (5), p.649-664</ispartof><rights>Copyright © 1994 Wiley Periodicals, Inc., A Wiley Company</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c3934-8fa79fe8bdab7dd09ca883a5503f7c80dca8ed3e21ae67a4de443e0dbacddc573</citedby><cites>FETCH-LOGICAL-c3934-8fa79fe8bdab7dd09ca883a5503f7c80dca8ed3e21ae67a4de443e0dbacddc573</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://onlinelibrary.wiley.com/doi/pdf/10.1002%2Frsa.3240050504$$EPDF$$P50$$Gwiley$$H</linktopdf><linktohtml>$$Uhttps://onlinelibrary.wiley.com/doi/full/10.1002%2Frsa.3240050504$$EHTML$$P50$$Gwiley$$H</linktohtml><link.rule.ids>314,776,780,27901,27902,50834,50943</link.rule.ids></links><search><creatorcontrib>Frieze, Alan</creatorcontrib><creatorcontrib>Suen, Stephen</creatorcontrib><title>On the independence number of random cubic graphs</title><title>Random structures &amp; algorithms</title><addtitle>Random Struct. Alg</addtitle><description>We show that as n→∞, the independence number α(G), for almost all 3‐regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ϵ)n, for any constant ϵ&gt;0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley &amp; Sons, Inc.</description><issn>1042-9832</issn><issn>1098-2418</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1994</creationdate><recordtype>article</recordtype><recordid>eNqFj8FKAzEQhoMoWKtXz3mBrZNMtskeS9EqFqtW8RiyyaxdbbcladG-vVsqiicZmPkH5hv4GDsX0BMA8iIm10OpAPK21AHrCChMJpUwh7usZFYYlMfsJKU3ANAoscPEpOHrGfG6CbSitjWeeLNZlBT5suLRNWG54H5T1p6_RreapVN2VLl5orPv2WXPV5dPw-tsPBndDAfjzGOBKjOV00VFpgyu1CFA4Z0x6PIcsNLeQGh3CkhSOOprpwIphQShdD4En2vsst7-r4_LlCJVdhXrhYtbK8DuhG0rbH-FW6DYAx_1nLb_XNvH6eAPm-3ZOq3p84d18d32NercvtyN7P3DrXrQ06kd4xcRemnH</recordid><startdate>199412</startdate><enddate>199412</enddate><creator>Frieze, Alan</creator><creator>Suen, Stephen</creator><general>Wiley Subscription Services, Inc., A Wiley Company</general><scope>BSCLL</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>199412</creationdate><title>On the independence number of random cubic graphs</title><author>Frieze, Alan ; Suen, Stephen</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c3934-8fa79fe8bdab7dd09ca883a5503f7c80dca8ed3e21ae67a4de443e0dbacddc573</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1994</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Frieze, Alan</creatorcontrib><creatorcontrib>Suen, Stephen</creatorcontrib><collection>Istex</collection><collection>CrossRef</collection><jtitle>Random structures &amp; algorithms</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Frieze, Alan</au><au>Suen, Stephen</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On the independence number of random cubic graphs</atitle><jtitle>Random structures &amp; algorithms</jtitle><addtitle>Random Struct. Alg</addtitle><date>1994-12</date><risdate>1994</risdate><volume>5</volume><issue>5</issue><spage>649</spage><epage>664</epage><pages>649-664</pages><issn>1042-9832</issn><eissn>1098-2418</eissn><abstract>We show that as n→∞, the independence number α(G), for almost all 3‐regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ϵ)n, for any constant ϵ&gt;0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley &amp; Sons, Inc.</abstract><cop>New York</cop><pub>Wiley Subscription Services, Inc., A Wiley Company</pub><doi>10.1002/rsa.3240050504</doi><tpages>16</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1042-9832
ispartof Random structures & algorithms, 1994-12, Vol.5 (5), p.649-664
issn 1042-9832
1098-2418
language eng
recordid cdi_crossref_primary_10_1002_rsa_3240050504
source Wiley Online Library Mathematics Backfiles
title On the independence number of random cubic graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-31T02%3A56%3A14IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-istex_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=On%20the%20independence%20number%20of%20random%20cubic%20graphs&rft.jtitle=Random%20structures%20&%20algorithms&rft.au=Frieze,%20Alan&rft.date=1994-12&rft.volume=5&rft.issue=5&rft.spage=649&rft.epage=664&rft.pages=649-664&rft.issn=1042-9832&rft.eissn=1098-2418&rft_id=info:doi/10.1002/rsa.3240050504&rft_dat=%3Cistex_cross%3Eark_67375_WNG_PQK4Q7SS_L%3C/istex_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c3934-8fa79fe8bdab7dd09ca883a5503f7c80dca8ed3e21ae67a4de443e0dbacddc573%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true