Global edge alliances in graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Global edge alliances in graphs

Abstrakt

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 minimum global edge alliance for certain classes: paths, cycles, wheels, complete k-partite graphs and complete k-ary trees. Moreover, we proved some lower bounds for arbitrary graphs.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Robert Lewoń, Anna Małafiejska, Michał Małafiejski, Kacper Wereszko. (2019). Global edge alliances in graphs, 1-11. https://doi.org/10.1016/j.dam.2018.09.002

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
DISCRETE APPLIED MATHEMATICS strony 1 - 11,
ISSN: 0166-218X
Język:
angielski
Rok wydania:
2019
Opis bibliograficzny:
Lewoń R., Małafiejska A., Małafiejski M., Wereszko K.: Global edge alliances in graphs// DISCRETE APPLIED MATHEMATICS. -, (2019), s.1-11
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2018.09.002

wyświetlono 1 razy

Publikacje, które mogą cię zainteresować

Meta Tagi