Robert Lewoń - Profil naukowy - MOST Wiedzy

Wyszukiwarka

Wybrane publikacje

  • Global defensive sets in graphs

    In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Strategic balance in graphs

    For a given graph G, a nonempty subset S contained in V ( G ) is an alliance iff for each vertex v ∈ S there are at least as many vertices from the closed neighbourhood of v in S as in V ( G ) − S. An alliance is global if it is also a dominating set of G. The alliance partition number of G was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of V ( G ) such that each set is an alliance. Similarly,...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Tight bounds on global edge and complete alliances in trees

    In the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...

    Pełny tekst do pobrania w serwisie zewnętrznym

wyświetlono 262 razy