Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

New Bounds on the Signed Total Domination Number of Graphs

100%

Moghaddam S. M. H., Mojdeh D. A., Samadi B., Volkmann L.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 2

467-477

In this paper, we study the signed total domination number in graphs and present new sharp lower and upper bounds for this parameter. For example by making use of the classic theorem of Turán [8], we present a sharp lower bound on Kr+1-free graphs for r ≥ 2. Applying the concept of total limited packing we bound the signed total domination number of G with δ(G) ≥ 3 from above by [...] . Also, we prove that γst(T) ≤ n − 2(s − s′) for any tree T of order n, with s support vertices and s′ support vertices of degree two. Moreover, we characterize all trees attaining this bound.

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Mojdeh D. A.

1 Alimadadi A.

1 Moghaddam S. M. H.

1 Rad N. J.

1 Samadi B.

1 Volkmann L.

2 2016

Wyniki wyszukiwania

New Bounds on the Signed Total Domination Number of Graphs

Various Bounds for Liar’s Domination Number