Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On well-covered graphs of odd girth 7 or greater

100%

Randerath B., Vestergaard P.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 1

159-172

EN

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.

2

Domination in partitioned graphs

100%

Tuza Z., Vestergaard P.

Discussiones Mathematicae Graph Theory

|

2002

|

tom 22

|

nr 1

199-210

EN

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).

3

Even [a,b]-factors in graphs

100%

Kouider M., Vestergaard P.

Discussiones Mathematicae Graph Theory

|

2004

|

tom 24

|

nr 3

431-441

EN

Let a and b be integers 4 ≤ a ≤ b. We give simple, sufficient conditions for graphs to contain an even [a,b]-factor. The conditions are on the order and on the minimum degree, or on the edge-connectivity of the graph.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

3 Vestergaard P.

1 Kouider M.

1 Randerath B.

1 Tuza Z.

1 2004

2 2002

On well-covered graphs of odd girth 7 or greater

Domination in partitioned graphs

Even [a,b]-factors in graphs