Jump to content

Well-covered graph

From Simple English Wikipedia, the free encyclopedia
A well-covered graph. It is the intersection graph of the nine diagonals of a hexagon. The three red vertices (points) make one of its 14 equal-sized maximal independent sets. The six blue vertices make the minimal vertex cover.

In graph theory, a well-covered graph is a kind of undirected graph. In these graphs, every minimal vertex cover has the same size. A vertex cover is a set of vertices (points) that touches all the edges (lines) in the graph. A cover is minimal if taking away any vertex means some edge is not covered anymore.

We can also describe well-covered graphs in another way. They are graphs where every maximal independent set has the same size. Michael D. Plummer first defined and studied well-covered graphs in 1970.

There are many kinds of well-covered graphs. These include complete graphs and balanced complete bipartite graphs. Another example is the rook's graph. In a rook's graph, vertices represent squares on a chessboard. Edges represent the moves of a chess rook. Mathematicians know how to find well-covered cubic graphs and well-covered claw-free graphs. They can also find well-covered graphs with high girth. Computers can find these graphs in polynomial time (quickly). But for other kinds of graphs, it is very hard to test if they are well-covered. This is a coNP-complete problem.

Definitions

[change | change source]

A vertex cover in an undirected graph is a group of vertices. This group touches every edge in the graph. A vertex cover is minimal if we cannot remove any vertex from it. If we remove a vertex, the edges are not all covered. A vertex cover is minimum if there is no other cover with fewer vertices. A well-covered graph is a graph where every minimal cover is also a minimum cover. In the first paper about these graphs, Plummer wrote that this is the same as saying every minimal cover has the same number of vertices.[1]

An independent set in a graph is a group of vertices. No two vertices in this group are connected to each other. Let C be a vertex cover in a graph G. The complement of C (the vertices not in C) must be an independent set. The opposite is also true. C is a minimal vertex cover if its complement I is a maximal independent set. C is a minimum vertex cover if its complement is a maximum independent set. Because of this, a well-covered graph is also a graph where every maximal independent set has the same size. Or, we can say it is a graph where every maximal independent set is a maximum independent set.[2]

The first paper about well-covered graphs only talked about connected graphs.[3] But these definitions work for disconnected graphs too. Later, some writers used a different rule. They said a well-covered graph must not have any isolated vertices (vertices with no edges).[4]

Connected well-covered graphs do not have essential vertices. An essential vertex is a vertex that is in every minimum vertex cover. Also, every well-covered graph is a critical graph for vertex covering. This means if we delete any vertex v, the new graph has a smaller minimum vertex cover.[3]

The independence complex of a graph G is a simplicial complex. It has a simplex for each independent set in G. A simplicial complex is pure if all its biggest simplices have the same cardinality (size). So, a well-covered graph is a graph with a pure independence complex.[5]

Examples

[change | change source]
abcdefgh
8
d8 white rook
g7 white rook
c6 white rook
a5 white rook
b4 white rook
h3 white rook
e2 white rook
f1 white rook
8
77
66
55
44
33
22
11
abcdefgh
Eight rooks on a chessboard. They do not attack each other. If we place fewer than eight rooks, and they do not attack each other, we can always add more until there are eight.

A cycle graph with four or five vertices is well-covered. In both graphs, every maximal independent set has size two. A cycle with seven vertices is also well-covered. A path with three edges is well-covered too.[6]

Every complete graph is well-covered. In a complete graph, every maximal independent set has only one vertex. Every cluster graph is also well-covered. A cluster graph is made of separate complete graphs.[7]

A complete bipartite graph is well-covered if both sides have the same number of vertices. These two sides are the only two maximal independent sets. The complement graph of a triangle-free graph is well-covered if it has no isolated vertices. In this graph, no independent set is larger than two. Also, every single vertex can be part of a two-vertex independent set.[6]

A rook's graph is well-covered. Imagine placing rooks on a chessboard so they do not attack each other. We can always keep adding rooks until there is one on every row and column.[8]

Imagine a graph where the vertices are the diagonals of a simple polygon. The edges connect diagonals that cross each other. This graph is well-covered. Its maximal independent sets are triangulations of the polygon. All triangulations have the same number of edges.[9]

Let G be a graph with n vertices. We can make a new graph called the rooted product of G with a one-edge graph. To do this, we add n new vertices to G. Each new vertex connects to one vertex in G. This new graph is well-covered. A maximal independent set in the new graph must have size n.[10]

There is a more general rule. Take any graph G and a clique cover (a way to split the vertices into groups called cliques). We can add a new vertex to each clique. This makes a graph Gp. This new graph is well-covered. The rooted product is a special case of this. In that case, each clique has only one vertex.[11] Because of this, every graph is an induced subgraph of a well-covered graph.

Bipartiteness, very well covered graphs, and girth

[change | change source]

Favaron (1982) writes about a very well covered graph. This is a well-covered graph that has no isolated vertices. Also, every maximal independent set must have exactly half of the vertices. This means every minimal vertex cover also has half of the vertices. The rooted products of a graph G and a one-edge graph are very well covered.

Bipartite well-covered graphs are also very well covered. These were studied by Ravindra (1977) and Berge (1981). In a bipartite graph, the vertices are in two groups. If there are no isolated vertices, each group is a maximal independent set. If the graph is well-covered, both groups must have the same number of vertices. In a well-covered graph with n vertices, the largest independent set has at most n/2 vertices. So, very well covered graphs are the well covered graphs with the biggest possible independent sets.[12]

A bipartite graph G is well-covered if it has a perfect matching M with a special property. For every edge uv in M, look at the neighbors of u and v. The induced subgraph of these neighbors must be a complete bipartite graph.[13]

We can use matchings to describe very well covered graphs too. A graph G is very well covered if it has a perfect matching M that follows two rules:

  1. No edge in M is part of a triangle in G.
  2. If an edge in M is the middle of a path with three edges, the ends of the path must be connected.

If G is very well covered, every perfect matching follows these rules.[14]

Trees are a type of bipartite graph. It is easy to test if a tree is well-covered. If G is a tree with more than two vertices, it is well-covered if every non-leaf node connects to exactly one leaf.[13]

This rule also works for graphs that look like trees locally. If a graph has girth eight or more, it is well-covered if every vertex with degree more than one has exactly one neighbor with degree one.[15] There is a similar rule for well-covered graphs with girth five or more.[16]

Regularity and planarity

[change | change source]
The seven cubic 3-connected well-covered graphs
A cubic 1-connected well-covered graph. It is made by replacing each node of a six-node path with one of three fragments.
The snub disphenoid. It is one of four well-covered 4-connected 3-dimensional simplicial polyhedra.

Mathematicians have listed all the cubic (3-regular) well-covered graphs. There are seven 3-connected examples. There are also three infinite families of cubic graphs that are less connected.[17]

The seven 3-connected cubic well-covered graphs are:

  • The complete graph K4.
  • The graph of the triangular prism.
  • The graph of the pentagonal prism.
  • The Dürer graph.
  • The utility graph K3,3.
  • An eight-vertex graph made from the utility graph by a Y-Δ transform.
  • The 14-vertex generalized Petersen graph G(7,2).[18]

The first four of these are planar graphs. They are the only four cubic polyhedral graphs that are well-covered.[19] Four of these graphs are generalized Petersen graphs.

The other cubic well-covered graphs are made by replacing nodes in a path or cycle. We replace them with shapes called fragments. Plummer (1993) calls these fragments A, B, and C.

  • Fragment A has a bridge. Using fragment A makes the graph 1-vertex-connected. All these graphs are planar.[17]
  • There are two types of 2-vertex-connected graphs. One type uses fragments A and B on a cycle. The other uses fragments B and C on a path. All graphs in the second type are planar.[17]

Researchers have also looked at well-covered simplicial polyhedra. These are the same as well-covered maximal planar graphs. Every maximal planar graph with five or more vertices has vertex connectivity 3, 4, or 5.[20]

  • There are no well-covered 5-connected maximal planar graphs.
  • There are only four 4-connected ones: the regular octahedron, the pentagonal dipyramid, the snub disphenoid, and an irregular polyhedron with 12 vertices.
  • There are infinitely many 3-connected ones.[21]

For example, take a maximal planar graph with t separate triangle faces. We can divide each of these triangles into three new triangles. This makes a well-covered maximal planar graph.[22]

Complexity

[change | change source]

It is hard to check if a graph is well-covered. It is a coNP-complete problem.[23] This means it is NP-complete to check if a graph has two maximal independent sets of different sizes. It is easy to find maximum independent sets in well-covered graphs. But it is NP-hard to find a maximum independent set if we do not know the graph is well-covered.[24]

However, we can test if a graph G is very well covered in polynomial time (quickly). First, we find the edges that follow the rules for a very well covered graph. Then we check if these edges form a perfect matching.[14] Some problems that are usually very hard, like finding a Hamiltonian cycle, are easy for very well covered graphs.[25]

A graph is equimatchable if every maximal matching is a maximum matching. This is the same as saying its line graph is well-covered.[26] A graph is randomly matchable if every maximal matching is a perfect matching. The only connected graphs like this are complete graphs and balanced complete bipartite graphs.[27] We can test if a line graph or a claw-free graph is well-covered in polynomial time.[28]

We can also quickly recognize well-covered graphs with girth five or more. The same is true for 3-regular well-covered graphs.[29]

Notes

[change | change source]
  1. ↑ 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; people do not use these words this way anymore.
  2. ↑ Plummer (1993).
  3. 1 2 Plummer (1970).
  4. ↑ Favaron (1982).
  5. ↑ For examples of papers using these words, see Dochtermann & Engström (2009) and Cook & Nagel (2010).
  6. 1 2 Sankaranarayana (1994), Section 2.4, "Examples", p. 7.
  7. ↑ Holroyd & Talbot (2005).
  8. ↑ The rook's graphs are the line graphs of complete bipartite graphs. So, saying rook's graphs are well-covered is the same as saying complete bipartite graphs are equimatchable. See Sumner (1979) and Lesk, Plummer & Pulleyblank (1984).
  9. ↑ Greenberg (1993).
  10. ↑ This example was studied by Fink et al. (1985). They are also exactly the graphs where the domination number is n/2. Theorem 4.4 of Dochtermann & Engström (2009) also talks about this property.
  11. ↑ For the clique cover construction, see Cook & Nagel (2010), Lemma 3.2. This source talks about the purity of the independence complex.
  12. ↑ Berge (1981).
  13. 1 2 Ravindra (1977); Plummer (1993).
  14. 1 2 Staples (1975); Favaron (1982); Plummer (1993).
  15. ↑ Finbow & Hartnell (1983); Plummer (1993), Theorem 4.1.
  16. ↑ Finbow & Hartnell (1983); Plummer (1993), Theorem 4.2.
  17. 1 2 3 Campbell (1987); Campbell & Plummer (1988); Plummer (1993).
  18. ↑ Campbell (1987); Finbow, Hartnell & Nowakowski (1988); Campbell, Ellingham & Royle (1993); Plummer (1993).
  19. ↑ Campbell & Plummer (1988).
  20. ↑ The complete graphs on 1, 2, 3, and 4 vertices are all maximal planar and well-covered.
  21. ↑ Finbow, Hartnell, and Nowakowski et al. (2003, 2009, 2010).
  22. ↑ These graphs are called the -family by Finbow et al. (2016).
  23. ↑ Sankaranarayana & Stewart (1992); Chvátal & Slater (1993); Caro, Sebő & Tarsi (1996).
  24. ↑ Raghavan & Spinrad (2003).
  25. ↑ Sankaranarayana & Stewart (1992).
  26. ↑ Lesk, Plummer & Pulleyblank (1984).
  27. ↑ Sumner (1979).
  28. ↑ Lesk, Plummer & Pulleyblank (1984); Tankus & Tarsi (1996); Tankus & Tarsi (1997).
  29. ↑ Campbell, Ellingham & Royle (1993); Plummer (1993).

References

[change | change source]
  • Berge, Claude (1981), "Some common properties for regularizable graphs, edge-critical graphs and B-graphs", Graph theory and algorithms (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980), Lecture Notes in Computer Science, vol. 108, Berlin: Springer, pp. 108–123, doi:10.1007/3-540-10704-5_10, ISBN 978-3-540-10704-0, MR 0622929.
  • Campbell, S. R. (1987), Some results on planar well-covered graphs, Ph.D. thesis, Vanderbilt University, Department of Mathematics. As cited by Plummer (1993).
  • Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F. (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212, MR 1220613.
  • Campbell, Stephen R.; Plummer, Michael D. (1988), "On well-covered 3-polytopes", Ars Combinatoria, 25 (A): 215–242, MR 0942505.
  • Caro, Yair; Sebő, András; Tarsi, Michael (1996), "Recognizing greedy structures", Journal of Algorithms, 20 (1): 137–156, doi:10.1006/jagm.1996.0006, MR 1368720.
  • Chvátal, Václav; Slater, Peter J. (1993), "A note on well-covered graphs", Quo vadis, graph theory?, Annals of Discrete Mathematics, vol. 55, Amsterdam: North-Holland, pp. 179–181, MR 1217991.
  • Cook, David II; Nagel, Uwe (2010), "Cohen-Macaulay graphs and face vectors of flag complexes", SIAM Journal on Discrete Mathematics, 26: 89–101, arXiv:1003.4447, Bibcode:2010arXiv1003.4447C, doi:10.1137/100818170.
  • Dochtermann, Anton; Engström, Alexander (2009), "Algebraic properties of edge ideals via combinatorial topology", Electronic Journal of Combinatorics, 16 (2): Research Paper 2, doi:10.37236/68, MR 2515765.
  • Favaron, O. (1982), "Very well covered graphs", Discrete Mathematics, 42 (2–3): 177–187, doi:10.1016/0012-365X(82)90215-1, MR 0677051.
  • Finbow, A. S.; Hartnell, B. L. (1983), "A game related to covering by stars", Ars Combinatoria, 16 (A): 189–198, MR 0737090.
  • Finbow, A.; Hartnell, B.; Nowakowski, R. (1988), "Well-dominated graphs: a collection of well-covered ones", Ars Combinatoria, 25 (A): 5–10, MR 0942485.
  • Finbow, A.; Hartnell, B.; Nowakowski, R. J. (1993), "A characterization of well covered graphs of girth 5 or greater", Journal of Combinatorial Theory, Series B, 57 (1): 44–68, doi:10.1006/jctb.1993.1005, MR 1198396.
  • Finbow, A.; Hartnell, B.; Nowakowski, R.; Plummer, Michael D. (2003), "On well-covered triangulations. I", Discrete Applied Mathematics, 132 (1–3): 97–108, doi:10.1016/S0166-218X(03)00393-7, MR 2024267.
  • Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2009), "On well-covered triangulations. II", Discrete Applied Mathematics, 157 (13): 2799–2817, doi:10.1016/j.dam.2009.03.014, MR 2537505.
  • Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2010), "On well-covered triangulations. III", Discrete Applied Mathematics, 158 (8): 894–912, doi:10.1016/j.dam.2009.08.002, MR 2602814.
  • Finbow, Arthur S.; Hartnell, Bert L.; Nowakowski, Richard J.; Plummer, Michael D. (2016), "Well-covered triangulations: Part IV", Discrete Applied Mathematics, 215: 71–94, doi:10.1016/j.dam.2016.06.030, MR 3548980.
  • Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J. (1985), "On graphs having domination number half their order", Period. Math. Hungar., 16 (4): 287–293, doi:10.1007/BF01848079, MR 0833264, S2CID 121734811.
  • Greenberg, Peter (1993), "Piecewise SL2Z geometry", Transactions of the American Mathematical Society, 335 (2): 705–720, doi:10.2307/2154401, JSTOR 2154401, MR 1140914.
  • Holroyd, Fred; Talbot, John (2005), "Graphs with the Erdős-Ko-Rado property", Discrete Mathematics, 293 (1–3): 165–176, arXiv:math/0307073, doi:10.1016/j.disc.2004.08.028, MR 2136060.
  • Lesk, M.; Plummer, M. D.; Pulleyblank, W. R. (1984), "Equi-matchable graphs", in Bollobás, Béla (ed.), Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős, London: Academic Press, pp. 239–254, MR 0777180.
  • Plummer, Michael D. (1970), "Some covering concepts in graphs", Journal of Combinatorial Theory, 8: 91–98, doi:10.1016/S0021-9800(70)80011-4, MR 0289347.
  • Plummer, Michael D. (1993), "Well-covered graphs: a survey", Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, MR 1254158, archived from the original on May 27, 2012.
  • Raghavan, Vijay; Spinrad, Jeremy (2003), "Robust algorithms for restricted domains", Journal of Algorithms, 48 (1): 160–172, doi:10.1016/S0196-6774(03)00048-8, MR 2006100, S2CID 16327087.
  • Ravindra, G. (1977), "Well-covered graphs", Journal of Combinatorics, Information and System Sciences, 2 (1): 20–21, MR 0469831.
  • Sankaranarayana, Ramesh S. (1994), Well-covered graphs: some new sub-classes and complexity results (Doctoral dissertation), University of Alberta
  • Sankaranarayana, Ramesh S.; Stewart, Lorna K. (1992), "Complexity results for well-covered graphs", Networks, 22 (3): 247–262, CiteSeerX 10.1.1.47.9278, doi:10.1002/net.3230220304, MR 1161178 {{citation}}: Cite uses deprecated parameter |citeseerx= (help).
  • Staples, J. (1975), On some subclasses of well-covered graphs, Ph.D. thesis, Vanderbilt University, Department of Mathematics. As cited by Plummer (1993).
  • Sumner, David P. (1979), "Randomly matchable graphs", Journal of Graph Theory, 3 (2): 183–186, doi:10.1002/jgt.3190030209, MR 0530304.
  • Tankus, David; Tarsi, Michael (1996), "Well-covered claw-free graphs", Journal of Combinatorial Theory, Series B, 66 (2): 293–302, doi:10.1006/jctb.1996.0022, MR 1376052.
  • Tankus, David; Tarsi, Michael (1997), "The structure of well-covered graphs and the complexity of their recognition problems", Journal of Combinatorial Theory, Series B, 69 (2): 230–233, doi:10.1006/jctb.1996.1742, MR 1438624.
Retrieved from "https://simple.wikipedia.org/w/index.php?title=Well-covered_graph&oldid=10693923"