DIKUL - logo
(UL)
  • Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
    Chiarelli, Nina ; Milanič, Martin, 1980-
    A total dominating set in a graph is a set of vertices such that every vertex of the graph has a neighbor in the set. We introduce and study graphs that admit non-negative real weights associated to ... their vertices such that a set of vertices is a total dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We show that these graphs, which we call total domishold graphs, form a non-hereditary class of graphs properly containing the classes of threshold graphs and the complements of domishold graphs, and are closely related to threshold Boolean functions and threshold hypergraphs. We present a polynomial time recognition algorithm of total domishold graphs, and characterize graphs in which the above property holds in a hereditary sense. Our characterization is obtained by studying a new family of hypergraphs, defined similarly as the Sperner hypergraphs, which may be of independent interest.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 179, 2014, str. 1-12)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2014
    Jezik - angleški
    COBISS.SI-ID - 1537025220

    Povezava(-e):

    http://dx.doi.org/10.1016/j.dam.2014.09.001

Vnos na polico