View source for Well-covered graph

{{Short description|Graph with equal-size maximal independent sets}}
{{good article}}
[[File:Well-covered graph.svg|thumb|A well-covered graph, the [[intersection graph]] of the nine diagonals of a [[hexagon]]. 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.]]
In [[graph theory]], a '''well-covered graph''' is an [[undirected graph]] in which the minimal vertex covers all have the same size. Here, a [[vertex cover]] is a set of vertices that touches all edges, and it is [[minimal element|minimal]] if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs are the graphs in which all [[maximal independent set]]s have equal size. Well-covered graphs were defined and first studied by [[Michael D. Plummer]] in 1970.

The well-covered graphs include all [[complete graph]]s, balanced [[complete bipartite graph]]s, and the [[rook's graph]]s whose vertices represent squares of a chessboard and edges represent moves of a chess rook. Known characterizations of the well-covered [[cubic graph]]s, well-covered [[claw-free graph]]s, and well-covered graphs of high [[girth (graph theory)|girth]] allow these graphs to be recognized in [[polynomial time]], but testing whether other kinds of graph are well-covered is a [[coNP-complete]] problem.

==Definitions==
A vertex cover in an [[undirected graph]] 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.<ref>{{harvtxt|Plummer|1970}}. 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.</ref>

An [[Independent set (graph theory)|independent set]] in a graph is a set of vertices no two of which are adjacent to each other. If {{mvar|C}} is a vertex cover in a graph {{mvar|G}}, the [[Complement (set theory)|complement]] of {{mvar|C}} must be an independent set, and vice versa. {{mvar|C}} is a minimal vertex cover if and only if its complement {{mvar|I}} is a maximal independent set, and {{mvar|C}} 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.{{sfnp|Plummer|1993}}

In the original paper defining well-covered graphs, these definitions were restricted to [[Connectivity (graph theory)|connected graphs]],{{sfnp|Plummer|1970}} 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.{{sfnp|Favaron|1982}} For both connected well-covered graphs and well-covered graphs without isolated vertices, there can be no ''essential vertices'', vertices which belong to every minimum vertex cover. Additionally, every well-covered graph is a [[critical graph]] for vertex covering in the sense that, for every vertex {{mvar|v}}, deleting {{mvar|v}} from the graph produces a graph with a smaller minimum vertex cover.{{sfnp|Plummer|1970}}

The [[clique complex|independence complex]] of a graph {{mvar|G}} is the [[simplicial complex]] having a simplex for each independent set in {{mvar|G}}. 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.<ref>For examples of papers using this terminology, see {{harvtxt|Dochtermann|Engström|2009}} and {{harvtxt|Cook|Nagel|2010}}.</ref>

==Examples==
{{Chess diagram
| tright
|
|__|__|__|rl|__|__|__|__
|__|__|__|__|__|__|rl|__
|__|__|rl|__|__|__|__|__
|rl|__|__|__|__|__|__|__
|__|rl|__|__|__|__|__|__
|__|__|__|__|__|__|__|rl
|__|__|__|__|rl|__|__|__
|__|__|__|__|__|rl|__|__
|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.
}}
A [[cycle graph]] 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.{{sfnp|Sankaranarayana|1994|loc=Section 2.4, "Examples", p. 7}} Every [[complete graph]] is well-covered: every maximal independent set consists of a single vertex. Similarly, every [[cluster graph]] (a disjoint union of complete graphs) is well-covered.{{sfnp|Holroyd|Talbot|2005}} A [[complete bipartite graph]] 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 [[complement graph]] of a [[triangle-free graph]] with no [[isolated vertex|isolated vertices]] is well-covered: it has no independent sets larger than two, and every single vertex can be extended to a two-vertex independent set.{{sfnp|Sankaranarayana|1994|loc=Section 2.4, "Examples", p. 7}} 

A [[rook's graph]] is well covered: if one places any set of [[Rook (chess)|rooks]] on a [[chessboard]] 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.<ref>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 {{harvtxt|Sumner|1979}} and {{harvtxt|Lesk|Plummer|Pulleyblank|1984}}.</ref> The graph whose vertices are the diagonals of a [[simple polygon]] 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.{{sfnp|Greenberg|1993}}

If {{mvar|G}} is any {{mvar|n}}-vertex graph, then the [[Rooted product of graphs|rooted product]] of {{mvar|G}} with a one-edge graph (that is, the graph {{mvar|H}} formed by adding {{mvar|n}} new vertices to {{mvar|G}}, each of degree one and each adjacent to a distinct vertex in {{mvar|G}}) is well-covered. For, a maximal independent set in {{mvar|H}} must consist of an arbitrary independent set in {{mvar|G}} together with the degree-one neighbors of the complementary set, and must therefore have size {{mvar|n}}.<ref>This class of examples was studied by {{harvtxt|Fink|Jacobson|Kinch|Roberts|1985}}; they are also (together with the four-edge cycle, which is also well-covered) exactly the graphs whose domination number is {{math|''n''/2}}. Its well-covering property is also stated in different terminology (having a pure independence complex) as Theorem 4.4 of {{harvtxt|Dochtermann|Engström|2009}}.</ref> More generally, given any graph {{mvar|G}} together with a [[clique cover]] (a partition {{mvar|p}} of the vertices of {{mvar|G}} into cliques), the graph {{mvar|G<sup>p</sup>}} formed by adding another vertex to each clique is well-covered; the rooted product is the special case of this construction when {{mvar|p}} consists of {{mvar|n}} one-vertex cliques.<ref name=cn10>For the clique cover construction, see {{harvtxt|Cook|Nagel|2010}}, 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.</ref> Thus, every graph is an [[induced subgraph]] of a well-covered graph.

==Bipartiteness, very well covered graphs, and girth==
{{harvtxt|Favaron|1982}} defines a '''very well covered graph''' 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 {{mvar|G}} and a one-edge graph. It also includes, for instance, the bipartite well-covered graphs studied by {{harvtxt|Ravindra|1977}} and {{harvtxt|Berge|1981}}: 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 {{mvar|n}} vertices, without isolated vertices, the size of a maximum independent set is at most {{math|''n''/2}}, so very well covered graphs are the well covered graphs in which the maximum independent set size is as large as possible.{{sfnp|Berge|1981}}

A bipartite graph {{mvar|G}} is well-covered if and only if it has a [[perfect matching]] {{mvar|M}} with the property that, for every edge {{mvar|uv}} in {{mvar|M}}, the [[induced subgraph]] of the neighbors of {{mvar|u}} and {{mvar|v}} forms a [[complete bipartite graph]].<ref name="r77p93">{{harvtxt|Ravindra|1977}}; {{harvtxt|Plummer|1993}}.</ref> The characterization in terms of matchings can be extended from bipartite graphs to very well covered graphs: a graph {{mvar|G}} is very well covered if and only if it has a perfect matching {{mvar|M}} with the following two properties:
#No edge of {{mvar|M}} belongs to a triangle in {{mvar|G}}, and
#If an edge of {{mvar|M}} is the central edge of a three-edge path in {{mvar|G}}, then the two endpoints of the path must be adjacent.
Moreover, if {{mvar|G}} is very well covered, then every perfect matching in {{mvar|G}} satisfies these properties.<ref name="sfp">{{harvtxt|Staples|1975}}; {{harvtxt|Favaron|1982}}; {{harvtxt|Plummer|1993}}.</ref>

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 {{mvar|G}} 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.<ref name="r77p93"/> 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 [[girth (graph theory)|girth]] eight or more (so that, for every vertex {{mvar|v}}, the subgraph of vertices within distance three of {{mvar|v}} is acyclic) then it is well-covered if and only if every vertex of [[Degree (graph theory)|degree]] greater than one has exactly one neighbor of degree one.<ref>{{harvtxt|Finbow|Hartnell|1983}}; {{harvtxt|Plummer|1993}}, Theorem 4.1.</ref> A closely related but more complex characterization applies to well-covered graphs of girth five or more.<ref>{{harvtxt|Finbow|Hartnell|1983}}; {{harvtxt|Plummer|1993}}, Theorem 4.2.</ref>

==Regularity and planarity==
[[File:3r3c well-covered.svg|thumb|400px|The seven cubic 3-connected well-covered graphs]]
[[File:3r1c well-covered.svg|thumb|240px|A cubic 1-connected well-covered graph, formed by replacing each node of a six-node path by one of three fragments]]
[[File:Snub disphenoid.png|thumb|The [[snub disphenoid]], one of four well-covered 4-connected 3-dimensional simplicial polyhedra.]]
The [[cubic graph|cubic]] ([[regular graph|3-regular]]) well-covered graphs have been classified: they consist of seven [[k-vertex-connected graph|3-connected]] examples, together with three infinite families of cubic graphs with lesser connectivity.<ref name="ccpp"/>

The seven 3-connected cubic well-covered graphs are the [[complete graph]] {{math|''K''<sub>4</sub>}}, the graphs of the [[triangular prism]] and the [[pentagonal prism]], the [[Dürer graph]], the [[utility graph]] {{math|''K''<sub>3,3</sub>}}, an eight-vertex graph obtained from the utility graph by a [[YΔ- and ΔY-transformation|Y-Δ transform]], and the 14-vertex [[generalized Petersen graph]] {{math|''G''(7,2)}}.<ref>{{harvtxt|Campbell|1987}}; {{harvtxt|Finbow|Hartnell|Nowakowski|1988}}; {{harvtxt|Campbell|Ellingham|Royle|1993}}; {{harvtxt|Plummer|1993}}.</ref> Of these graphs, the first four are [[planar graph]]s. They are the only four cubic [[polyhedral graph]]s (graphs of [[Simple polytope|simple]]  [[convex polyhedron|convex polyhedra]]) that are well-covered.{{sfnp|Campbell|Plummer|1988}} Four of the graphs (the two prisms, the Dürer graph, and {{math|''G''(7,2)}}) are generalized Petersen graphs.

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 {{harvtxt|Plummer|1993}} labels {{mvar|A}}, {{mvar|B}}, and {{mvar|C}}. Fragments {{mvar|A}} or {{mvar|B}} may be used to replace the nodes of a cycle or the interior nodes of a path, while fragment {{mvar|C}} is used to replace the two end nodes of a path. Fragment {{mvar|A}} contains a [[bridge (graph theory)|bridge]], so the result of performing this replacement process on a path and using fragment {{mvar|A}} 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.<ref name="ccpp">{{harvtxt|Campbell|1987}}; {{harvtxt|Campbell|Plummer|1988}}; {{harvtxt|Plummer|1993}}.</ref>

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 {{mvar|A}} and {{mvar|B}}, with at least two of the fragments being of type {{mvar|A}}; a graph of this type is planar if and only if it does not contain any fragments of type {{mvar|B}}. The other family is formed by replacing the nodes of a path by fragments of type {{mvar|B}} and {{mvar|C}}; all such graphs are planar.<ref name="ccpp"/>

Complementing the characterization of well-covered simple polyhedra in three dimensions, researchers have also considered the well-covered [[simplicial polytope|simplicial polyhedra]], or equivalently the well-covered maximal planar graphs. Every maximal planar graph with five or more vertices has vertex connectivity 3, 4, or 5.<ref>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.</ref> 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 [[regular octahedron]], the [[pentagonal dipyramid]], the [[snub disphenoid]], and an irregular polyhedron (a nonconvex [[deltahedron]]) with 12 vertices, 30 edges, and 20 triangular faces. However, there are infinitely many 3-connected well-covered maximal planar graphs.<ref>{{harvs|last1=Finbow|last2=Hartnell|last3=Nowakowski|last4=Plummer|year=2003|year2=2009|year3=2010|txt}}.</ref> For instance, if a {{math|3''t''}}-vertex maximal planar graph has {{mvar|t}} 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 {{mvar|t}} triangles into three new triangles meeting at a central vertex, produces a well-covered maximal planar graph.<ref>The graphs constructed in this way are called the <math>K_4</math>-family by {{harvtxt|Finbow|Hartnell|Nowakowski|Plummer|2016}}; additional examples can be constructed by an operation they call an O-join for combining smaller graphs.</ref>

==Complexity==
Testing whether a graph contains two maximal independent sets of different sizes is [[NP-complete]]; that is, complementarily, testing whether a graph is well-covered is coNP-complete.<ref>{{harvtxt|Sankaranarayana|Stewart|1992}}; {{harvtxt|Chvátal|Slater|1993}}; {{harvtxt|Caro|Sebő|Tarsi|1996}}.</ref> 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.<ref>{{harvtxt|Raghavan|Spinrad|2003}}.</ref>

In contrast, it is possible to test whether a given graph {{mvar|G}} is very well covered in [[polynomial time]]. To do so, find the subgraph {{mvar|H}} of {{mvar|G}} 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 {{mvar|H}} has a perfect matching.<ref name="sfp"/> Some problems that are NP-complete for arbitrary graphs, such as the problem of finding a [[Hamiltonian cycle]], may also be solved in polynomial time for very well covered graphs.<ref>{{harvtxt|Sankaranarayana|Stewart|1992}}.</ref>

A graph is said to be '''equimatchable''' if every [[maximal matching]] is maximum; that is, it is equimatchable if its [[line graph]] is well-covered.{{sfnp|Lesk|Plummer|Pulleyblank|1984}} More strongly it is called '''randomly matchable''' if every maximal matching is a [[perfect matching]]. The only connected randomly matchable graphs are the complete graphs and the balanced complete bipartite graphs.{{sfnp|Sumner|1979}} It is possible to test whether a line graph, or more generally a [[claw-free graph]], is well-covered in polynomial time.<ref>{{harvtxt|Lesk|Plummer|Pulleyblank|1984}}; {{harvtxt|Tankus|Tarsi|1996}}; {{harvtxt|Tankus|Tarsi|1997}}.</ref>

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.<ref>{{harvtxt|Campbell|Ellingham|Royle|1993}}; {{harvtxt|Plummer|1993}}.</ref>

==Notes==
{{reflist|colwidth=30em}}

==References==
{{refbegin|colwidth=30em}}
*{{citation
 | last = Berge | first = Claude | author-link = Claude Berge
 | contribution = Some common properties for regularizable graphs, edge-critical graphs and {{mvar|B}}-graphs
 | doi = 10.1007/3-540-10704-5_10
 | location = Berlin
 | mr = 622929
 | pages = 108–123
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Graph theory and algorithms (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980)
 | volume = 108
 | year = 1981| isbn = 978-3-540-10704-0 | doi-access = free
 }}.
*{{citation|first=S. R.|last=Campbell|title=Some results on planar well-covered graphs|series=Ph.D. thesis|year=1987|publisher=Vanderbilt University, Department of Mathematics}}. As cited by {{harvtxt|Plummer|1993}}.
*{{citation
 | last1 = Campbell | first1 = S. R.
 | last2 = Ellingham | first2 = M. N. | author2-link = Mark Ellingham
 | last3 = Royle | first3 = Gordon F. | author3-link = Gordon Royle
 | journal = Journal of Combinatorial Mathematics and Combinatorial Computing
 | mr = 1220613
 | pages = 193–212
 | title = A characterisation of well-covered cubic graphs
 | volume = 13
 | year = 1993}}.
*{{citation
 | last1 = Campbell | first1 = Stephen R.
 | last2 = Plummer | first2 = Michael D. | author2-link = Michael D. Plummer
 | issue = A
 | journal = [[Ars Combinatoria (journal)|Ars Combinatoria]]
 | mr = 942505
 | pages = 215–242
 | title = On well-covered 3-polytopes
 | volume = 25
 | year = 1988}}.
*{{citation
 | last1 = Caro | first1 = Yair
 | last2 = Sebő | first2 = András | author2-link = András Sebő
 | last3 = Tarsi | first3 = Michael
 | doi = 10.1006/jagm.1996.0006
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 1368720
 | pages = 137–156
 | title = Recognizing greedy structures
 | volume = 20
 | year = 1996}}.
*{{citation
 | last1 = Chvátal | first1 = Václav | author1-link = Václav Chvátal
 | last2 = Slater | first2 = Peter J.
 | contribution = A note on well-covered graphs
 | location = Amsterdam
 | mr = 1217991
 | pages = 179–181
 | publisher = North-Holland
 | series = Annals of Discrete Mathematics
 | title = Quo vadis, graph theory?
 | volume = 55
 | year = 1993}}.
*{{citation|last1=Cook|first1=David II|last2=Nagel|first2=Uwe|title=Cohen-Macaulay graphs and face vectors of flag complexes|journal=SIAM Journal on Discrete Mathematics|volume=26|pages=89–101|year=2010|arxiv=1003.4447|bibcode=2010arXiv1003.4447C|doi=10.1137/100818170}}.
*{{citation
 | last1 = Dochtermann | first1 = Anton
 | last2 = Engström | first2 = Alexander
 | doi = 10.37236/68 
 | issue = 2
 | journal = [[Electronic Journal of Combinatorics]]
 | mr = 2515765
 | page = Research Paper 2
 | title = Algebraic properties of edge ideals via combinatorial topology
 | volume = 16
 | year = 2009| doi-access = free
 }}.
*{{citation
 | last = Favaron | first = O. | author-link = Odile Favaron
 | doi = 10.1016/0012-365X(82)90215-1
 | issue = 2–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 677051
 | pages = 177–187
 | title = Very well covered graphs
 | volume = 42
 | year = 1982| doi-access = free
 }}.
*{{citation
 | last1 = Finbow | first1 = A. S.
 | last2 = Hartnell | first2 = B. L.
 | issue = A
 | journal = [[Ars Combinatoria (journal)|Ars Combinatoria]]
 | mr = 737090
 | pages = 189–198
 | title = A game related to covering by stars
 | volume = 16
 | year = 1983}}.
*{{citation
 | last1 = Finbow | first1 = A.
 | last2 = Hartnell | first2 = B.
 | last3 = Nowakowski | first3 = R.
 | issue = A
 | journal = [[Ars Combinatoria (journal)|Ars Combinatoria]]
 | mr = 942485
 | pages = 5–10
 | title = Well-dominated graphs: a collection of well-covered ones
 | volume = 25
 | year = 1988}}.
*{{citation
 | last1 = Finbow | first1 = A.
 | last2 = Hartnell | first2 = B.
 | last3 = Nowakowski | first3 = R. J.
 | doi = 10.1006/jctb.1993.1005
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]|series=Series B
 | mr = 1198396
 | pages = 44–68
 | title = A characterization of well covered graphs of girth 5 or greater
 | volume = 57
 | year = 1993| doi-access = free
 }}.
*{{citation
 | last1 = Finbow | first1 = A.
 | last2 = Hartnell | first2 = B.
 | last3 = Nowakowski | first3 = R.
 | last4 = Plummer | first4 = Michael D. | author4-link = Michael D. Plummer
 | doi = 10.1016/S0166-218X(03)00393-7
 | issue = 1–3
 | journal = [[Discrete Applied Mathematics]]
 | mr = 2024267
 | pages = 97–108
 | title = On well-covered triangulations. I
 | volume = 132
 | year = 2003| doi-access = free
 }}.
*{{citation
 | last1 = Finbow | first1 = Arthur S.
 | last2 = Hartnell | first2 = Bert L.
 | last3 = Nowakowski | first3 = Richard J.
 | last4 = Plummer | first4 = Michael D. | author4-link = Michael D. Plummer
 | doi = 10.1016/j.dam.2009.03.014
 | issue = 13
 | journal = [[Discrete Applied Mathematics]]
 | mr = 2537505
 | pages = 2799–2817
 | title = On well-covered triangulations. II
 | volume = 157
 | year = 2009| doi-access = free
 }}.
*{{citation
 | last1 = Finbow | first1 = Arthur S.
 | last2 = Hartnell | first2 = Bert L.
 | last3 = Nowakowski | first3 = Richard J.
 | last4 = Plummer | first4 = Michael D. | author4-link = Michael D. Plummer
 | doi = 10.1016/j.dam.2009.08.002
 | issue = 8
 | journal = [[Discrete Applied Mathematics]]
 | mr = 2602814
 | pages = 894–912
 | title = On well-covered triangulations. III
 | volume = 158
 | year = 2010| doi-access = free
 }}.
*{{citation
 | last1 = Finbow | first1 = Arthur S.
 | last2 = Hartnell | first2 = Bert L.
 | last3 = Nowakowski | first3 = Richard J.
 | last4 = Plummer | first4 = Michael D. | author4-link = Michael D. Plummer
 | doi = 10.1016/j.dam.2016.06.030
 | journal = [[Discrete Applied Mathematics]]
 | mr = 3548980
 | pages = 71–94
 | title = Well-covered triangulations: Part IV
 | volume = 215
 | year = 2016| doi-access = free
 }}.
*{{citation
 | last1 = Fink | first1 = J. F.
 | last2 = Jacobson | first2 = M. S.
 | last3 = Kinch | first3 = L. F.
 | last4 = Roberts | first4 = J.
 | title = On graphs having domination number half their order
 | year = 1985
 | journal = Period. Math. Hungar.
 | volume = 16
 | pages = 287–293
 | mr = 0833264
 | doi = 10.1007/BF01848079
 | issue = 4| s2cid = 121734811
 }}.
*{{citation
 | last = Greenberg | first = Peter
 | doi = 10.2307/2154401
 | issue = 2
 | journal = [[Transactions of the American Mathematical Society]]
 | mr = 1140914
 | pages = 705–720
 | title = Piecewise {{math|SL<sub>2</sub>'''Z'''}} geometry
 | volume = 335
 | year = 1993| jstor = 2154401
 }}.
*{{citation
 | last1 = Holroyd | first1 = Fred
 | last2 = Talbot | first2 = John
 | arxiv = math/0307073
 | doi = 10.1016/j.disc.2004.08.028
 | issue = 1–3
 | journal = Discrete Mathematics
 | mr = 2136060
 | pages = 165–176
 | title = Graphs with the Erdős-Ko-Rado property
 | volume = 293
 | year = 2005}}.
*{{citation
 | last1 = Lesk | first1 = M.
 | last2 = Plummer | first2 = M. D.
 | last3 = Pulleyblank | first3 = W. R.
 | editor-last = Bollobás | editor-first = Béla
 | contribution = Equi-matchable graphs
 | location = London
 | mr = 777180
 | pages = 239–254
 | publisher = Academic Press
 | title = Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős
 | year = 1984}}.
*{{citation
 | last = Plummer | first = Michael D. | author-link = Michael D. Plummer
 | doi = 10.1016/S0021-9800(70)80011-4
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 0289347
 | pages = 91–98
 | title = Some covering concepts in graphs
 | volume = 8
 | year = 1970| doi-access = free
 }}.
*{{citation
 | last = Plummer | first = Michael D. | author-link = Michael D. Plummer
 | issue = 3
 | journal = Quaestiones Mathematicae
 | mr = 1254158
 | pages = 253–287
 | title = Well-covered graphs: a survey
 | url = http://handle.dtic.mil/100.2/ADA247861
 | archive-url = https://web.archive.org/web/20120527164352/http://handle.dtic.mil/100.2/ADA247861
 
 | archive-date = May 27, 2012
 | volume = 16
 | year = 1993
 | doi=10.1080/16073606.1993.9631737}}.
*{{citation
 | last1 = Raghavan | first1 = Vijay
 | last2 = Spinrad | first2 = Jeremy
 | doi = 10.1016/S0196-6774(03)00048-8
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 2006100
 | pages = 160–172
 | title = Robust algorithms for restricted domains
 | volume = 48
 | year = 2003| s2cid = 16327087
 }}.
*{{citation
 | last = Ravindra | first = G.
 | issue = 1
 | journal = Journal of Combinatorics, Information and System Sciences
 | mr = 0469831
 | pages = 20–21
 | title = Well-covered graphs
 | volume = 2
 | year = 1977}}.
*{{citation
 | last = Sankaranarayana | first = Ramesh S.
 | title = Well-covered graphs: some new sub-classes and complexity results
 | type = Doctoral dissertation
 | publisher = University of Alberta
 | year = 1994
 | url = https://era.library.ualberta.ca/items/56555f77-5eb0-4539-ab3f-dd845ede193b}}
*{{citation
 | last1 = Sankaranarayana | first1 = Ramesh S.
 | last2 = Stewart | first2 = Lorna K. | author2-link = Lorna Stewart
 | doi = 10.1002/net.3230220304
 | issue = 3
 | journal = Networks
 | mr = 1161178
 | pages = 247–262
 | title = Complexity results for well-covered graphs
 | volume = 22
 | year = 1992| citeseerx = 10.1.1.47.9278
 }}.
*{{citation|first=J.|last=Staples|title=On some subclasses of well-covered graphs|publisher=Vanderbilt University, Department of Mathematics|series=Ph.D. thesis|year=1975}}. As cited by {{harvtxt|Plummer|1993}}.
*{{citation
 | last = Sumner | first = David P. | author-link = David Sumner
 | doi = 10.1002/jgt.3190030209
 | issue = 2
 | journal = [[Journal of Graph Theory]]
 | mr = 530304
 | pages = 183–186
 | title = Randomly matchable graphs
 | volume = 3
 | year = 1979}}.
*{{citation
 | last1 = Tankus | first1 = David
 | last2 = Tarsi | first2 = Michael
 | doi = 10.1006/jctb.1996.0022
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 1376052
 | pages = 293–302
 | title = Well-covered claw-free graphs
 | volume = 66
 | year = 1996| doi-access = free
 }}.
*{{citation
 | last1 = Tankus | first1 = David
 | last2 = Tarsi | first2 = Michael
 | doi = 10.1006/jctb.1996.1742
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 1438624
 | pages = 230–233
 | title = The structure of well-covered graphs and the complexity of their recognition problems
 | volume = 69
 | year = 1997| doi-access = free
 }}.
{{refend}}

[[Category:Graph families]]