Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "Rall, Douglas" wg kryterium: Wszystkie pola

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-9 z 9
    Tytuł:
    Total domination in categorical products of graphs
    Autorzy:
    Rall, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/744287.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    categorical product
    open packing
    total domination
    submultiplicative
    supermultiplicative
    Opis:
    Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination number on the categorical product of graphs. In particular, we show that the total domination number of the categorical product of a nontrivial tree and any graph without isolated vertices is equal to the product of their total domination numbers. In the process we establish a packing and covering equality for trees analogous to the well-known result of Meir and Moon. Specifically, we prove equality between the total domination number and the open packing number of any tree of order at least two.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 35-44
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On dominating the Cartesian product of a graph and K₂
    Autorzy:
    Hartnell, Bert
    Rall, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/744535.pdf
    Data publikacji:
    2004
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    2-packing, Cartesian product
    Opis:
    In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated further.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2004, 24, 3; 389-402
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Vizings conjecture and the one-half argument
    Autorzy:
    Hartnell, Bert
    Rall, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/972044.pdf
    Data publikacji:
    1995
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination number
    Cartesian product
    Vizing's conjecture
    clique
    Opis:
    The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as well as the collection of graphs considered by Barcalkin and German in [1]. A crucial part of the proof depends on the well-known fact that the domination number of any connected graph of order at least two is no more than half its order.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1995, 15, 2; 205-216
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Improving some bounds for dominating Cartesian products
    Autorzy:
    Hartnell, Bert
    Rall, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/743158.pdf
    Data publikacji:
    2003
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination number
    Cartesian product
    Vizing's conjecture
    2-packing
    Opis:
    The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds for dominating the Cartesian product of any two graphs. We show how it is possible to improve some of these bounds by imposing conditions on both graphs. For example, we establish a new lower bound for the domination number of T T, when T is a tree, and we improve an upper bound of Vizing in the case when one of the graphs has k > 1 dominating sets which cover the vertex set and the other has a dominating set which partitions in a certain way.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2003, 23, 2; 261-272
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Associative graph products and their independence, domination and coloring numbers
    Autorzy:
    Nowakowski, Richard
    Rall, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/972041.pdf
    Data publikacji:
    1996
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph products
    independence
    domination
    irredundance
    coloring
    Opis:
    Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity of a graph and Hedetniemi's coloring conjecture.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1996, 16, 1; 53-79
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Well-Covered Direct Products
    Autorzy:
    Kuenzel, Kirsti
    Rall, Douglas F.
    Powiązania:
    https://bibliotekanauki.pl/articles/32315158.pdf
    Data publikacji:
    2022-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    well-covered graph
    direct product of graphs
    isolatable vertex
    Opis:
    A graph G is well-covered if all maximal independent sets of G have the same cardinality. In 1992 Topp and Volkmann investigated the structure of well-covered graphs that have nontrivial factorizations with respect to some of the standard graph products. In particular, they showed that both factors of a well-covered direct product are also well-covered and proved that the direct product of two complete graphs (respectively, two cycles) is well-covered precisely when they have the same order (respectively, both have order 3 or 4). Furthermore, they proved that the direct product of two well-covered graphs with independence number one-half their order is well-covered. We initiate a characterization of nontrivial connected well-covered graphs G and H, whose independence numbers are strictly less than one-half their orders, such that their direct product G × H is well-covered. In particular, we show that in this case both G and H have girth 3 and we present several infinite families of such well-covered direct products. Moreover, we show that if G is a factor of any well-covered direct product, then G is a complete graph unless it is possible to create an isolated vertex by removing the closed neighborhood of some independent set of vertices in G.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 2; 627-640
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Graphs with Disjoint Dominating and 2-Dominating Sets
    Autorzy:
    Henning, Michael A.
    Rall, Douglas F.
    Powiązania:
    https://bibliotekanauki.pl/articles/30146715.pdf
    Data publikacji:
    2013-03-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    2-domination
    vertex partition
    Opis:
    A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 1; 139-146
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Survey on Packing Colorings
    Autorzy:
    Brešar, Boštjan
    Ferme, Jasmina
    Klavžar, Sandi
    Rall, Douglas F.
    Powiązania:
    https://bibliotekanauki.pl/articles/31804166.pdf
    Data publikacji:
    2020-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    packing coloring
    packing chromatic number
    subcubic graph
    S -packing chromatic number
    computational complexity
    Opis:
    If S = (a1, a2, . . .) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1, X2, . . . such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V (G) = X1 ∪ ∪ Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai = i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and its generalization, the S-packing coloring. We also list several conjectures and open problems.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 4; 923-970
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A New Framework to Approach Vizing’s Conjecture
    Autorzy:
    Brešar, Boštjan
    Hartnell, Bert L.
    Henning, Michael A.
    Kuenzel, Kirsti
    Rall, Douglas F.
    Powiązania:
    https://bibliotekanauki.pl/articles/32222699.pdf
    Data publikacji:
    2021-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Cartesian product
    total domination
    Vizing’s conjecture
    Clark and Suen bound
    Opis:
    We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing’s conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: $ \gamma (X \square Y) \ge \max \{\frac{1}{2} \gamma (X) \gamma_t (Y), \frac{1}{2} \gamma_t (X) \gamma (Y) \} $, where $ \gamma $ stands for the domination number, $ \gamma_t $ is the total domination number, and $ X \square Y $ is the Cartesian product of graphs $X$ and $Y$.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 3; 749-762
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-9 z 9

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies