Wyniki wyszukiwania dla: alliances in graphs

• Global edge alliances in graphs

  Publikacja

  • R. Lewoń
  • A. Małafiejska
  • M. Małafiejski
  • K. Wereszko

  - DISCRETE APPLIED MATHEMATICS - Rok 2019

  In the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...

  Pełny tekst do pobrania w portalu

• Strategic balance in graphs

  Publikacja

  • R. Lewoń
  • A. Małafiejska
  • M. Małafiejski

  - DISCRETE MATHEMATICS - Rok 2016

  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 portalu

• GRAPHS AND COMBINATORICS

  Czasopisma

  ISSN: 0911-0119 , eISSN: 1435-5914

• Tight bounds on global edge and complete alliances in trees

  Publikacja

  • K. Wereszko
  • R. Kozakiewicz
  • R. Lewoń
  • M. Małafiejski

  - Rok 2020

  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

• Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.

  Publikacja

  • H. Furmańczyk
  • A. Kosowski
  • P. Żyliński

  - Rok 2008

  W pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.

  Pełny tekst do pobrania w serwisie zewnętrznym

• Global defensive sets in graphs

  Publikacja

  • R. Lewoń
  • A. Małafiejska
  • M. Małafiejski

  - DISCRETE MATHEMATICS - Rok 2016

  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 portalu

• Global defensive secure structures

  Publikacja

  • M. Małafiejski
  • K. Wereszko

  - Rok 2022

  Let S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Discussiones Mathematicae Graph Theory

  Czasopisma

  ISSN: 1234-3099 , eISSN: 2083-5892

• Life Science Alliance

  Czasopisma

  eISSN: 2575-1077

• Connection graphs

  Publikacja

  • P. Bartłomiejczyk

  - FUNDAMENTA MATHEMATICAE - Rok 2006

  Pełny tekst do pobrania w serwisie zewnętrznym