Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Bounds on global secure sets in cactus trees

100%

Jesse-Józefczyk K.

Open Mathematics

2012

tom 10

nr 3

1113-1124

Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances.

Secure sets and their expansion in cubic graphs

63%

Jesse-Józefczyk K., Sidorowicz E.

Open Mathematics

2014

tom 12

nr 11

1664-1673

Consider a graph whose vertices play the role of members of the opposing groups. The edge between two vertices means that these vertices may defend or attack each other. At one time, any attacker may attack only one vertex. Similarly, any defender fights for itself or helps exactly one of its neighbours. If we have a set of defenders that can repel any attack, then we say that the set is secure. Moreover, it is strong if it is also prepared for a raid of one additional foe who can strike anywhere. We show that almost any cubic graph of order n has a minimum strong secure set of cardinality less or equal to n/2 + 1. Moreover, we examine the possibility of an expansion of secure sets and strong secure sets.

Ograniczanie wyników

2 Open Mathematics

2 Jesse-Józefczyk K.

1 Sidorowicz E.

1 2014

1 2012

Wyniki wyszukiwania

Bounds on global secure sets in cactus trees

Secure sets and their expansion in cubic graphs