Temat: dominating set - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Highly connected counterexamples to a conjecture on α-domination
Autorzy:: Tuza, Zsolt
Powiązania:: https://bibliotekanauki.pl/articles/744177.pdf
Data publikacji:: 2005
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph
dominating set
α-domination
Opis:: An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.
Źródło:: Discussiones Mathematicae Graph Theory; 2005, 25, 3; 435-440
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Domination in partitioned graphs
Autorzy:: Tuza, Zsolt
Vestergaard, Preben
Powiązania:: https://bibliotekanauki.pl/articles/743565.pdf
Data publikacji:: 2002
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph
dominating set
domination number
vertex partition
Opis:: 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δ)/(δ).
Źródło:: Discussiones Mathematicae Graph Theory; 2002, 22, 1; 199-210
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Graph domination in distance two
Autorzy:: Bacsó, Gábor
Tálos, Attila
Tuza, Zsolt
Powiązania:: https://bibliotekanauki.pl/articles/744316.pdf
Data publikacji:: 2005
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph
dominating set
connected domination
distance domination
forbidden induced subgraph
Opis:: Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $Dom Dom _u = Dom₂ _u$ holds for $_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, ₂ = {K₁} and ₃ = {all complete graphs}.) Some negative examples are also given.
Źródło:: Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 121-128
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja