Clever Geek Handbook
📜 ⬆️ ⬇️

Well Covered Count

Well-covered graph, intersection graph of nine diagonals of a hexagon . Three red vertices form one of its 14 maximum independent sets of the same size, and six blue vertices form an additional minimum vertex covering.

In graph theory, a well-covered graph (sometimes the name is well-covered graph ) is an undirected graph in which any minimum vertex cover is the same size (like any other minimum vertex cover). Well-covered graphs were defined and studied by Plummer [1] .

Content

Definitions

A vertex covering of a graph is a set of vertices of a graph such that at each edge at least one end enters into the covering. Coverage is minimal (irreducible) if removing any vertex destroys the coverage. A coverage is called least if there is no other coverage of the graph with fewer vertices. A well-covered graph is a graph in which any minimal coverage is also the smallest. In his original article, Plummer writes [1] that the definition of a well-covered graph is “obviously equivalent” to the property that any two minimal coverings are of the same size.

An independent set of a graph is a set of vertices in which no two vertices are adjacent. If C is a vertex cover of a graph G , the complement C must be an independent set, and vice versa. C is a minimal vertex coverage if and only if its complement I is a maximal independent set, and C is the smallest vertex cover if and only if its complement is the largest independent set. Thus, a well-covered graph is, equivalently, a graph in which each maximal independent set is largest.

In the original article on well-covered graphs, these definitions applied only to connected graphs [1] , although they also make sense for disconnected graphs. Some later authors replaced the connectivity requirement with a weaker requirement for the absence of isolated vertices [2] . Both connected well-covered graphs and well-covered graphs without isolated vertices cannot have significant vertices , vertices that belong to each smallest vertex cover [1] . In addition, any well-covered graph is a critical graph for vertex coverings in the sense that removing any vertex v from the graph gives a graph with a smaller smallest vertex cover [1] .

graph G is a simplicial complex having a simplex for each independent set in G. It is said that a simplicial complex is simple if all its maximal simplexes have the same cardinality, so a well-covered graph is equivalent to a graph with a simple independence complex [3] .

Examples

abcdefgh
eight
 
 
 
 
 
 
 
 
 
eight
77
66
fivefive
fourfour
33
22
oneone
abcdefgh
Non-attacking each other eight rooks on a chessboard. If you place fewer rooks that do not attack each other, there will always be a place where to place an additional rook, while all the rooks will not attack each other.

A graph cycle of length four or five is well covered — in both cases the maximum independent set is two. A cycle of length seven and a path of length three are also well covered. Any complete graph is well covered - any maximal independent set consists of a single vertex. A complete bipartite graph is well covered if both its parts have an equal number of vertices - for it there are only two maximum independent sets. The rook graph is well covered - if you place any number of rooks on the chessboard so that no two rooks attack each other, you can always add another non-attacking rook until there is a rook on each line and each column.

If P is a polygon or a set of points, S is the set of open intervals having vertices P as end points and not containing points P inside, and G is the intersection graph of S (a graph having vertices for each interval from S and edges for each pair intersecting intervals), then G is well covered. For this case, any maximal independent set in G corresponds to the set of edges in the triangulation of the polygon P , and the calculation of the Euler characteristic shows that any two triangularizations have the same number of edges [4] .

If G is a graph with n vertices, the G with a graph consisting of one edge (that is, the graph H formed by adding n new vertices to G , each with degree one and all are connected to different vertices, in G ) is well covered. The maximal independent set in H must consist of an arbitrary independent set in G, together with neighbors of degree one, from the additional set. Thus, this set has size n [5] . In general, if any graph G along with clique coverage is given (dividing p vertices of G into cliques), the graph G p formed by adding a vertex for each clique is well covered. The root product is a special case of this construction when p consists of n cliques containing one vertex [6] . Thus, any graph is a subgraph of a well-covered graph.

Bipartite, very well covered graphs and girth

Favaron defines a very well-covered graph as a well-covered graph (possibly disconnected, but without isolated vertices), in which any maximum independent set (and therefore also any minimum vertex coverage) contains exactly half the vertices [2] . This definition includes the root products of a graph G and a graph consisting of one edge. This also includes, for example, bipartite well-covered graphs studied by Ravindra and Berge [7] [8] - in a bipartite graph without isolated vertices, both sides of any fraction form maximum independent sets (and minimal vertex coverings), so if the graph is well covered , both sides must have an equal number of vertices. In a well-covered graph with n vertices, the size of the maximum independent set does not exceed n / 2 , so very well-covered graphs are well-covered graphs in which the largest independent set has the maximum possible size for the graphs [8] .

A bipartite graph G is well covered if and only if it is a perfect matching M with the property that for any edge uv from M the generated subgraph of the neighbors u and v forms a complete bipartite graph [7] [9] . Characterization in terms of matching can be extended from bipartite graphs to very well-covered graphs - a graph G is very well-covered if and only if the graph has a perfect matching M with the following two properties:

  1. No edge M belongs to a triangle in G ;
  2. If the edge M is central in the path, consisting of three edges in G , then the two end vertices of the path must be adjacent.

However, if G is very well covered, then any perfect matching in G satisfies these properties [10] .

Trees are a special case of bipartite graphs, and checking if a tree is well covered can be considered as a very simple case of characterizing well covered bipartite graphs - if G is a tree with more than two vertices, it is well covered if and only if each non-leaf edge tree adjacent to exactly one leaf [7] [9] . The same characterization applies to graphs that are locally similar to trees, in the sense that the close environment of any vertex is acyclic - if the graph has a girth of eight or more (so for any vertex v a subgraph of vertices at a distance of three from v is acyclic), then it is well covered if and only if any vertex with degree greater than two has exactly one neighbor with degree one [11] . A closely related, but more complex characterization applies to well-covered girth graphs of five or more [12] [13] .

Homogeneity and Planarity

 
Seven cubic 3-connected well-covered graphs
 
A cubic 1-connected well-covered graph formed by replacing each edge of the six-edge path with one of three fragments
 
A flat-nosed biclinoid , one of four well-covered 4-connected 3-dimensional simplicial polytopes.

Cubic ( 3-regular ) well-covered graphs are classified - the family consists of seven 3-connected representatives and, in addition, includes three infinite families of cubic graphs with less connectivity.

These seven 3-connected cubic well-covered graphs include the complete graph K 4 , the graphs of triangular and pentagonal prisms , the Dürer graph , the communal graph K 3.3 , the eight-vertex graph obtained by the Y-Δ transformation from the communal graph and the generalized Petersen graph G (7.2) with 14 vertices [14] . Of these graphs, the first four are planar , and therefore only they are also four cubic polyhedral graphs (graphs of simple convex polyhedra ) that are well covered. Four of the seven graphs (both prisms, the Dürer graph and G (7,2) ) are generalized Petersen graphs.

1- and 2-connected cubic well-covered graphs are formed by replacing the vertices of a graph or cycle with three fragments, which Plummer designated A , B and C [9] . Fragments A or B can be used to replace the vertices of the loop or internal vertices of the path, while fragment C is used to replace the two final vertices of the path. Fragment A contains a bridge , so as a result of replacing some vertices with fragment A (the others are replaced by B and C ), we obtain a vertex 1-connected cubic well-covered graph. All vertex 1-connected cubic well-covered graphs have this form, and all such graphs are planar [15] .

There are two types of vertex 2-connected cubic well-covered graphs. One of these two families is formed by replacing the vertices of the cycle by fragments A and B , while at least two fragments must be of type A. A graph of this type is planar if and only if it does not contain fragments of type B. Another family is formed by replacing the vertices of the path with fragments of type B and C. All such graphs are planar [15] .

Considering the good coverage of simple polytopes in three-dimensional space, the researchers consider simplicial polyhedra , or, equivalently, well-covered maximal planar graphs, to be well covered. Any maximal planar graph with five or more vertices has a vertex connectivity of 3, 4, or 5 [16] . 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 a regular octahedron , a pentagonal bipyramid , a flat-faced two-clinoid and an irregular polyhedron (non-convex ) with 12 vertices, 30 edges and 20 triangular faces. However, there are infinitely many 3-connected well-covered maximal planar graphs [17] [18] [19] . For example, a well-covered 3-connected maximal planar graph can be obtained by constructing a clique cover [6] from any maximal planar graph with 3 t vertices, in which there are t unconnected triangular faces, by adding t new vertices, one each in this facets.

Difficulty

Checking whether a graph contains two maximal independent sets of different sizes is NP-complete . That is, checking whether a graph is well covered is a coNP-complete problem [20] . Although it is easy to find the largest independent sets in a graph that is known to be well covered, for all graphs the problem of determining the largest independent set, as well as checking that the graph is not well covered, is NP-hard [21] .

In contrast, it is possible to verify that a given graph G is very well covered in polynomial time . To do this, we find a subgraph H of G consisting of edges satisfying two matching properties in a very well-covered graph, and then use the algorithm for finding the perfect cover to check if H has a perfect match [10] . Some problems that are NP-complete for arbitrary graphs, such as the problem of finding the Hamiltonian path , can be solved in polynomial time for any well-covered graph [22] .

It is said that a graph is uniformly matching if any maximum matching is greatest. That is, it is uniformly matching if its edge graph is well covered. One can check whether an edge graph, or, more generally, a graph without claws , is well covered in polynomial time [23] .

Characterization of well-covered graphs with girth of five or more and well-covered graphs that are 3-regular also leads to efficient polynomial recognition algorithms for such graphs [24] .

Notes

  1. ↑ 1 2 3 4 5 Plummer, 1970 .
  2. ↑ 1 2 Favaron, 1982 .
  3. ↑ As an example, such terminology is used in the article by Dochtermann and Engström ( Dochtermann & Engström (2009 )), as well as in the article by Cook and Nagel ( Cook, Nagel (2010 )).
  4. ↑ Greenberg, 1993 .
  5. ↑ This class of examples was studied by Jacobson, Kinch, Roberts ( Fink, Jacobson, Kinch, Roberts (1985 )). A class is also (together with a four-edge cycle, which is also well covered) the set of graphs whose dominant number is n / 2 . The property of good coverage of these graphs is also affirmed in another terminology (as simple independence complexes) in Theorem 4.4 of the article by Dochtermann and Engström ( Dochtermann & Engström (2009 )).
  6. ↑ 1 2 Cook, Nagel, 2010 .
  7. ↑ 1 2 3 Ravindra, 1977 .
  8. ↑ 1 2 Berge, 1981 .
  9. ↑ 1 2 3 Plummer, 1993 .
  10. ↑ 1 2 Staples (1975 ); Favaron (1982 ); Plummer (1993 ).
  11. ↑ Finbow & Hartnell (1983 ); Plummer (1993 ), Theorem 4.1.
  12. ↑ Finbow & Hartnell, 1983 .
  13. ↑ Plummer, 1993 , Theorem 4.2.
  14. ↑ Campbell (1987 ); Finbow, Hartnell, Nowakowski (1988 ); Campbell, Ellingham & Royle (1993 ); Plummer (1993 ).
  15. ↑ 1 2 Campbell (1987 ); Campbell & Plummer (1988 ); Plummer (1993 ).
  16. ↑ Complete graphs with 1, 2, 3, and 4 vertices are maximal planar and well covered. Their vertex connectivity is either not limited or does not exceed three, which depends on the details of the definition of vertex connectivity. For larger maximum planar graphs, these nuances do not matter.
  17. ↑ Finbow, Hartnell, Nowakowski, Plummer, 2003 .
  18. ↑ Finbow, Hartnell, Nowakowski, Plummer, 2009 .
  19. ↑ Finbow, Hartnell, Nowakowski, Plummer, 2010 .
  20. ↑ Sankaranarayana, Stewart (1992 ); Chvátal & Slater (1993 ); Caro, Sebő & Tarsi (1996 ).
  21. ↑ Raghavan, Spinrad, 2003 .
  22. ↑ Sankaranarayana, Stewart, 1992 .
  23. ↑ Lesk, Plummer, Pulleyblank (1984 ); Tankus, Tarsi (1996 ); Tankus, Tarsi (1997 ).
  24. ↑ Campbell, Ellingham & Royle (1993 ); Plummer (1993 ).

Literature

  • Claude Berge. Graph theory and algorithms (Proc. Sympos., Res. Inst. Electr. Comm., Tohoku Univ., Sendai, 1980). - Berlin: Springer, 1981. - T. 108. - S. 108-123. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 3-540-10704-5_10 .
  • SR Campbell. Some results on cubic well-covered graphs. - Vanderbilt University, Department of Mathematics, 1987. As quoted by Plummer ( Plummer (1993 )).
  • SR Campbell, MN Ellingham, Gordon F. Royle. A characterization of well-covered cubic graphs // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993 .-- T. 13 . - S. 193-212 .
  • Stephen R. Campbell, Michael D. Plummer. On well-covered 3-polytopes // Ars Combinatoria . - 1988.- T. 25 , no. A. - S. 215-242 .
  • Yair Caro, András Sebő, Michael Tarsi. Recognizing greedy structures // Journal of Algorithms. - 1996. - T. 20 , no. 1 . - S. 137-156 . - DOI : 10.1006 / jagm.1996.0006 .
  • Václav Chvátal, Peter J. Slater. Quo vadis, graph theory ?. - Amsterdam: North-Holland, 1993 .-- T. 55. - S. 179-181. - (Annals of Discrete Mathematics).
  • David Cook II, Uwe Nagel. Cohen-Macaulay graphs and face vectors of flag complexes. - 2010 .-- arXiv : 1003.4447 .
  • Anton Dochtermann, Alexander Engström. Algebraic properties of edge ideals via combinatorial topology // Electronic Journal of Combinatorics . - 2009. - T. 16 , no. 2 - C. Research Paper 2 .
  • O. Favaron. Very well covered graphs // Discrete Mathematics . - 1982. - T. 42 , no. 2-3 . - S. 177-187 . - DOI : 10.1016 / 0012-365X (82) 90215-1 .
  • AS Finbow, BL Hartnell. A game related to covering by stars // Ars Combinatoria . - 1983 .-- T. 16 , no. A. - S. 189—198 .
  • A. Finbow, B. Hartnell, R. Nowakowski. Well-dominated graphs: a collection of well-covered ones // Ars Combinatoria . - 1988.- T. 25 , no. A. - S. 5-10 .
  • A. Finbow, B. Hartnell, RJ Nowakowski. A characterization of well covered graphs of girth 5 or greater // Journal of Combinatorial Theory . - 1993.- T. 57 , no. 1 . - S. 44-68 . - DOI : 10.1006 / jctb.1993.1005 .
  • A. Finbow, B. Hartnell, R. Nowakowski, Michael D. Plummer. On well-covered triangulations. I // Discrete Applied Mathematics . - 2003. - T. 132 , no. 1-3 . - S. 97-108 . - DOI : 10.1016 / S0166-218X (03) 00393-7 .
  • Arthur S. Finbow, Bert L. Hartnell, Richard J. Nowakowski, Michael D. Plummer. On well-covered triangulations. II // Discrete Applied Mathematics . - 2009. - T. 157 , no. 13 . - S. 2799-2817 . - DOI : 10.1016 / j.dam.2009.03.01.014 .
  • Arthur S. Finbow, Bert L. Hartnell, Richard J. Nowakowski, Michael D. Plummer. On well-covered triangulations. III // Discrete Applied Mathematics . - 2010 .-- T. 158 , no. 8 - S. 894-912 . - DOI : 10.1016 / j.dam.2009.08.08.002 .
  • JF Fink, MS Jacobson, LF Kinch, J. Roberts. On graphs having domination number half their order // Period. Math Hungar .. - 1985.- T. 16 , no. 4 - S. 287-293 . - DOI : 10.1007 / BF01848079 .
  • Peter Greenberg. Piecewise SL 2 Z geometry // Transactions of the American Mathematical Society . - 1993.- T. 335 , no. 2 - S. 705-720 . - DOI : 10.2307 / 2154401 .
  • M. Lesk, MD Plummer, WR Pulleyblank. Graph theory and combinatorics (Cambridge, 1983). - London: Academic Press, 1984. - S. 239-254.
  • Michael D. Plummer. Some covering concepts in graphs // Journal of Combinatorial Theory . - 1970.- T. 8 . - S. 91-98 . - DOI : 10.1016 / S0021-9800 (70) 80011-4 .
  • Michael D. Plummer. Well-covered graphs: a survey // Quaestiones Mathematicae. - 1993. - T. 16 , no. 3 - S. 253-287 . - DOI : 10.1080 / 16073606.1993.9631737 .
  • Vijay Raghavan, Jeremy Spinrad. Robust algorithms for restricted domains // Journal of Algorithms. - 2003. - T. 48 , no. 1 . - S. 160—172 . - DOI : 10.1016 / S0196-6774 (03) 00048-8 .
  • G. Ravindra. Well-covered graphs // Journal of Combinatorics, Information and System Sciences. - 1977. - T. 2 , no. 1 . - S. 20-21 .
  • Ramesh S. Sankaranarayana, Lorna K. Stewart. Complexity results for well-covered graphs // Networks. - 1992. - T. 22 , no. 3 - S. 247-262 . - DOI : 10.1002 / net.3230220304 .
  • J. Staples. On some subclasses of well-covered graphs. - Vanderbilt University, Department of Mathematics, 1975. As quoted by Plummer ( Plummer (1993 )).
  • David Tankus, Michael Tarsi. Well-covered claw-free graphs // Journal of Combinatorial Theory . - 1996.- T. 66 , no. 2 - S. 293-302 . - DOI : 10.1006 / jctb.1996.0022 .
  • David Tankus, Michael Tarsi. The structure of well-covered graphs and the complexity of their recognition problems // Journal of Combinatorial Theory . - 1997. - T. 69 , no. 2 - S. 230-233 . - DOI : 10.1006 / jctb.1996.1742 .
Source - https://ru.wikipedia.org/w/index.php?title=Good_covered_graph&oldid=94888217


More articles:

  • Repression in the Byelorussian SSR
  • Dmitriev, Vasily Polikarpovich
  • Rashkulev, Dmitry Kharlampievich
  • Nykobing (Falster)
  • Gogua, Cedric
  • Mistress (TV series)
  • Radio 1
  • Russian-Kachim Village Council
  • Corn (group)
  • Akhatov, Shaukat Nurligayanovich

All articles

Clever Geek | 2019