- Tytuł:
- On well-covered graphs of odd girth 7 or greater
- Autorzy:
-
Randerath, Bert
Vestergaard, Preben - Powiązania:
- https://bibliotekanauki.pl/articles/743557.pdf
- Data publikacji:
- 2002
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
well-covered
independence number
domination number
odd girth - Opis:
- A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the graph. We prove that every isolate-vertex-free well-covered graph G containing neither C₃, C₅ nor C₇ as a subgraph is even very well-covered. Here, a isolate-vertex-free well-covered graph G is called very well-covered, if G satisfies α(G) = n/2. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. The domination number γ(G) is the minimum order of a dominating set of G. Obviously, the inequality γ(G) ≤ α(G) holds. The family $_{γ=α}$ of graphs G with γ(G) = α(G) forms a subclass of well-covered graphs. We prove that every connected member G of $_{γ=α}$ containing neither C₃ nor C₅ as a subgraph is a K₁, C₄,C₇ or a corona graph.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 159-172
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł