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ę "Nordhaus-Gaddum bounds" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-4 z 4
    Tytuł:
    Triameter of Graphs
    Autorzy:
    Das, Angsuman
    Powiązania:
    https://bibliotekanauki.pl/articles/32083897.pdf
    Data publikacji:
    2021-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    distance
    radio k -coloring
    Nordhaus-Gaddum bounds
    Opis:
    In this paper, we study a new distance parameter triameter of a connected graph G, which is defined as max{d(u; v)+d(v;w)+d(u;w) : u; v;w ∈ V} and is denoted by tr(G). We find various upper and lower bounds on tr(G) in terms of order, girth, domination parameters etc., and characterize the graphs attaining those bounds. In the process, we provide some lower bounds of (connected, total) domination numbers of a connected graph in terms of its triameter. The lower bound on total domination number was proved earlier by Henning and Yeo. We provide a shorter proof of that. Moreover, we prove Nordhaus-Gaddum type bounds on tr(G) and find tr(G) for some specific family of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 2; 601-616
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    More on the Rainbow Disconnection in Graphs
    Autorzy:
    Bai, Xuqing
    Chang, Renying
    Huang, Zhong
    Li, Xueliang
    Powiązania:
    https://bibliotekanauki.pl/articles/32222544.pdf
    Data publikacji:
    2022-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-coloring
    edge-connectivity
    rainbow disconnection coloring (number)
    Erdős-Gallai type problem
    Nordhaus-Gaddum type bounds
    complexity
    NP-hard (complete)
    Opis:
    Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1185-1204
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some Sharp Bounds on the Negative Decision Number of Graphs
    Autorzy:
    Liang, Hongyu
    Powiązania:
    https://bibliotekanauki.pl/articles/29785048.pdf
    Data publikacji:
    2013-09-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    negative decision number
    bad function
    sharp upper bounds
    Nordhaus-Gaddum results
    Opis:
    Let $G = (V,E)$ be a graph. A function $f : V → {-1,1}$ is called a bad function of $G$ if $∑_{u∈N_G(v)} f(u) ≤ 1$ for all $v ∈ V$ where $N_G(v)$ denotes the set of neighbors of $v$ in $G$. The negative decision number of $G$, introduced in [12], is the maximum value of $∑_{v∈V} f(v)$ taken over all bad functions of $G$. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality for the negative decision number.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 4; 649-656
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Bounds on the Signed 2-Independence Number in Graphs
    Autorzy:
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/29794119.pdf
    Data publikacji:
    2013-09-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    bounds
    signed 2-independence function
    signed 2-independence number
    Nordhaus-Gaddum type result
    Opis:
    Let $G$ be a finite and simple graph with vertex set $V (G)$, and let $f V (G) → {−1, 1}$ be a two-valued function. If $∑_{x∈N|v|} f(x) ≤ 1$ for each $v ∈ V (G)$, where $N[v]$ is the closed neighborhood of $v$, then $f$ is a signed 2-independence function on $G$. The weight of a signed 2-independence function $f$ is $w(f) = ∑_{v∈V (G)} f(v)$. The maximum of weights $w(f)$, taken over all signed 2-independence functions $f$ on $G$, is the signed 2-independence number $α_s^2(G)$ of $G$. In this work, we mainly present upper bounds on $α_s^2(G)$, as for example $α_s^2(G) ≤ n−2 [∆ (G)//2]$, and we prove the Nordhaus-Gaddum type inequality $α_s^2 (G) + α_s^2(G) ≤ n+1$, where $n$ is the order and $∆ (G)$ is the maximum degree of the graph $G$. Some of our theorems improve well-known results on the signed 2-independence number.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 4; 709-715
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-4 z 4

      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