Informacja

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

Wyszukujesz frazę "connected domination" wg kryterium: Temat


Wyświetlanie 1-15 z 15
Tytuł:
Weakly connected domination subdivision numbers
Autorzy:
Raczek, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/743529.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
weakly connected domination number
weakly connected domination subdivision number
Opis:
A set D of vertices in a graph G = (V,E) is a weakly connected dominating set of G if D is dominating in G and the subgraph weakly induced by D is connected. The weakly connected domination number of G is the minimum cardinality of a weakly connected dominating set of G. The weakly connected domination subdivision number of a connected graph G is the minimum number of edges that must be subdivided (where each egde can be subdivided at most once) in order to increase the weakly connected domination number. We study the weakly connected domination subdivision numbers of some families of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 109-119
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Connected Domination Critical Graphs with Cut Vertices
Autorzy:
Kaemawichanurat, Pawaton
Ananchuen, Nawarat
Powiązania:
https://bibliotekanauki.pl/articles/31348137.pdf
Data publikacji:
2020-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connected domination
critical
Opis:
A graph G is said to be k-γc-critical if the connected domination number of G, γc(G), is k and γc(G + uv) < k for any pair of non-adjacent vertices u and v of G. Let G be a k-γc-critical graph and ζ (G) the number of cut vertices of G. It was proved, in [1, 6], that, for 3 ≤ k ≤ 4, every k-γc-critical graph satisfies ζ (G) ≤ k − 2. In this paper, we generalize that every k-γc-critical graph satisfies ζ (G) ≤ k − 2 for all k ≥ 5. We also characterize all k-γc-critical graphs when ζ(G) is achieving the upper bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 4; 1035-1055
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination numbers in graphs with removed edge or set of edges
Autorzy:
Lemańska, Magdalena
Powiązania:
https://bibliotekanauki.pl/articles/744295.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
connected domination number
weakly connected domination number
edge removal
Opis:
It is known that the removal of an edge from a graph G cannot decrease a domination number γ(G) and can increase it by at most one. Thus we can write that γ(G) ≤ γ(G-e) ≤ γ(G)+1 when an arbitrary edge e is removed. Here we present similar inequalities for the weakly connected domination number $γ_w$ and the connected domination number $γ_c$, i.e., we show that $γ_w(G) ≤ γ_w(G-e) ≤ γ_w(G)+1$ and $γ_c(G) ≤ γ_c(G-e) ≤ γ_c(G) + 2$ if G and G-e are connected. Additionally we show that $γ_w(G) ≤ γ_w(G-Eₚ) ≤ γ_w(G) + p - 1$ and $γ_c(G) ≤ γ_c(G -Eₚ) ≤ γ_c(G) + 2p - 2$ if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected subgraph of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 51-56
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total connected domination game
Autorzy:
Bujtás, Csilla
Henning, Michael A.
Iršič, Vesna
Klavžar, Sandi
Powiązania:
https://bibliotekanauki.pl/articles/2050904.pdf
Data publikacji:
2021
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
connected domination game
total connected domination game
graph product
tree
Opis:
The (total) connected domination game on a graph $G$ is played by two players, Dominator and Staller, according to the standard (total) domination game with the additional requirement that at each stage of the game the selected vertices induce a connected subgraph of $G$. If Dominator starts the game and both players play optimally, then the number of vertices selected during the game is the (total) connected game domination number $(\gamma_{tcg}(G))(\gamma_{cg(G)})$ of $G$. We show that $\gamma_{tcg}(G) \in \{\gamma_{cg}(G), \gamma_{cg}(G)+1, \gamma_{cg}(G)+2\}$, and consequently define $G$ as Class $i$ if $\gamma_{tcg}(G) = \gamma_{cg}(G)+i$ for $i \in \{0, 1, 2\}$. A large family of Class 0 graphs is constructed which contains all connected Cartesian product graphs and connected direct product graphs with minimum degree at least 2. We show that no tree is Class 2 and characterize Class 1 trees. We provide an infinite family of Class 2 bipartite graphs.
Źródło:
Opuscula Mathematica; 2021, 41, 4; 453-464
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Perfect connected-dominant graphs
Autorzy:
Zverovich, Igor
Powiązania:
https://bibliotekanauki.pl/articles/743393.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Connected domination
perfect connected-dominant graph
Opis:
If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number $γ_c(G)$ of G. A graph G is called a perfect connected-dominant graph if $γ(H) = γ_c(H)$ for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 159-162
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total outer-connected domination in trees
Autorzy:
Cyman, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/744028.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total outer-connected domination number
domination number
Opis:
Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by $γ_{tc}(G)$, is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then $γ_{tc}(T) ≥ ⎡2n/3⎤$. Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 377-383
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination Parameters of a Graph and its Complement
Autorzy:
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/31342430.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
complement
total domination
connected domination
clique domination
restrained domination
Opis:
A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 203-215
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Weakly connected domination critical graphs
Autorzy:
Lemańska, M.
Patyk, A.
Powiązania:
https://bibliotekanauki.pl/articles/255051.pdf
Data publikacji:
2008
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
weakly connected domination number
tree
critical graphs
Opis:
A dominating set D ⊂ V(G) is a weakly connected dominating set in G if the subgraph G[D]w = (NG[D], Ew) weakly induced by D is connected, where Ew is the set of all edges with at least one vertex in D. The weakly connected domination number ϒw(G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. The graph is said to be weakly connected domination critical (ϒw-critical) if for each u, v ∈ V(G) with v not adjacent to u, ϒw(G + vu) < ϒw(G). Further, G is k- ϒw-critical if ϒw(G) = k and for each edge e ∉ E(G), ϒw(G + e) < k. In this paper we consider weakly connected domination critical graphs and give some properties of 3-ϒw,-critical graphs.
Źródło:
Opuscula Mathematica; 2008, 28, 3; 325-330
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graph domination in distance two
Autorzy:
Bacsó, Gábor
Tálos, Attila
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/744316.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
dominating set
connected domination
distance domination
forbidden induced subgraph
Opis:
Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $Dom Dom _u = Dom₂ _u$ holds for $_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, ₂ = {K₁} and ₃ = {all complete graphs}.) Some negative examples are also given.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 121-128
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs without induced P₅ and C₅
Autorzy:
Bacsó, Gabor
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/744580.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph domination
connected domination
complete subgraph
forbidden induced subgraph
characterization
Opis:
Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 503-507
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Neighbourhood total domination in graphs
Autorzy:
Arumugam, S.
Sivagnanam, C.
Powiązania:
https://bibliotekanauki.pl/articles/254824.pdf
Data publikacji:
2011
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
neighbourhood total domination
total domination
connected domination
paired domination
neighbourhood total domatic number
Opis:
Let G = (V, E) be a graph without isolated vertices. A dominating set S of G is called a neighbourhood total dominating set (ntd-set) if the induced subgraph ⟨ N(S) ⟩ has no isolated vertices. The minimum cardinality of a ntd-set of G is called the neighbourhood total domination number of G and is denoted by ϒnt(G). The maximum order of a partition of V into ntd-sets is called the neighbourhood total domatic number of G and is denoted by dnt(G). In this paper we initiate a study of these parameters.
Źródło:
Opuscula Mathematica; 2011, 31, 4; 519-531
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Weakly convex and convex domination numbers
Autorzy:
Lemańska, M.
Powiązania:
https://bibliotekanauki.pl/articles/2050775.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
dominating set
connected domination number
distance
isometric set
convex set
Opis:
Two new domination parameters for a connected graph G: the weakly convex domination number of G and the convex domination number of G are introduced. Relations between these parameters and the other domination parameters are derived. In particular, we study for which cubic graphs the convex domination number equals the connected domination number.
Źródło:
Opuscula Mathematica; 2004, 24, 2; 181-188
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An application of the selected graph theory domination concepts to transportation networks modelling
Autorzy:
Guze, S.
Powiązania:
https://bibliotekanauki.pl/articles/135168.pdf
Data publikacji:
2017
Wydawca:
Akademia Morska w Szczecinie. Wydawnictwo AMSz
Tematy:
domination
edge-subdivision
connected bondage number
bondage-connected number
transportation network
modelling
Opis:
One of the possibilities when modelling a transport network is to use a graph with vertices and edges. They represent the nodes and arcs of such a network respectively. There are dozens of parameters or characteristics that we can describe in graphs, including the different types of domination number and the problems related to it. The main aim of this paper has been to show the possibilities of the application of the selected domination-oriented concepts to modelling and improving the transportation and/or logistics networks. Firstly, the basic description of domination in graph theory has been introduced. The edge-subdivision and bondage number notations and their implementations to the transportation network description and modelling were then proposed. Furthermore, the possible usage of distinguishing concepts in an exemplary academic transportation network has been shown. Finally, the conclusions and future directions of the work have been presented.
Źródło:
Zeszyty Naukowe Akademii Morskiej w Szczecinie; 2017, 52 (124); 97-102
1733-8670
2392-0378
Pojawia się w:
Zeszyty Naukowe Akademii Morskiej w Szczecinie
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Connected global offensive k-alliances in graphs
Autorzy:
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743583.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
alliances in graphs
connected global offensive k-alliance
global offensive k-alliance
domination
Opis:
We consider finite graphs G with vertex set V(G). For a subset S ⊆ V(G), we define by G[S] the subgraph induced by S. By n(G) = |V(G) | and δ(G) we denote the order and the minimum degree of G, respectively. Let k be a positive integer. A subset S ⊆ V(G) is a connected global offensive k-alliance of the connected graph G, if G[S] is connected and |N(v) ∩ S | ≥ |N(v) -S | + k for every vertex v ∈ V(G) -S, where N(v) is the neighborhood of v. The connected global offensive k-alliance number $γₒ^{k,c}(G)$ is the minimum cardinality of a connected global offensive k-alliance in G.
In this paper we characterize connected graphs G with $γₒ^{k,c}(G) = n(G)$. In the case that δ(G) ≥ k ≥ 2, we also characterize the family of connected graphs G with $γₒ^{k,c}(G) = n(G) - 1$. Furthermore, we present different tight bounds of $γₒ^{k,c}(G)$.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 4; 699-707
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Review of Methods and Algorithms for Modelling Transportation Networks Based on Graph Theory
Przegląd metod i algorytmów modelowania sieci transportowych opartych na teorii grafów
Autorzy:
Guze, S.
Powiązania:
https://bibliotekanauki.pl/articles/341823.pdf
Data publikacji:
2018
Wydawca:
Uniwersytet Morski w Gdyni. Wydawnictwo Uniwersytetu Morskiego w Gdyni
Tematy:
knapsack problem
domination number
bondage-connected number
MST
maximal flow
transportation network
vulnerability
problem plecakowy
liczba dominowania
liczba zniewolenia spójnego
maksymalny przepływ
sieć transportowa
wrażliwość sieci
Opis:
One of the best ways of modelling a transport network is to use a graph with vertices and edges. They represent nodes and arcs of such network respectively. Graph theory gives dozens of parameters or characteristics, including a connectivity, spanning trees or the different types of domination number and problems related to it. The main aim of the paper is to show graph theory methods and algorithms helpful in modelling and optimization of a transportation network. Firstly, the descriptions of basic notations in graph theory are introduced. Next, the concepts of domination, bondage number, edge-subdivision and their implementations to the transportation network description and modeling are proposed. Moreover, the algorithms for finding spanning tree or maximal flow in networks are presented. Finally, the possible usage of distinguishing concepts to exemplary transportation network is shown. The conclusions and future directions of work are presented at the end of the paper.
Jednym z najlepszych sposobów modelowania sieci transportowej jest użycie grafu z wierzchołkami i krawędziami. Reprezentują one odpowiednio węzły i łuki takiej sieci. Teoria grafów daje możliwość użycia dziesiątek parametrów lub charakterystyk, w tym spójności, drzew spinających lub różnych typów liczb dominowania i związanych z tym problemów. Głównym celem artykułu jest przedstawienie metod i algorytmów teorii grafów pomocnych w modelowaniu i optymalizacji sieci transportowej. Po pierwsze, wprowadzono opisy podstawowych pojęć w teorii grafów. Następnie zaprezentowano koncepcje dominowania, liczby zniewolenia czy podziału krawędzi grafu oraz ich implementacji do opisu i modelowania sieci transportowej. Ponadto przedstawiono algorytmy do wyszukiwania drzewa opinającego i maksymalnego przepływu w sieciach. Wreszcie pokazano możliwe sposoby wykorzystania wyróżnionych koncepcji do przykładu sieci transportowej. Na zakończenia przedstawiono wnioski i przyszłe kierunki prac.
Źródło:
Zeszyty Naukowe Akademii Morskiej w Gdyni; 2018, 107; 25-39
1644-1818
2451-2486
Pojawia się w:
Zeszyty Naukowe Akademii Morskiej w Gdyni
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-15 z 15

    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