Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Nordhaus-Gaddum

Sortuj według:

Ogranicz wyniki do:

Various Bounds for Liar’s Domination Number

100%

Alimadadi A., Mojdeh D. A., Rad N. J.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 3

629-641

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by γLR(G). In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for γLR(G), and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets.

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

Generalised irredundance in graphs: Nordhaus-Gaddum bounds

100%

Cockayne E., Finbow S.

Discussiones Mathematicae Graph Theory

2004

tom 24

nr 1

147-160

For each vertex s of the vertex subset S of a simple graph G, we define Boolean variables p = p(s,S), q = q(s,S) and r = r(s,S) which measure existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f = f(p,q,r) may be considered as a compound existence property of S-pns. The subset S is called an f-set of G if f = 1 for all s ∈ S and the class of f-sets of G is denoted by $Ω_f(G)$. Only 64 Boolean functions f can produce different classes $Ω_f(G)$, special cases of which include the independent sets, irredundant sets, open irredundant sets and CO-irredundant sets of G. Let $Q_f(G)$ be the maximum cardinality of an f-set of G. For each of the 64 functions f, we establish sharp upper bounds for the sum $Q_f(G) + Q_f(G̅)$ and the product $Q_f(G)Q_f(G̅)$ in terms of n, the order of G.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Alimadadi A.

1 Cockayne E.

1 Finbow S.

1 Mojdeh D. A.

1 Rad N. J.

1 2016

1 2004

Wyniki wyszukiwania

Various Bounds for Liar’s Domination Number

Generalised irredundance in graphs: Nordhaus-Gaddum bounds