CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Well-covered graph - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"34685447-0148-43d4-9a64-04bb2c034c39","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Well-covered_graph","wgTitle":"Well-covered graph","wgCurRevisionId":1235224887,"wgRevisionId":1235224887,"wgArticleId":32696387,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Good articles","Graph families"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Well-covered_graph","wgRelevantArticleId":32696387,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{ "status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q7981049","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready", "ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns", "ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.16"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/9/94/Well-covered_graph.svg/1200px-Well-covered_graph.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1145"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/9/94/Well-covered_graph.svg/800px-Well-covered_graph.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="763"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/9/94/Well-covered_graph.svg/640px-Well-covered_graph.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="611"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Well-covered graph - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Well-covered_graph"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Well-covered_graph&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Well-covered_graph"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Well-covered_graph rootpage-Well-covered_graph skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Well-covered+graph" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Well-covered+graph" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Well-covered+graph" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Well-covered+graph" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Definitions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definitions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definitions</span> </div> </a> <ul id="toc-Definitions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bipartiteness,_very_well_covered_graphs,_and_girth" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bipartiteness,_very_well_covered_graphs,_and_girth"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Bipartiteness, very well covered graphs, and girth</span> </div> </a> <ul id="toc-Bipartiteness,_very_well_covered_graphs,_and_girth-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Regularity_and_planarity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Regularity_and_planarity"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Regularity and planarity</span> </div> </a> <ul id="toc-Regularity_and_planarity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Complexity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Complexity</span> </div> </a> <ul id="toc-Complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Well-covered graph</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 1 language" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-1" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">1 language</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A5%D0%BE%D1%80%D0%BE%D1%88%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84" title="Хорошо покрытый граф – Russian" lang="ru" hreflang="ru" data-title="Хорошо покрытый граф" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q7981049#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Well-covered_graph" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Well-covered_graph" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Well-covered_graph"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Well-covered_graph&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Well-covered_graph&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Well-covered_graph"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Well-covered_graph&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Well-covered_graph&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Well-covered_graph" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Well-covered_graph" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Well-covered_graph&oldid=1235224887" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Well-covered_graph&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Well-covered_graph&id=1235224887&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FWell-covered_graph"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FWell-covered_graph"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Well-covered_graph&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Well-covered_graph&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q7981049" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> <div id="mw-indicator-good-star" class="mw-indicator"><div class="mw-parser-output"><span typeof="mw:File"><a href="/wiki/Wikipedia:Good_articles*" title="This is a good article. Click here for more information."><img alt="This is a good article. Click here for more information." src="//upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/19px-Symbol_support_vote.svg.png" decoding="async" width="19" height="20" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/29px-Symbol_support_vote.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/39px-Symbol_support_vote.svg.png 2x" data-file-width="180" data-file-height="185" /></a></span></div></div> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Graph with equal-size maximal independent sets</div> <p class="mw-empty-elt"> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Well-covered_graph.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/94/Well-covered_graph.svg/220px-Well-covered_graph.svg.png" decoding="async" width="220" height="210" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/94/Well-covered_graph.svg/330px-Well-covered_graph.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/94/Well-covered_graph.svg/440px-Well-covered_graph.svg.png 2x" data-file-width="196" data-file-height="187" /></a><figcaption>A well-covered graph, the <a href="/wiki/Intersection_graph" title="Intersection graph">intersection graph</a> of the nine diagonals of a <a href="/wiki/Hexagon" title="Hexagon">hexagon</a>. The three red vertices form one of its 14 equal-sized maximal independent sets, and the six blue vertices form the complementary minimal vertex cover.</figcaption></figure> <p>In <a href="/wiki/Graph_theory" title="Graph theory">graph theory</a>, a <b>well-covered graph</b> is an <a href="/wiki/Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a> in which the minimal vertex covers all have the same size. Here, a <a href="/wiki/Vertex_cover" title="Vertex cover">vertex cover</a> is a set of vertices that touches all edges, and it is <a href="/wiki/Minimal_element" class="mw-redirect" title="Minimal element">minimal</a> if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs are the graphs in which all <a href="/wiki/Maximal_independent_set" title="Maximal independent set">maximal independent sets</a> have equal size. Well-covered graphs were defined and first studied by <a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Michael D. Plummer</a> in 1970. </p><p>The well-covered graphs include all <a href="/wiki/Complete_graph" title="Complete graph">complete graphs</a>, balanced <a href="/wiki/Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graphs</a>, and the <a href="/wiki/Rook%27s_graph" title="Rook's graph">rook's graphs</a> whose vertices represent squares of a chessboard and edges represent moves of a chess rook. Known characterizations of the well-covered <a href="/wiki/Cubic_graph" title="Cubic graph">cubic graphs</a>, well-covered <a href="/wiki/Claw-free_graph" title="Claw-free graph">claw-free graphs</a>, and well-covered graphs of high <a href="/wiki/Girth_(graph_theory)" title="Girth (graph theory)">girth</a> allow these graphs to be recognized in <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, but testing whether other kinds of graph are well-covered is a <a href="/wiki/CoNP-complete" class="mw-redirect" title="CoNP-complete">coNP-complete</a> problem. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Well-covered_graph&action=edit&section=1" title="Edit section: Definitions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A vertex cover in an <a href="/wiki/Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a> is a set of vertices that touches every edge in the graph. A vertex cover is minimal, or irredundant, if removing any vertex from it would destroy the covering property: the removal would cause some edge to become uncovered. It is minimum if there is no other vertex cover with fewer vertices. A well-covered graph is one in which every minimal cover is also minimum. In the original paper defining well-covered graphs, Plummer writes that this is "obviously equivalent" to the property that every two minimal covers have the same number of vertices as each other.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>An <a href="/wiki/Independent_set_(graph_theory)" title="Independent set (graph theory)">independent set</a> in a graph is a set of vertices no two of which are adjacent to each other. If <span class="texhtml mvar" style="font-style:italic;">C</span> is a vertex cover in a graph <span class="texhtml mvar" style="font-style:italic;">G</span>, the <a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">complement</a> of <span class="texhtml mvar" style="font-style:italic;">C</span> must be an independent set, and vice versa. <span class="texhtml mvar" style="font-style:italic;">C</span> is a minimal vertex cover if and only if its complement <span class="texhtml mvar" style="font-style:italic;">I</span> is a maximal independent set, and <span class="texhtml mvar" style="font-style:italic;">C</span> is a minimum vertex cover if and only if its complement is a maximum independent set. Therefore, a well-covered graph is, equivalently, a graph in which every maximal independent set has the same size, or a graph in which every maximal independent set is maximum.<sup id="cite_ref-FOOTNOTEPlummer1993_2-0" class="reference"><a href="#cite_note-FOOTNOTEPlummer1993-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>In the original paper defining well-covered graphs, these definitions were restricted to <a href="/wiki/Connectivity_(graph_theory)" title="Connectivity (graph theory)">connected graphs</a>,<sup id="cite_ref-FOOTNOTEPlummer1970_3-0" class="reference"><a href="#cite_note-FOOTNOTEPlummer1970-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> although they are meaningful for disconnected graphs as well. Some later authors have replaced the connectivity requirement with the weaker requirement that a well-covered graph must not have any isolated vertices.<sup id="cite_ref-FOOTNOTEFavaron1982_4-0" class="reference"><a href="#cite_note-FOOTNOTEFavaron1982-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> For both connected well-covered graphs and well-covered graphs without isolated vertices, there can be no <i>essential vertices</i>, vertices which belong to every minimum vertex cover. Additionally, every well-covered graph is a <a href="/wiki/Critical_graph" title="Critical graph">critical graph</a> for vertex covering in the sense that, for every vertex <span class="texhtml mvar" style="font-style:italic;">v</span>, deleting <span class="texhtml mvar" style="font-style:italic;">v</span> from the graph produces a graph with a smaller minimum vertex cover.<sup id="cite_ref-FOOTNOTEPlummer1970_3-1" class="reference"><a href="#cite_note-FOOTNOTEPlummer1970-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>The <a href="/wiki/Clique_complex" title="Clique complex">independence complex</a> of a graph <span class="texhtml mvar" style="font-style:italic;">G</span> is the <a href="/wiki/Simplicial_complex" title="Simplicial complex">simplicial complex</a> having a simplex for each independent set in <span class="texhtml mvar" style="font-style:italic;">G</span>. A simplicial complex is said to be pure if all its maximal simplices have the same cardinality, so a well-covered graph is equivalently a graph with a pure independence complex.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Well-covered_graph&action=edit&section=2" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="chessboard thumb noviewer tright"><div class="center" style="line-height:130%;margin:0 auto;max-width:254px"> </div><div class="thumbinner" style="width:246px"><table cellpadding="0" cellspacing="0"><tbody><tr><td></td><td style="height:18px;width:26px">a</td><td style="height:18px;width:26px">b</td><td style="height:18px;width:26px">c</td><td style="height:18px;width:26px">d</td><td style="height:18px;width:26px">e</td><td style="height:18px;width:26px">f</td><td style="height:18px;width:26px">g</td><td style="height:18px;width:26px">h</td><td></td></tr><tr><td style="width:18px;height:26px">8</td><td colspan="8" rowspan="8"><div class="chess-pieces notheme" style="position:relative"><span class="notpageimage" typeof="mw:File"><span><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Chessboard480.svg/208px-Chessboard480.svg.png" decoding="async" width="208" height="208" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Chessboard480.svg/312px-Chessboard480.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Chessboard480.svg/416px-Chessboard480.svg.png 2x" data-file-width="480" data-file-height="480" /></span></span><div style="top:0px;left:78px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="d8 white rook"><img alt="d8 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div><div style="top:26px;left:156px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="g7 white rook"><img alt="g7 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div><div style="top:52px;left:52px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="c6 white rook"><img alt="c6 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div><div style="top:78px;left:0px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="a5 white rook"><img alt="a5 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div><div style="top:104px;left:26px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="b4 white rook"><img alt="b4 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div><div style="top:130px;left:182px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="h3 white rook"><img alt="h3 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div><div style="top:156px;left:104px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="e2 white rook"><img alt="e2 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div><div style="top:182px;left:130px"><span class="mw-valign-top notpageimage" typeof="mw:File"><span title="f1 white rook"><img alt="f1 white rook" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/26px-Chess_rlt45.svg.png" decoding="async" width="26" height="26" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/39px-Chess_rlt45.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Chess_rlt45.svg/52px-Chess_rlt45.svg.png 2x" data-file-width="45" data-file-height="45" /></span></span></div></div></td><td style="width:18px;height:26px">8</td></tr><tr><td style="height:26px">7</td><td style="height:26px">7</td></tr><tr><td style="height:26px">6</td><td style="height:26px">6</td></tr><tr><td style="height:26px">5</td><td style="height:26px">5</td></tr><tr><td style="height:26px">4</td><td style="height:26px">4</td></tr><tr><td style="height:26px">3</td><td style="height:26px">3</td></tr><tr><td style="height:26px">2</td><td style="height:26px">2</td></tr><tr><td style="height:26px">1</td><td style="height:26px">1</td></tr><tr><td></td><td style="height:18px;width:26px">a</td><td style="height:18px;width:26px">b</td><td style="height:18px;width:26px">c</td><td style="height:18px;width:26px">d</td><td style="height:18px;width:26px">e</td><td style="height:18px;width:26px">f</td><td style="height:18px;width:26px">g</td><td style="height:18px;width:26px">h</td><td></td></tr></tbody></table><div class="thumbcaption">A non-attacking placement of eight rooks on a chessboard. If fewer than eight rooks are placed in a non-attacking way on a chessboard, they can always be extended to eight rooks that remain non-attacking. </div></div></div><style data-mw-deduplicate="TemplateStyles:r1271734817">.mw-parser-output .chessboard table{font-size:88%;border:1px #c8ccd1 solid;padding:0;margin:auto}.mw-parser-output .chessboard table tr{vertical-align:middle}.mw-parser-output .chessboard table td{padding:0;vertical-align:inherit;text-align:center}.mw-parser-output .chessboard table td[rowspan]{text-align:unset}.mw-parser-output .chessboard .chess-pieces div{position:absolute;z-index:3}</style> <p>A <a href="/wiki/Cycle_graph" title="Cycle graph">cycle graph</a> of length four or five is well-covered: in each case, every maximal independent set has size two. A cycle of length seven, and a path of length three, are also well-covered.<sup id="cite_ref-FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7_6-0" class="reference"><a href="#cite_note-FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Every <a href="/wiki/Complete_graph" title="Complete graph">complete graph</a> is well-covered: every maximal independent set consists of a single vertex. Similarly, every <a href="/wiki/Cluster_graph" title="Cluster graph">cluster graph</a> (a disjoint union of complete graphs) is well-covered.<sup id="cite_ref-FOOTNOTEHolroydTalbot2005_7-0" class="reference"><a href="#cite_note-FOOTNOTEHolroydTalbot2005-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> A <a href="/wiki/Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a> is well covered if the two sides of its bipartition have equal numbers of vertices, for these are its only two maximal independent sets. The <a href="/wiki/Complement_graph" title="Complement graph">complement graph</a> of a <a href="/wiki/Triangle-free_graph" title="Triangle-free graph">triangle-free graph</a> with no <a href="/wiki/Isolated_vertex" class="mw-redirect" title="Isolated vertex">isolated vertices</a> is well-covered: it has no independent sets larger than two, and every single vertex can be extended to a two-vertex independent set.<sup id="cite_ref-FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7_6-1" class="reference"><a href="#cite_note-FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p><p>A <a href="/wiki/Rook%27s_graph" title="Rook's graph">rook's graph</a> is well covered: if one places any set of <a href="/wiki/Rook_(chess)" title="Rook (chess)">rooks</a> on a <a href="/wiki/Chessboard" title="Chessboard">chessboard</a> so that no two rooks are attacking each other, it is always possible to continue placing more non-attacking rooks until there is one on every row and column of the chessboard.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> The graph whose vertices are the diagonals of a <a href="/wiki/Simple_polygon" title="Simple polygon">simple polygon</a> and whose edges connect pairs of diagonals that cross each other is well-covered, because its maximal independent sets are triangulations of the polygon and all triangulations have the same number of edges.<sup id="cite_ref-FOOTNOTEGreenberg1993_9-0" class="reference"><a href="#cite_note-FOOTNOTEGreenberg1993-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p><p>If <span class="texhtml mvar" style="font-style:italic;">G</span> is any <span class="texhtml mvar" style="font-style:italic;">n</span>-vertex graph, then the <a href="/wiki/Rooted_product_of_graphs" title="Rooted product of graphs">rooted product</a> of <span class="texhtml mvar" style="font-style:italic;">G</span> with a one-edge graph (that is, the graph <span class="texhtml mvar" style="font-style:italic;">H</span> formed by adding <span class="texhtml mvar" style="font-style:italic;">n</span> new vertices to <span class="texhtml mvar" style="font-style:italic;">G</span>, each of degree one and each adjacent to a distinct vertex in <span class="texhtml mvar" style="font-style:italic;">G</span>) is well-covered. For, a maximal independent set in <span class="texhtml mvar" style="font-style:italic;">H</span> must consist of an arbitrary independent set in <span class="texhtml mvar" style="font-style:italic;">G</span> together with the degree-one neighbors of the complementary set, and must therefore have size <span class="texhtml mvar" style="font-style:italic;">n</span>.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> More generally, given any graph <span class="texhtml mvar" style="font-style:italic;">G</span> together with a <a href="/wiki/Clique_cover" title="Clique cover">clique cover</a> (a partition <span class="texhtml mvar" style="font-style:italic;">p</span> of the vertices of <span class="texhtml mvar" style="font-style:italic;">G</span> into cliques), the graph <span class="texhtml mvar" style="font-style:italic;">G<sup>p</sup></span> formed by adding another vertex to each clique is well-covered; the rooted product is the special case of this construction when <span class="texhtml mvar" style="font-style:italic;">p</span> consists of <span class="texhtml mvar" style="font-style:italic;">n</span> one-vertex cliques.<sup id="cite_ref-cn10_11-0" class="reference"><a href="#cite_note-cn10-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Thus, every graph is an <a href="/wiki/Induced_subgraph" title="Induced subgraph">induced subgraph</a> of a well-covered graph. </p> <div class="mw-heading mw-heading2"><h2 id="Bipartiteness,_very_well_covered_graphs,_and_girth"><span id="Bipartiteness.2C_very_well_covered_graphs.2C_and_girth"></span>Bipartiteness, very well covered graphs, and girth</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Well-covered_graph&action=edit&section=3" title="Edit section: Bipartiteness, very well covered graphs, and girth"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="#CITEREFFavaron1982">Favaron (1982)</a> defines a <b>very well covered graph</b> to be a well-covered graph (possibly disconnected, but with no isolated vertices) in which each maximal independent set (and therefore also each minimal vertex cover) contains exactly half of the vertices. This definition includes the rooted products of a graph <span class="texhtml mvar" style="font-style:italic;">G</span> and a one-edge graph. It also includes, for instance, the bipartite well-covered graphs studied by <a href="#CITEREFRavindra1977">Ravindra (1977)</a> and <a href="#CITEREFBerge1981">Berge (1981)</a>: in a bipartite graph without isolated vertices, both sides of any bipartition form maximal independent sets (and minimal vertex covers), so if the graph is well-covered both sides must have equally many vertices. In a well-covered graph with <span class="texhtml mvar" style="font-style:italic;">n</span> vertices, without isolated vertices, the size of a maximum independent set is at most <span class="texhtml"><i>n</i>/2</span>, so very well covered graphs are the well covered graphs in which the maximum independent set size is as large as possible.<sup id="cite_ref-FOOTNOTEBerge1981_12-0" class="reference"><a href="#cite_note-FOOTNOTEBerge1981-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </p><p>A bipartite graph <span class="texhtml mvar" style="font-style:italic;">G</span> is well-covered if and only if it has a <a href="/wiki/Perfect_matching" title="Perfect matching">perfect matching</a> <span class="texhtml mvar" style="font-style:italic;">M</span> with the property that, for every edge <span class="texhtml mvar" style="font-style:italic;">uv</span> in <span class="texhtml mvar" style="font-style:italic;">M</span>, the <a href="/wiki/Induced_subgraph" title="Induced subgraph">induced subgraph</a> of the neighbors of <span class="texhtml mvar" style="font-style:italic;">u</span> and <span class="texhtml mvar" style="font-style:italic;">v</span> forms a <a href="/wiki/Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a>.<sup id="cite_ref-r77p93_13-0" class="reference"><a href="#cite_note-r77p93-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> The characterization in terms of matchings can be extended from bipartite graphs to very well covered graphs: a graph <span class="texhtml mvar" style="font-style:italic;">G</span> is very well covered if and only if it has a perfect matching <span class="texhtml mvar" style="font-style:italic;">M</span> with the following two properties: </p> <ol><li>No edge of <span class="texhtml mvar" style="font-style:italic;">M</span> belongs to a triangle in <span class="texhtml mvar" style="font-style:italic;">G</span>, and</li> <li>If an edge of <span class="texhtml mvar" style="font-style:italic;">M</span> is the central edge of a three-edge path in <span class="texhtml mvar" style="font-style:italic;">G</span>, then the two endpoints of the path must be adjacent.</li></ol> <p>Moreover, if <span class="texhtml mvar" style="font-style:italic;">G</span> is very well covered, then every perfect matching in <span class="texhtml mvar" style="font-style:italic;">G</span> satisfies these properties.<sup id="cite_ref-sfp_14-0" class="reference"><a href="#cite_note-sfp-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </p><p>Trees are a special case of bipartite graphs, and testing whether a tree is well-covered can be handled as a much simpler special case of the characterization of well-covered bipartite graphs: if <span class="texhtml mvar" style="font-style:italic;">G</span> is a tree with more than two vertices, it is well-covered if and only if each non-leaf node of the tree is adjacent to exactly one leaf.<sup id="cite_ref-r77p93_13-1" class="reference"><a href="#cite_note-r77p93-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> The same characterization applies to graphs that are locally tree-like, in the sense that low-diameter neighborhoods of every vertex are acyclic: if a graph has <a href="/wiki/Girth_(graph_theory)" title="Girth (graph theory)">girth</a> eight or more (so that, for every vertex <span class="texhtml mvar" style="font-style:italic;">v</span>, the subgraph of vertices within distance three of <span class="texhtml mvar" style="font-style:italic;">v</span> is acyclic) then it is well-covered if and only if every vertex of <a href="/wiki/Degree_(graph_theory)" title="Degree (graph theory)">degree</a> greater than one has exactly one neighbor of degree one.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> A closely related but more complex characterization applies to well-covered graphs of girth five or more.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Regularity_and_planarity">Regularity and planarity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Well-covered_graph&action=edit&section=4" title="Edit section: Regularity and planarity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:3r3c_well-covered.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/50/3r3c_well-covered.svg/400px-3r3c_well-covered.svg.png" decoding="async" width="400" height="196" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/50/3r3c_well-covered.svg/600px-3r3c_well-covered.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/50/3r3c_well-covered.svg/800px-3r3c_well-covered.svg.png 2x" data-file-width="711" data-file-height="348" /></a><figcaption>The seven cubic 3-connected well-covered graphs</figcaption></figure> <figure typeof="mw:File/Thumb"><a href="/wiki/File:3r1c_well-covered.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/74/3r1c_well-covered.svg/240px-3r1c_well-covered.svg.png" decoding="async" width="240" height="149" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/74/3r1c_well-covered.svg/360px-3r1c_well-covered.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/74/3r1c_well-covered.svg/480px-3r1c_well-covered.svg.png 2x" data-file-width="756" data-file-height="468" /></a><figcaption>A cubic 1-connected well-covered graph, formed by replacing each node of a six-node path by one of three fragments</figcaption></figure> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Snub_disphenoid.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Snub_disphenoid.png/220px-Snub_disphenoid.png" decoding="async" width="220" height="282" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Snub_disphenoid.png/330px-Snub_disphenoid.png 1.5x, //upload.wikimedia.org/wikipedia/commons/e/e2/Snub_disphenoid.png 2x" data-file-width="344" data-file-height="441" /></a><figcaption>The <a href="/wiki/Snub_disphenoid" title="Snub disphenoid">snub disphenoid</a>, one of four well-covered 4-connected 3-dimensional simplicial polyhedra.</figcaption></figure> <p>The <a href="/wiki/Cubic_graph" title="Cubic graph">cubic</a> (<a href="/wiki/Regular_graph" title="Regular graph">3-regular</a>) well-covered graphs have been classified: they consist of seven <a href="/wiki/K-vertex-connected_graph" title="K-vertex-connected graph">3-connected</a> examples, together with three infinite families of cubic graphs with lesser connectivity.<sup id="cite_ref-ccpp_17-0" class="reference"><a href="#cite_note-ccpp-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p><p>The seven 3-connected cubic well-covered graphs are the <a href="/wiki/Complete_graph" title="Complete graph">complete graph</a> <span class="texhtml"><i>K</i><sub>4</sub></span>, the graphs of the <a href="/wiki/Triangular_prism" title="Triangular prism">triangular prism</a> and the <a href="/wiki/Pentagonal_prism" title="Pentagonal prism">pentagonal prism</a>, the <a href="/wiki/D%C3%BCrer_graph" title="Dürer graph">Dürer graph</a>, the <a href="/wiki/Utility_graph" class="mw-redirect" title="Utility graph">utility graph</a> <span class="texhtml"><i>K</i><sub>3,3</sub></span>, an eight-vertex graph obtained from the utility graph by a <a href="/wiki/Y%CE%94-_and_%CE%94Y-transformation" title="YΔ- and ΔY-transformation">Y-Δ transform</a>, and the 14-vertex <a href="/wiki/Generalized_Petersen_graph" title="Generalized Petersen graph">generalized Petersen graph</a> <span class="texhtml"><i>G</i>(7,2)</span>.<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> Of these graphs, the first four are <a href="/wiki/Planar_graph" title="Planar graph">planar graphs</a>. They are the only four cubic <a href="/wiki/Polyhedral_graph" title="Polyhedral graph">polyhedral graphs</a> (graphs of <a href="/wiki/Simple_polytope" title="Simple polytope">simple</a> <a href="/wiki/Convex_polyhedron" class="mw-redirect" title="Convex polyhedron">convex polyhedra</a>) that are well-covered.<sup id="cite_ref-FOOTNOTECampbellPlummer1988_19-0" class="reference"><a href="#cite_note-FOOTNOTECampbellPlummer1988-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> Four of the graphs (the two prisms, the Dürer graph, and <span class="texhtml"><i>G</i>(7,2)</span>) are generalized Petersen graphs. </p><p>The 1- and 2-connected cubic well-covered graphs are all formed by replacing the nodes of a path or cycle by three fragments of graphs which <a href="#CITEREFPlummer1993">Plummer (1993)</a> labels <span class="texhtml mvar" style="font-style:italic;">A</span>, <span class="texhtml mvar" style="font-style:italic;">B</span>, and <span class="texhtml mvar" style="font-style:italic;">C</span>. Fragments <span class="texhtml mvar" style="font-style:italic;">A</span> or <span class="texhtml mvar" style="font-style:italic;">B</span> may be used to replace the nodes of a cycle or the interior nodes of a path, while fragment <span class="texhtml mvar" style="font-style:italic;">C</span> is used to replace the two end nodes of a path. Fragment <span class="texhtml mvar" style="font-style:italic;">A</span> contains a <a href="/wiki/Bridge_(graph_theory)" title="Bridge (graph theory)">bridge</a>, so the result of performing this replacement process on a path and using fragment <span class="texhtml mvar" style="font-style:italic;">A</span> to replace some of the path nodes (and the other two fragments for the remaining nodes) is a 1-vertex-connected cubic well-covered graph. All 1-vertex-connected cubic well-covered graphs have this form, and all such graphs are planar.<sup id="cite_ref-ccpp_17-1" class="reference"><a href="#cite_note-ccpp-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p><p>There are two types of 2-vertex-connected cubic well-covered graphs. One of these two families is formed by replacing the nodes of a cycle by fragments <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span>, with at least two of the fragments being of type <span class="texhtml mvar" style="font-style:italic;">A</span>; a graph of this type is planar if and only if it does not contain any fragments of type <span class="texhtml mvar" style="font-style:italic;">B</span>. The other family is formed by replacing the nodes of a path by fragments of type <span class="texhtml mvar" style="font-style:italic;">B</span> and <span class="texhtml mvar" style="font-style:italic;">C</span>; all such graphs are planar.<sup id="cite_ref-ccpp_17-2" class="reference"><a href="#cite_note-ccpp-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p><p>Complementing the characterization of well-covered simple polyhedra in three dimensions, researchers have also considered the well-covered <a href="/wiki/Simplicial_polytope" title="Simplicial polytope">simplicial polyhedra</a>, or equivalently the well-covered maximal planar graphs. Every maximal planar graph with five or more vertices has vertex connectivity 3, 4, or 5.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> There are no well-covered 5-connected maximal planar graphs, and there are only four 4-connected well-covered maximal planar graphs: the graphs of the <a href="/wiki/Regular_octahedron" class="mw-redirect" title="Regular octahedron">regular octahedron</a>, the <a href="/wiki/Pentagonal_dipyramid" class="mw-redirect" title="Pentagonal dipyramid">pentagonal dipyramid</a>, the <a href="/wiki/Snub_disphenoid" title="Snub disphenoid">snub disphenoid</a>, and an irregular polyhedron (a nonconvex <a href="/wiki/Deltahedron" title="Deltahedron">deltahedron</a>) with 12 vertices, 30 edges, and 20 triangular faces. However, there are infinitely many 3-connected well-covered maximal planar graphs.<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> For instance, if a <span class="texhtml">3<i>t</i></span>-vertex maximal planar graph has <span class="texhtml mvar" style="font-style:italic;">t</span> disjoint triangle faces, then these faces will form a clique cover. Therefore, the clique cover construction, which for these graphs consists of subdividing each of these <span class="texhtml mvar" style="font-style:italic;">t</span> triangles into three new triangles meeting at a central vertex, produces a well-covered maximal planar graph.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Well-covered_graph&action=edit&section=5" title="Edit section: Complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Testing whether a graph contains two maximal independent sets of different sizes is <a href="/wiki/NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>; that is, complementarily, testing whether a graph is well-covered is coNP-complete.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> Although it is easy to find maximum independent sets in graphs that are known to be well-covered, it is also NP-hard for an algorithm to produce as output, on all graphs, either a maximum independent set or a guarantee that the input is not well-covered.<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> </p><p>In contrast, it is possible to test whether a given graph <span class="texhtml mvar" style="font-style:italic;">G</span> is very well covered in <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>. To do so, find the subgraph <span class="texhtml mvar" style="font-style:italic;">H</span> of <span class="texhtml mvar" style="font-style:italic;">G</span> consisting of the edges that satisfy the two properties of a matched edge in a very well covered graph, and then use a matching algorithm to test whether <span class="texhtml mvar" style="font-style:italic;">H</span> has a perfect matching.<sup id="cite_ref-sfp_14-1" class="reference"><a href="#cite_note-sfp-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> Some problems that are NP-complete for arbitrary graphs, such as the problem of finding a <a href="/wiki/Hamiltonian_cycle" class="mw-redirect" title="Hamiltonian cycle">Hamiltonian cycle</a>, may also be solved in polynomial time for very well covered graphs.<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> </p><p>A graph is said to be <b>equimatchable</b> if every <a href="/wiki/Maximal_matching" class="mw-redirect" title="Maximal matching">maximal matching</a> is maximum; that is, it is equimatchable if its <a href="/wiki/Line_graph" title="Line graph">line graph</a> is well-covered.<sup id="cite_ref-FOOTNOTELeskPlummerPulleyblank1984_26-0" class="reference"><a href="#cite_note-FOOTNOTELeskPlummerPulleyblank1984-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup> More strongly it is called <b>randomly matchable</b> if every maximal matching is a <a href="/wiki/Perfect_matching" title="Perfect matching">perfect matching</a>. The only connected randomly matchable graphs are the complete graphs and the balanced complete bipartite graphs.<sup id="cite_ref-FOOTNOTESumner1979_27-0" class="reference"><a href="#cite_note-FOOTNOTESumner1979-27"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup> It is possible to test whether a line graph, or more generally a <a href="/wiki/Claw-free_graph" title="Claw-free graph">claw-free graph</a>, is well-covered in polynomial time.<sup id="cite_ref-28" class="reference"><a href="#cite_note-28"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></a></sup> </p><p>The characterizations of well-covered graphs with girth five or more, and of well-covered graphs that are 3-regular, also lead to efficient polynomial time algorithms to recognize these graphs.<sup id="cite_ref-29" class="reference"><a href="#cite_note-29"><span class="cite-bracket">[</span>29<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Well-covered_graph&action=edit&section=6" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a href="#CITEREFPlummer1970">Plummer (1970)</a>. Plummer uses "point" to mean a vertex in a graph, "line" to mean an edge, and "point cover" to mean a vertex cover; this terminology has fallen out of use.</span> </li> <li id="cite_note-FOOTNOTEPlummer1993-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEPlummer1993_2-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFPlummer1993">Plummer (1993)</a>.</span> </li> <li id="cite_note-FOOTNOTEPlummer1970-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTEPlummer1970_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTEPlummer1970_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFPlummer1970">Plummer (1970)</a>.</span> </li> <li id="cite_note-FOOTNOTEFavaron1982-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEFavaron1982_4-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFFavaron1982">Favaron (1982)</a>.</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">For examples of papers using this terminology, see <a href="#CITEREFDochtermannEngström2009">Dochtermann & Engström (2009)</a> and <a href="#CITEREFCookNagel2010">Cook & Nagel (2010)</a>.</span> </li> <li id="cite_note-FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTESankaranarayana1994Section_2.4,_"Examples",_p._7_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFSankaranarayana1994">Sankaranarayana (1994)</a>, Section 2.4, "Examples", p. 7.</span> </li> <li id="cite_note-FOOTNOTEHolroydTalbot2005-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEHolroydTalbot2005_7-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFHolroydTalbot2005">Holroyd & Talbot (2005)</a>.</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">The rook's graphs are, equivalently, the line graphs of complete bipartite graphs, so the well-covered property of rook's graphs is equivalent to the fact that complete bipartite graphs are equimatchable, for which see <a href="#CITEREFSumner1979">Sumner (1979)</a> and <a href="#CITEREFLeskPlummerPulleyblank1984">Lesk, Plummer & Pulleyblank (1984)</a>.</span> </li> <li id="cite_note-FOOTNOTEGreenberg1993-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEGreenberg1993_9-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFGreenberg1993">Greenberg (1993)</a>.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">This class of examples was studied by <a href="#CITEREFFinkJacobsonKinchRoberts1985">Fink et al. (1985)</a>; they are also (together with the four-edge cycle, which is also well-covered) exactly the graphs whose domination number is <span class="texhtml"><i>n</i>/2</span>. Its well-covering property is also stated in different terminology (having a pure independence complex) as Theorem 4.4 of <a href="#CITEREFDochtermannEngström2009">Dochtermann & Engström (2009)</a>.</span> </li> <li id="cite_note-cn10-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-cn10_11-0">^</a></b></span> <span class="reference-text">For the clique cover construction, see <a href="#CITEREFCookNagel2010">Cook & Nagel (2010)</a>, Lemma 3.2. This source states its results in terms of the purity of the independence complex, and uses the term "fully-whiskered" for the special case of the rooted product.</span> </li> <li id="cite_note-FOOTNOTEBerge1981-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEBerge1981_12-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFBerge1981">Berge (1981)</a>.</span> </li> <li id="cite_note-r77p93-13"><span class="mw-cite-backlink">^ <a href="#cite_ref-r77p93_13-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-r77p93_13-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFRavindra1977">Ravindra (1977)</a>; <a href="#CITEREFPlummer1993">Plummer (1993)</a>.</span> </li> <li id="cite_note-sfp-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-sfp_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-sfp_14-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFStaples1975">Staples (1975)</a>; <a href="#CITEREFFavaron1982">Favaron (1982)</a>; <a href="#CITEREFPlummer1993">Plummer (1993)</a>.</span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><a href="#CITEREFFinbowHartnell1983">Finbow & Hartnell (1983)</a>; <a href="#CITEREFPlummer1993">Plummer (1993)</a>, Theorem 4.1.</span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><a href="#CITEREFFinbowHartnell1983">Finbow & Hartnell (1983)</a>; <a href="#CITEREFPlummer1993">Plummer (1993)</a>, Theorem 4.2.</span> </li> <li id="cite_note-ccpp-17"><span class="mw-cite-backlink">^ <a href="#cite_ref-ccpp_17-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-ccpp_17-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-ccpp_17-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFCampbell1987">Campbell (1987)</a>; <a href="#CITEREFCampbellPlummer1988">Campbell & Plummer (1988)</a>; <a href="#CITEREFPlummer1993">Plummer (1993)</a>.</span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><a href="#CITEREFCampbell1987">Campbell (1987)</a>; <a href="#CITEREFFinbowHartnellNowakowski1988">Finbow, Hartnell & Nowakowski (1988)</a>; <a href="#CITEREFCampbellEllinghamRoyle1993">Campbell, Ellingham & Royle (1993)</a>; <a href="#CITEREFPlummer1993">Plummer (1993)</a>.</span> </li> <li id="cite_note-FOOTNOTECampbellPlummer1988-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTECampbellPlummer1988_19-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFCampbellPlummer1988">Campbell & Plummer (1988)</a>.</span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text">The complete graphs on 1, 2, 3, and 4 vertices are all maximal planar and well-covered; their vertex connectivity is either unbounded or at most three, depending on details of the definition of vertex connectivity that are irrelevant for larger maximal planar graphs.</span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text">Finbow, Hartnell, and Nowakowski et al. (<a href="#CITEREFFinbowHartnellNowakowskiPlummer2003">2003</a>, <a href="#CITEREFFinbowHartnellNowakowskiPlummer2009">2009</a>, <a href="#CITEREFFinbowHartnellNowakowskiPlummer2010">2010</a>).</span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text">The graphs constructed in this way are called the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{4}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K_{4}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe633da926900748cc19ee1ffec1853834a6c061" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle K_{4}}"></span>-family by <a href="#CITEREFFinbowHartnellNowakowskiPlummer2016">Finbow et al. (2016)</a>; additional examples can be constructed by an operation they call an O-join for combining smaller graphs.</span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><a href="#CITEREFSankaranarayanaStewart1992">Sankaranarayana & Stewart (1992)</a>; <a href="#CITEREFChvátalSlater1993">Chvátal & Slater (1993)</a>; <a href="#CITEREFCaroSebőTarsi1996">Caro, Sebő & Tarsi (1996)</a>.</span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><a href="#CITEREFRaghavanSpinrad2003">Raghavan & Spinrad (2003)</a>.</span> </li> <li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><a href="#CITEREFSankaranarayanaStewart1992">Sankaranarayana & Stewart (1992)</a>.</span> </li> <li id="cite_note-FOOTNOTELeskPlummerPulleyblank1984-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTELeskPlummerPulleyblank1984_26-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFLeskPlummerPulleyblank1984">Lesk, Plummer & Pulleyblank (1984)</a>.</span> </li> <li id="cite_note-FOOTNOTESumner1979-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTESumner1979_27-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFSumner1979">Sumner (1979)</a>.</span> </li> <li id="cite_note-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-28">^</a></b></span> <span class="reference-text"><a href="#CITEREFLeskPlummerPulleyblank1984">Lesk, Plummer & Pulleyblank (1984)</a>; <a href="#CITEREFTankusTarsi1996">Tankus & Tarsi (1996)</a>; <a href="#CITEREFTankusTarsi1997">Tankus & Tarsi (1997)</a>.</span> </li> <li id="cite_note-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-29">^</a></b></span> <span class="reference-text"><a href="#CITEREFCampbellEllinghamRoyle1993">Campbell, Ellingham & Royle (1993)</a>; <a href="#CITEREFPlummer1993">Plummer (1993)</a>.</span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Well-covered_graph&action=edit&section=7" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}</style><div class="refbegin refbegin-columns references-column-width" style="column-width: 30em"> <ul><li><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFBerge1981" class="citation cs2"><a href="/wiki/Claude_Berge" title="Claude Berge">Berge, Claude</a> (1981), "Some common properties for regularizable graphs, edge-critical graphs and <span class="texhtml mvar" style="font-style:italic;">B</span>-graphs", <i>Graph theory and algorithms (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980)</i>, Lecture Notes in Computer Science, vol. 108, Berlin: Springer, pp. <span class="nowrap">108–</span>123, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-10704-5_10">10.1007/3-540-10704-5_10</a></span>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-10704-0" title="Special:BookSources/978-3-540-10704-0"><bdi>978-3-540-10704-0</bdi></a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0622929">0622929</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Some+common+properties+for+regularizable+graphs%2C+edge-critical+graphs+and+%3Cspan+class%3D%22texhtml+mvar%22+style%3D%22font-style%3Aitalic%3B%22%3EB%3C%2Fspan%3E-graphs&rft.btitle=Graph+theory+and+algorithms+%28Proc.+Sympos.%2C+Res.+Inst.+Electr.+Comm.%2C+Tohoku+Univ.%2C+Sendai%2C+1980%29&rft.place=Berlin&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=%3Cspan+class%3D%22nowrap%22%3E108-%3C%2Fspan%3E123&rft.pub=Springer&rft.date=1981&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D622929%23id-name%3DMR&rft_id=info%3Adoi%2F10.1007%2F3-540-10704-5_10&rft.isbn=978-3-540-10704-0&rft.aulast=Berge&rft.aufirst=Claude&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCampbell1987" class="citation cs2">Campbell, S. R. (1987), <i>Some results on planar well-covered graphs</i>, Ph.D. thesis, Vanderbilt University, Department of Mathematics</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Some+results+on+planar+well-covered+graphs&rft.series=Ph.D.+thesis&rft.pub=Vanderbilt+University%2C+Department+of+Mathematics&rft.date=1987&rft.aulast=Campbell&rft.aufirst=S.+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>. As cited by <a href="#CITEREFPlummer1993">Plummer (1993)</a>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCampbellEllinghamRoyle1993" class="citation cs2">Campbell, S. R.; <a href="/wiki/Mark_Ellingham" title="Mark Ellingham">Ellingham, M. N.</a>; <a href="/wiki/Gordon_Royle" title="Gordon Royle">Royle, Gordon F.</a> (1993), "A characterisation of well-covered cubic graphs", <i>Journal of Combinatorial Mathematics and Combinatorial Computing</i>, <b>13</b>: <span class="nowrap">193–</span>212, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1220613">1220613</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Combinatorial+Mathematics+and+Combinatorial+Computing&rft.atitle=A+characterisation+of+well-covered+cubic+graphs&rft.volume=13&rft.pages=%3Cspan+class%3D%22nowrap%22%3E193-%3C%2Fspan%3E212&rft.date=1993&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1220613%23id-name%3DMR&rft.aulast=Campbell&rft.aufirst=S.+R.&rft.au=Ellingham%2C+M.+N.&rft.au=Royle%2C+Gordon+F.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCampbellPlummer1988" class="citation cs2">Campbell, Stephen R.; <a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (1988), "On well-covered 3-polytopes", <i><a href="/wiki/Ars_Combinatoria_(journal)" title="Ars Combinatoria (journal)">Ars Combinatoria</a></i>, <b>25</b> (A): <span class="nowrap">215–</span>242, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0942505">0942505</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Ars+Combinatoria&rft.atitle=On+well-covered+3-polytopes&rft.volume=25&rft.issue=A&rft.pages=%3Cspan+class%3D%22nowrap%22%3E215-%3C%2Fspan%3E242&rft.date=1988&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D942505%23id-name%3DMR&rft.aulast=Campbell&rft.aufirst=Stephen+R.&rft.au=Plummer%2C+Michael+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCaroSebőTarsi1996" class="citation cs2">Caro, Yair; <a href="/wiki/Andr%C3%A1s_Seb%C5%91" title="András Sebő">Sebő, András</a>; Tarsi, Michael (1996), "Recognizing greedy structures", <i>Journal of Algorithms</i>, <b>20</b> (1): <span class="nowrap">137–</span>156, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjagm.1996.0006">10.1006/jagm.1996.0006</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1368720">1368720</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Algorithms&rft.atitle=Recognizing+greedy+structures&rft.volume=20&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E137-%3C%2Fspan%3E156&rft.date=1996&rft_id=info%3Adoi%2F10.1006%2Fjagm.1996.0006&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1368720%23id-name%3DMR&rft.aulast=Caro&rft.aufirst=Yair&rft.au=Seb%C5%91%2C+Andr%C3%A1s&rft.au=Tarsi%2C+Michael&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChvátalSlater1993" class="citation cs2"><a href="/wiki/V%C3%A1clav_Chv%C3%A1tal" title="Václav Chvátal">Chvátal, Václav</a>; Slater, Peter J. (1993), "A note on well-covered graphs", <i>Quo vadis, graph theory?</i>, Annals of Discrete Mathematics, vol. 55, Amsterdam: North-Holland, pp. <span class="nowrap">179–</span>181, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1217991">1217991</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=A+note+on+well-covered+graphs&rft.btitle=Quo+vadis%2C+graph+theory%3F&rft.place=Amsterdam&rft.series=Annals+of+Discrete+Mathematics&rft.pages=%3Cspan+class%3D%22nowrap%22%3E179-%3C%2Fspan%3E181&rft.pub=North-Holland&rft.date=1993&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1217991%23id-name%3DMR&rft.aulast=Chv%C3%A1tal&rft.aufirst=V%C3%A1clav&rft.au=Slater%2C+Peter+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCookNagel2010" class="citation cs2">Cook, David II; Nagel, Uwe (2010), "Cohen-Macaulay graphs and face vectors of flag complexes", <i>SIAM Journal on Discrete Mathematics</i>, <b>26</b>: <span class="nowrap">89–</span>101, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1003.4447">1003.4447</a></span>, <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010arXiv1003.4447C">2010arXiv1003.4447C</a>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F100818170">10.1137/100818170</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Discrete+Mathematics&rft.atitle=Cohen-Macaulay+graphs+and+face+vectors+of+flag+complexes&rft.volume=26&rft.pages=%3Cspan+class%3D%22nowrap%22%3E89-%3C%2Fspan%3E101&rft.date=2010&rft_id=info%3Aarxiv%2F1003.4447&rft_id=info%3Adoi%2F10.1137%2F100818170&rft_id=info%3Abibcode%2F2010arXiv1003.4447C&rft.aulast=Cook&rft.aufirst=David+II&rft.au=Nagel%2C+Uwe&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDochtermannEngström2009" class="citation cs2">Dochtermann, Anton; Engström, Alexander (2009), "Algebraic properties of edge ideals via combinatorial topology", <i><a href="/wiki/Electronic_Journal_of_Combinatorics" title="Electronic Journal of Combinatorics">Electronic Journal of Combinatorics</a></i>, <b>16</b> (2): Research Paper 2, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F68">10.37236/68</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2515765">2515765</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Electronic+Journal+of+Combinatorics&rft.atitle=Algebraic+properties+of+edge+ideals+via+combinatorial+topology&rft.volume=16&rft.issue=2&rft.pages=Research+Paper+2&rft.date=2009&rft_id=info%3Adoi%2F10.37236%2F68&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2515765%23id-name%3DMR&rft.aulast=Dochtermann&rft.aufirst=Anton&rft.au=Engstr%C3%B6m%2C+Alexander&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFavaron1982" class="citation cs2"><a href="/wiki/Odile_Favaron" title="Odile Favaron">Favaron, O.</a> (1982), "Very well covered graphs", <i><a href="/wiki/Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a></i>, <b>42</b> (<span class="nowrap">2–</span>3): <span class="nowrap">177–</span>187, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2882%2990215-1">10.1016/0012-365X(82)90215-1</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0677051">0677051</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Mathematics&rft.atitle=Very+well+covered+graphs&rft.volume=42&rft.issue=%3Cspan+class%3D%22nowrap%22%3E2%E2%80%93%3C%2Fspan%3E3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E177-%3C%2Fspan%3E187&rft.date=1982&rft_id=info%3Adoi%2F10.1016%2F0012-365X%2882%2990215-1&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D677051%23id-name%3DMR&rft.aulast=Favaron&rft.aufirst=O.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinbowHartnell1983" class="citation cs2">Finbow, A. S.; Hartnell, B. L. (1983), "A game related to covering by stars", <i><a href="/wiki/Ars_Combinatoria_(journal)" title="Ars Combinatoria (journal)">Ars Combinatoria</a></i>, <b>16</b> (A): <span class="nowrap">189–</span>198, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0737090">0737090</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Ars+Combinatoria&rft.atitle=A+game+related+to+covering+by+stars&rft.volume=16&rft.issue=A&rft.pages=%3Cspan+class%3D%22nowrap%22%3E189-%3C%2Fspan%3E198&rft.date=1983&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D737090%23id-name%3DMR&rft.aulast=Finbow&rft.aufirst=A.+S.&rft.au=Hartnell%2C+B.+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinbowHartnellNowakowski1988" class="citation cs2">Finbow, A.; Hartnell, B.; Nowakowski, R. (1988), "Well-dominated graphs: a collection of well-covered ones", <i><a href="/wiki/Ars_Combinatoria_(journal)" title="Ars Combinatoria (journal)">Ars Combinatoria</a></i>, <b>25</b> (A): <span class="nowrap">5–</span>10, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0942485">0942485</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Ars+Combinatoria&rft.atitle=Well-dominated+graphs%3A+a+collection+of+well-covered+ones&rft.volume=25&rft.issue=A&rft.pages=%3Cspan+class%3D%22nowrap%22%3E5-%3C%2Fspan%3E10&rft.date=1988&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D942485%23id-name%3DMR&rft.aulast=Finbow&rft.aufirst=A.&rft.au=Hartnell%2C+B.&rft.au=Nowakowski%2C+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinbowHartnellNowakowski1993" class="citation cs2">Finbow, A.; Hartnell, B.; Nowakowski, R. J. (1993), "A characterization of well covered graphs of girth 5 or greater", <i><a href="/wiki/Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a></i>, Series B, <b>57</b> (1): <span class="nowrap">44–</span>68, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjctb.1993.1005">10.1006/jctb.1993.1005</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1198396">1198396</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Combinatorial+Theory&rft.atitle=A+characterization+of+well+covered+graphs+of+girth+5+or+greater&rft.volume=57&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E44-%3C%2Fspan%3E68&rft.date=1993&rft_id=info%3Adoi%2F10.1006%2Fjctb.1993.1005&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1198396%23id-name%3DMR&rft.aulast=Finbow&rft.aufirst=A.&rft.au=Hartnell%2C+B.&rft.au=Nowakowski%2C+R.+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinbowHartnellNowakowskiPlummer2003" class="citation cs2">Finbow, A.; Hartnell, B.; Nowakowski, R.; <a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (2003), "On well-covered triangulations. I", <i><a href="/wiki/Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a></i>, <b>132</b> (<span class="nowrap">1–</span>3): <span class="nowrap">97–</span>108, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0166-218X%2803%2900393-7">10.1016/S0166-218X(03)00393-7</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2024267">2024267</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Applied+Mathematics&rft.atitle=On+well-covered+triangulations.+I&rft.volume=132&rft.issue=%3Cspan+class%3D%22nowrap%22%3E1%E2%80%93%3C%2Fspan%3E3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E97-%3C%2Fspan%3E108&rft.date=2003&rft_id=info%3Adoi%2F10.1016%2FS0166-218X%2803%2900393-7&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2024267%23id-name%3DMR&rft.aulast=Finbow&rft.aufirst=A.&rft.au=Hartnell%2C+B.&rft.au=Nowakowski%2C+R.&rft.au=Plummer%2C+Michael+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinbowHartnellNowakowskiPlummer2009" class="citation cs2">Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; <a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (2009), "On well-covered triangulations. II", <i><a href="/wiki/Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a></i>, <b>157</b> (13): <span class="nowrap">2799–</span>2817, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2009.03.014">10.1016/j.dam.2009.03.014</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2537505">2537505</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Applied+Mathematics&rft.atitle=On+well-covered+triangulations.+II&rft.volume=157&rft.issue=13&rft.pages=%3Cspan+class%3D%22nowrap%22%3E2799-%3C%2Fspan%3E2817&rft.date=2009&rft_id=info%3Adoi%2F10.1016%2Fj.dam.2009.03.014&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2537505%23id-name%3DMR&rft.aulast=Finbow&rft.aufirst=Arthur+S.&rft.au=Hartnell%2C+Bert+L.&rft.au=Nowakowski%2C+Richard+J.&rft.au=Plummer%2C+Michael+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinbowHartnellNowakowskiPlummer2010" class="citation cs2">Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; <a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (2010), "On well-covered triangulations. III", <i><a href="/wiki/Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a></i>, <b>158</b> (8): <span class="nowrap">894–</span>912, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2009.08.002">10.1016/j.dam.2009.08.002</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2602814">2602814</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Applied+Mathematics&rft.atitle=On+well-covered+triangulations.+III&rft.volume=158&rft.issue=8&rft.pages=%3Cspan+class%3D%22nowrap%22%3E894-%3C%2Fspan%3E912&rft.date=2010&rft_id=info%3Adoi%2F10.1016%2Fj.dam.2009.08.002&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2602814%23id-name%3DMR&rft.aulast=Finbow&rft.aufirst=Arthur+S.&rft.au=Hartnell%2C+Bert+L.&rft.au=Nowakowski%2C+Richard+J.&rft.au=Plummer%2C+Michael+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinbowHartnellNowakowskiPlummer2016" class="citation cs2">Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; <a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (2016), "Well-covered triangulations: Part IV", <i><a href="/wiki/Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a></i>, <b>215</b>: <span class="nowrap">71–</span>94, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2016.06.030">10.1016/j.dam.2016.06.030</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3548980">3548980</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Applied+Mathematics&rft.atitle=Well-covered+triangulations%3A+Part+IV&rft.volume=215&rft.pages=%3Cspan+class%3D%22nowrap%22%3E71-%3C%2Fspan%3E94&rft.date=2016&rft_id=info%3Adoi%2F10.1016%2Fj.dam.2016.06.030&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D3548980%23id-name%3DMR&rft.aulast=Finbow&rft.aufirst=Arthur+S.&rft.au=Hartnell%2C+Bert+L.&rft.au=Nowakowski%2C+Richard+J.&rft.au=Plummer%2C+Michael+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFinkJacobsonKinchRoberts1985" class="citation cs2">Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985), "On graphs having domination number half their order", <i>Period. Math. Hungar.</i>, <b>16</b> (4): <span class="nowrap">287–</span>293, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01848079">10.1007/BF01848079</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0833264">0833264</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:121734811">121734811</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Period.+Math.+Hungar.&rft.atitle=On+graphs+having+domination+number+half+their+order&rft.volume=16&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E287-%3C%2Fspan%3E293&rft.date=1985&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0833264%23id-name%3DMR&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A121734811%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2FBF01848079&rft.aulast=Fink&rft.aufirst=J.+F.&rft.au=Jacobson%2C+M.+S.&rft.au=Kinch%2C+L.+F.&rft.au=Roberts%2C+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGreenberg1993" class="citation cs2">Greenberg, Peter (1993), "Piecewise <span class="texhtml">SL<sub>2</sub><b>Z</b></span> geometry", <i><a href="/wiki/Transactions_of_the_American_Mathematical_Society" title="Transactions of the American Mathematical Society">Transactions of the American Mathematical Society</a></i>, <b>335</b> (2): <span class="nowrap">705–</span>720, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2154401">10.2307/2154401</a>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2154401">2154401</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1140914">1140914</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Transactions+of+the+American+Mathematical+Society&rft.atitle=Piecewise+%3Cspan+class%3D%22texhtml+%22+%3ESL%3Csub%3E2%3C%2Fsub%3EZ%3C%2Fspan%3E+geometry&rft.volume=335&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E705-%3C%2Fspan%3E720&rft.date=1993&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1140914%23id-name%3DMR&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2154401%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2307%2F2154401&rft.aulast=Greenberg&rft.aufirst=Peter&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHolroydTalbot2005" class="citation cs2">Holroyd, Fred; Talbot, John (2005), "Graphs with the Erdős-Ko-Rado property", <i>Discrete Mathematics</i>, <b>293</b> (<span class="nowrap">1–</span>3): <span class="nowrap">165–</span>176, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0307073">math/0307073</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2004.08.028">10.1016/j.disc.2004.08.028</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2136060">2136060</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Mathematics&rft.atitle=Graphs+with+the+Erd%C5%91s-Ko-Rado+property&rft.volume=293&rft.issue=%3Cspan+class%3D%22nowrap%22%3E1%E2%80%93%3C%2Fspan%3E3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E165-%3C%2Fspan%3E176&rft.date=2005&rft_id=info%3Aarxiv%2Fmath%2F0307073&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2136060%23id-name%3DMR&rft_id=info%3Adoi%2F10.1016%2Fj.disc.2004.08.028&rft.aulast=Holroyd&rft.aufirst=Fred&rft.au=Talbot%2C+John&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLeskPlummerPulleyblank1984" class="citation cs2">Lesk, M.; Plummer, M. D.; Pulleyblank, W. R. (1984), "Equi-matchable graphs", in Bollobás, Béla (ed.), <i>Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős</i>, London: Academic Press, pp. <span class="nowrap">239–</span>254, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0777180">0777180</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Equi-matchable+graphs&rft.btitle=Graph+Theory+and+Combinatorics%3A+Proceedings+of+the+Cambridge+Combinatorial+Conference%2C+in+Honour+of+Paul+Erd%C5%91s&rft.place=London&rft.pages=%3Cspan+class%3D%22nowrap%22%3E239-%3C%2Fspan%3E254&rft.pub=Academic+Press&rft.date=1984&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D777180%23id-name%3DMR&rft.aulast=Lesk&rft.aufirst=M.&rft.au=Plummer%2C+M.+D.&rft.au=Pulleyblank%2C+W.+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPlummer1970" class="citation cs2"><a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (1970), "Some covering concepts in graphs", <i><a href="/wiki/Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a></i>, <b>8</b>: <span class="nowrap">91–</span>98, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0021-9800%2870%2980011-4">10.1016/S0021-9800(70)80011-4</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0289347">0289347</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Combinatorial+Theory&rft.atitle=Some+covering+concepts+in+graphs&rft.volume=8&rft.pages=%3Cspan+class%3D%22nowrap%22%3E91-%3C%2Fspan%3E98&rft.date=1970&rft_id=info%3Adoi%2F10.1016%2FS0021-9800%2870%2980011-4&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0289347%23id-name%3DMR&rft.aulast=Plummer&rft.aufirst=Michael+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPlummer1993" class="citation cs2"><a href="/wiki/Michael_D._Plummer" title="Michael D. Plummer">Plummer, Michael D.</a> (1993), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120527164352/http://handle.dtic.mil/100.2/ADA247861">"Well-covered graphs: a survey"</a>, <i>Quaestiones Mathematicae</i>, <b>16</b> (3): <span class="nowrap">253–</span>287, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F16073606.1993.9631737">10.1080/16073606.1993.9631737</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1254158">1254158</a>, archived from <a rel="nofollow" class="external text" href="http://handle.dtic.mil/100.2/ADA247861">the original</a> on May 27, 2012</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Quaestiones+Mathematicae&rft.atitle=Well-covered+graphs%3A+a+survey&rft.volume=16&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E253-%3C%2Fspan%3E287&rft.date=1993&rft_id=info%3Adoi%2F10.1080%2F16073606.1993.9631737&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1254158%23id-name%3DMR&rft.aulast=Plummer&rft.aufirst=Michael+D.&rft_id=http%3A%2F%2Fhandle.dtic.mil%2F100.2%2FADA247861&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRaghavanSpinrad2003" class="citation cs2">Raghavan, Vijay; Spinrad, Jeremy (2003), "Robust algorithms for restricted domains", <i>Journal of Algorithms</i>, <b>48</b> (1): <span class="nowrap">160–</span>172, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0196-6774%2803%2900048-8">10.1016/S0196-6774(03)00048-8</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2006100">2006100</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16327087">16327087</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Algorithms&rft.atitle=Robust+algorithms+for+restricted+domains&rft.volume=48&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E160-%3C%2Fspan%3E172&rft.date=2003&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2006100%23id-name%3DMR&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A16327087%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1016%2FS0196-6774%2803%2900048-8&rft.aulast=Raghavan&rft.aufirst=Vijay&rft.au=Spinrad%2C+Jeremy&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRavindra1977" class="citation cs2">Ravindra, G. (1977), "Well-covered graphs", <i>Journal of Combinatorics, Information and System Sciences</i>, <b>2</b> (1): <span class="nowrap">20–</span>21, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0469831">0469831</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Combinatorics%2C+Information+and+System+Sciences&rft.atitle=Well-covered+graphs&rft.volume=2&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E20-%3C%2Fspan%3E21&rft.date=1977&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0469831%23id-name%3DMR&rft.aulast=Ravindra&rft.aufirst=G.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSankaranarayana1994" class="citation cs2">Sankaranarayana, Ramesh S. (1994), <a rel="nofollow" class="external text" href="https://era.library.ualberta.ca/items/56555f77-5eb0-4539-ab3f-dd845ede193b"><i>Well-covered graphs: some new sub-classes and complexity results</i></a> (Doctoral dissertation), University of Alberta</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Well-covered+graphs%3A+some+new+sub-classes+and+complexity+results&rft.pub=University+of+Alberta&rft.date=1994&rft.aulast=Sankaranarayana&rft.aufirst=Ramesh+S.&rft_id=https%3A%2F%2Fera.library.ualberta.ca%2Fitems%2F56555f77-5eb0-4539-ab3f-dd845ede193b&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSankaranarayanaStewart1992" class="citation cs2">Sankaranarayana, Ramesh S.; <a href="/wiki/Lorna_Stewart" title="Lorna Stewart">Stewart, Lorna K.</a> (1992), "Complexity results for well-covered graphs", <i>Networks</i>, <b>22</b> (3): <span class="nowrap">247–</span>262, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.9278">10.1.1.47.9278</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fnet.3230220304">10.1002/net.3230220304</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1161178">1161178</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Networks&rft.atitle=Complexity+results+for+well-covered+graphs&rft.volume=22&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E247-%3C%2Fspan%3E262&rft.date=1992&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.47.9278%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1161178%23id-name%3DMR&rft_id=info%3Adoi%2F10.1002%2Fnet.3230220304&rft.aulast=Sankaranarayana&rft.aufirst=Ramesh+S.&rft.au=Stewart%2C+Lorna+K.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStaples1975" class="citation cs2">Staples, J. (1975), <i>On some subclasses of well-covered graphs</i>, Ph.D. thesis, Vanderbilt University, Department of Mathematics</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=On+some+subclasses+of+well-covered+graphs&rft.series=Ph.D.+thesis&rft.pub=Vanderbilt+University%2C+Department+of+Mathematics&rft.date=1975&rft.aulast=Staples&rft.aufirst=J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>. As cited by <a href="#CITEREFPlummer1993">Plummer (1993)</a>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSumner1979" class="citation cs2"><a href="/wiki/David_Sumner" title="David Sumner">Sumner, David P.</a> (1979), "Randomly matchable graphs", <i><a href="/wiki/Journal_of_Graph_Theory" title="Journal of Graph Theory">Journal of Graph Theory</a></i>, <b>3</b> (2): <span class="nowrap">183–</span>186, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fjgt.3190030209">10.1002/jgt.3190030209</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0530304">0530304</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Graph+Theory&rft.atitle=Randomly+matchable+graphs&rft.volume=3&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E183-%3C%2Fspan%3E186&rft.date=1979&rft_id=info%3Adoi%2F10.1002%2Fjgt.3190030209&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D530304%23id-name%3DMR&rft.aulast=Sumner&rft.aufirst=David+P.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTankusTarsi1996" class="citation cs2">Tankus, David; Tarsi, Michael (1996), "Well-covered claw-free graphs", <i><a href="/wiki/Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a></i>, Series B, <b>66</b> (2): <span class="nowrap">293–</span>302, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjctb.1996.0022">10.1006/jctb.1996.0022</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1376052">1376052</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Combinatorial+Theory&rft.atitle=Well-covered+claw-free+graphs&rft.volume=66&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E293-%3C%2Fspan%3E302&rft.date=1996&rft_id=info%3Adoi%2F10.1006%2Fjctb.1996.0022&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1376052%23id-name%3DMR&rft.aulast=Tankus&rft.aufirst=David&rft.au=Tarsi%2C+Michael&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTankusTarsi1997" class="citation cs2">Tankus, David; Tarsi, Michael (1997), "The structure of well-covered graphs and the complexity of their recognition problems", <i><a href="/wiki/Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a></i>, Series B, <b>69</b> (2): <span class="nowrap">230–</span>233, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjctb.1996.1742">10.1006/jctb.1996.1742</a></span>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1438624">1438624</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Combinatorial+Theory&rft.atitle=The+structure+of+well-covered+graphs+and+the+complexity+of+their+recognition+problems&rft.volume=69&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E230-%3C%2Fspan%3E233&rft.date=1997&rft_id=info%3Adoi%2F10.1006%2Fjctb.1996.1742&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1438624%23id-name%3DMR&rft.aulast=Tankus&rft.aufirst=David&rft.au=Tarsi%2C+Michael&rfr_id=info%3Asid%2Fen.wikipedia.org%3AWell-covered+graph" class="Z3988"></span>.</li></ul> </div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Well-covered_graph&oldid=1235224887">https://en.wikipedia.org/w/index.php?title=Well-covered_graph&oldid=1235224887</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Category</a>: <ul><li><a href="/wiki/Category:Graph_families" title="Category:Graph families">Graph families</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Good_articles" title="Category:Good articles">Good articles</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 18 July 2024, at 07:42<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Well-covered_graph&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" lang="en" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Well-covered graph</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>1 language</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-8568cbfbb4-gdv6q","wgBackendResponseTime":113,"wgPageParseReport":{"limitreport":{"cputime":"0.431","walltime":"0.594","ppvisitednodes":{"value":5139,"limit":1000000},"postexpandincludesize":{"value":88922,"limit":2097152},"templateargumentsize":{"value":2776,"limit":2097152},"expansiondepth":{"value":11,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":84339,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 480.592 1 -total"," 41.14% 197.698 30 Template:Citation"," 14.21% 68.290 1 Template:Short_description"," 13.13% 63.081 1 Template:Reflist"," 10.87% 52.238 12 Template:Sfnp"," 10.27% 49.353 24 Template:Main_other"," 7.99% 38.411 2 Template:Pagetype"," 6.91% 33.200 41 Template:Harvtxt"," 5.82% 27.956 1 Template:Good_article"," 5.47% 26.268 1 Template:Top_icon"]},"scribunto":{"limitreport-timeusage":{"value":"0.259","limit":"10.000"},"limitreport-memusage":{"value":7044780,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFBerge1981\"] = 1,\n [\"CITEREFCampbell1987\"] = 1,\n [\"CITEREFCampbellEllinghamRoyle1993\"] = 1,\n [\"CITEREFCampbellPlummer1988\"] = 1,\n [\"CITEREFCaroSebőTarsi1996\"] = 1,\n [\"CITEREFChvátalSlater1993\"] = 1,\n [\"CITEREFCookNagel2010\"] = 1,\n [\"CITEREFDochtermannEngström2009\"] = 1,\n [\"CITEREFFavaron1982\"] = 1,\n [\"CITEREFFinbowHartnell1983\"] = 1,\n [\"CITEREFFinbowHartnellNowakowski1988\"] = 1,\n [\"CITEREFFinbowHartnellNowakowski1993\"] = 1,\n [\"CITEREFFinbowHartnellNowakowskiPlummer2003\"] = 1,\n [\"CITEREFFinbowHartnellNowakowskiPlummer2009\"] = 1,\n [\"CITEREFFinbowHartnellNowakowskiPlummer2010\"] = 1,\n [\"CITEREFFinbowHartnellNowakowskiPlummer2016\"] = 1,\n [\"CITEREFFinkJacobsonKinchRoberts1985\"] = 1,\n [\"CITEREFGreenberg1993\"] = 1,\n [\"CITEREFHolroydTalbot2005\"] = 1,\n [\"CITEREFLeskPlummerPulleyblank1984\"] = 1,\n [\"CITEREFPlummer1970\"] = 1,\n [\"CITEREFPlummer1993\"] = 1,\n [\"CITEREFRaghavanSpinrad2003\"] = 1,\n [\"CITEREFRavindra1977\"] = 1,\n [\"CITEREFSankaranarayana1994\"] = 1,\n [\"CITEREFSankaranarayanaStewart1992\"] = 1,\n [\"CITEREFStaples1975\"] = 1,\n [\"CITEREFSumner1979\"] = 1,\n [\"CITEREFTankusTarsi1996\"] = 1,\n [\"CITEREFTankusTarsi1997\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Chess diagram\"] = 1,\n [\"Citation\"] = 30,\n [\"Good article\"] = 1,\n [\"Harvs\"] = 1,\n [\"Harvtxt\"] = 41,\n [\"Math\"] = 8,\n [\"Mvar\"] = 66,\n [\"Refbegin\"] = 1,\n [\"Refend\"] = 1,\n [\"Reflist\"] = 1,\n [\"Sfnp\"] = 12,\n [\"Short description\"] = 1,\n}\narticle_whitelist = table#1 {\n}\nciteref_patterns = table#1 {\n}\n"},"cachereport":{"origin":"mw-api-ext.eqiad.main-58bb4f8ccf-vf8ts","timestamp":"20250214045956","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Well-covered graph","url":"https:\/\/en.wikipedia.org\/wiki\/Well-covered_graph","sameAs":"http:\/\/www.wikidata.org\/entity\/Q7981049","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q7981049","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2011-08-10T01:09:50Z","dateModified":"2024-07-18T07:42:54Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/9\/94\/Well-covered_graph.svg","headline":"graph with equal-size maximal independent sets"}</script> </body> </html>