Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: dominating sets

Sortuj według:

Ogranicz wyniki do:

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

γ-graphs of graphs

100%

Fricke G., Hedetniemi S., Hedetniemi S., Hutson K.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 3

517-531

A set S ⊆ V is a dominating set of a graph G = (V,E) if every vertex in V -S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. In this paper we consider the family of all γ-sets in a graph G and we define the γ-graph G(γ) = (V(γ), E(γ)) of G to be the graph whose vertices V(γ) correspond 1-to-1 with the γ-sets of G, and two γ-sets, say D₁ and D₂, are adjacent in E(γ) if there exists a vertex v ∈ D₁ and a vertex w ∈ D₂ such that v is adjacent to w and D₁ = D₂ - {w} ∪ {v}, or equivalently, D₂ = D₁ - {v} ∪ {w}. In this paper we initiate the study of γ-graphs of graphs.

Convex universal fixers

80%

Lemańska M., Zuazua R.

Discussiones Mathematicae Graph Theory

2012

tom 32

nr 4

807-812

In [1] Burger and Mynhardt introduced the idea of universal fixers. Let G = (V, E) be a graph with n vertices and G' a copy of G. For a bijective function π: V(G) → V(G'), define the prism πG of G as follows: V(πG) = V(G) ∪ V(G') and $E(πG) = E(G) ∪ E(G') ∪ M_{π}$, where $M_{π} = {u π(u) | u ∈ V(G)}$. Let γ(G) be the domination number of G. If γ(πG) = γ(G) for any bijective function π, then G is called a universal fixer. In [9] it is conjectured that the only universal fixers are the edgeless graphs K̅ₙ. In this work we generalize the concept of universal fixers to the convex universal fixers. In the second section we give a characterization for convex universal fixers (Theorem 6) and finally, we give an in infinite family of convex universal fixers for an arbitrary natural number n ≥ 10.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Fricke G.

1 Hedetniemi S.

1 Hutson K.

1 Lemańska M.

1 Zuazua R.

1 2012

1 2011

Wyniki wyszukiwania

γ-graphs of graphs

Convex universal fixers