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ę "DOMINATION" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-100 z 328
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ł:
Total Domination Versus Paired-Domination in Regular Graphs
Autorzy:
Cyman, Joanna
Dettlaff, Magda
Henning, Michael A.
Lemańska, Magdalena
Raczek, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/31342314.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
paired-domination
Opis:
A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, γt(G), and the paired-domination number, γpr(G), respectively. For k ≥ 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447] that γpr(G)/γt(G) ≤ (2k)/(k+1). In the special case when k = 2, we observe that γpr(G)/γt(G) ≤ 4/3, with equality if and only if G ≅ C5. When k = 3, we show that γpr(G)/γt(G) ≤ 3/2, with equality if and only if G is the Petersen graph. More generally for k ≥ 2, if G has girth at least 5 and satisfies γpr(G)/γt(G) = (2k)/(k + 1), then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k ≥ 2 and k ≠ 57, if G has girth at least 5, then γpr(G)/γt(G) ≤ (2k)/(k +1), with equality if and only if k = 2 and G ≅ C5 or k = 3 and G is the Petersen graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 573-586
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertices belonging to all or to no minimum locating dominating sets of trees
Autorzy:
Blidia, M.
Lounes, R.
Powiązania:
https://bibliotekanauki.pl/articles/255510.pdf
Data publikacji:
2009
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination
locating domination
Opis:
A set D of vertices in a graph G is a locating-dominating set if for every two vertices u, v of G \ D the sets N(u) ∩ D and N (v) ∩ D are non-empty and different. In this paper, we characterize vertices that are in all or in no minimum locating dominating sets in trees. The characterization guarantees that the γL-excellent tree can be recognized in a polynomial time.
Źródło:
Opuscula Mathematica; 2009, 29, 1; 5-14
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with equal domination and certified domination numbers
Autorzy:
Dettlaff, Magda
Lemańska, Magdalena
Miotk, Mateusz
Topp, Jerzy
Ziemann, Radosław
Żyliński, Paweł
Powiązania:
https://bibliotekanauki.pl/articles/255932.pdf
Data publikacji:
2019
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination
certified domination
Opis:
A set D of vertices of a graph G = (VG, EG) is a dominating set of G if every vertex in VG — D is adjacent to at least one vertex in D. The domination number (upper domination number, respectively) of G, denoted by [formula], respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of G. A subset D ⊆ VG is called a certified dominating set of G if D is a dominating set of G and every vertex in D has either zero or at least two neighbors in VG — D. The cardinality of a smallest (largest minimal, respectively) certified dominating set of G is called the certified (upper certified, respectively) domination number of G and is denoted by [formula]), respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.
Źródło:
Opuscula Mathematica; 2019, 39, 6; 815-827
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Trees with unique minimum total dominating sets
Autorzy:
Haynes, Teresa
Henning, Michael
Powiązania:
https://bibliotekanauki.pl/articles/743354.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
Opis:
A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 2; 233-246
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets
Autorzy:
Henning, Michael A.
Topp, Jerzy
Powiązania:
https://bibliotekanauki.pl/articles/32222686.pdf
Data publikacji:
2021-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
paired-domination
Opis:
A subset D ⊆ VG is a dominating set of G if every vertex in VG – D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP -graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP -graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459–467; J. Comb. Optim. 22 (2011) 217–234]. In this paper, we provide conditions which ensure that a graph is a DPDP -graph. In particular, we characterize the minimal DPDP -graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 827-847
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some remarks on α-domination
Autorzy:
Dahme, Franz
Rautenbach, Dieter
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/744557.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
α-domination
domination
Opis:
Let α ∈ (0,1) and let $G = (V_G,E_G$) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D ⊆ V_G$ is called an α-dominating set of G, if $|N_G(u) ∩ D| ≥ αd_G(u)$ for all $u ∈ V_G∖D$. We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 423-430
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A remark on the (2,2)-domination number
Autorzy:
Korneffel, Torsten
Meierling, Dirk
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743033.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
distance domination number
p-domination number
Opis:
A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k,p}(G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k,p}(G) ≤ (p/(p+k))n(G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture for all integers k and p for the case that p is a multiple of k. In this paper we show that $γ_{2,2}(G) ≤ (n(G)+1)/2$ for all connected graphs G and characterize all connected graphs with $γ_{2,2} = (n+1)/2$. This means that for k = p = 2 we characterize all connected graphs for which the conjecture is true without the precondition that δ₂ ≥ 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 2; 361-366
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterization of block graphs with equal 2-domination number and domination number plus one
Autorzy:
Hansberg, Adriana
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743677.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
2-domination
multiple domination
block graph
Opis:
Let G be a simple graph, and let p be a positive integer. A subset D ⊆ V(G) is a p-dominating set of the graph G, if every vertex v ∈ V(G)-D is adjacent with at least p vertices of D. The p-domination number γₚ(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ₁(G) is the usual domination number γ(G).
If G is a nontrivial connected block graph, then we show that γ₂(G) ≥ γ(G)+1, and we characterize all connected block graphs with γ₂(G) = γ(G)+1. Our results generalize those of Volkmann [12] for trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 93-103
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Domination in Generalized Prisms and a New Domination Invariant
Autorzy:
Tepeh, Aleksandra
Powiązania:
https://bibliotekanauki.pl/articles/32222717.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
k -rainbow total domination
total domination
Opis:
In this paper we complement recent studies on the total domination of prisms by considering generalized prisms, i.e., Cartesian products of an arbitrary graph and a complete graph. By introducing a new domination invariant on a graph G, called the k-rainbow total domination number and denoted by γkrt(G), it is shown that the problem of finding the total domination number of a generalized prism G □ Kk is equivalent to an optimization problem of assigning subsets of {1, 2, . . ., k} to vertices of G. Various properties of the new domination invariant are presented, including, inter alia, that γkrt(G) = n for a nontrivial graph G of order n as soon as k ≥ 2Δ(G). To prove the mentioned result as well as the closed formulas for the k-rainbow total domination number of paths and cycles for every k, a new weight-redistribution method is introduced, which serves as an efficient tool for establishing a lower bound for a domination invariant.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1165-1178
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Complexity of Reinforcement in Graphs
Autorzy:
Rad, Nader Jafari
Powiązania:
https://bibliotekanauki.pl/articles/31340751.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
total restrained domination
p- domination
k-rainbow domination
reinforcement
NP-hard
Opis:
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 877-887
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Paired-domination
Autorzy:
Fitzpatrick, S.
Hartnell, B.
Powiązania:
https://bibliotekanauki.pl/articles/744199.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
paired-domination
matching
Opis:
We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of girth seven or more of this type.
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 1; 63-72
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs With Large Semipaired Domination Number
Autorzy:
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/31343332.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
paired-domination
semipaired domination
Opis:
Let $G$ be a graph with vertex set $V$ and no isolated vertices. A subset $ S \subseteq V $ is a semipaired dominating set of $G$ if every vertex in $ V \backslash S $ is adjacent to a vertex in $S$ and $S$ can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number $ \gamma_{pr2}(G) $ is the minimum cardinality of a semipaired dominating set of $G$. We show that if $G$ is a connected graph $G$ of order $ n \ge 3 $, then \( \gamma_{pr2} (G) \le \tfrac{2}{3} n \), and we characterize the extremal graphs achieving equality in the bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 659-671
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on perfect k-domination in trees: an algorithmic approach
Autorzy:
Chaluvaraju, B.
Vidya, K. A.
Powiązania:
https://bibliotekanauki.pl/articles/255985.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
k-domination
perfect domination
perfect k-domination
Opis:
Let k be a positive integer and G = (V, E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G if every vertex v of G not in D is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k -dominating set of G is the perfect k-domination number γkp (G ). In this paper, a sharp bound for γkp (T) is obtained where T is a tree.
Źródło:
Opuscula Mathematica; 2012, 32, 4; 707-714
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on domination parameters in random graphs
Autorzy:
Bonato, Anthony
Wang, Changping
Powiązania:
https://bibliotekanauki.pl/articles/743019.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
random graphs
independent domination
total domination
Opis:
Domination parameters in random graphs G(n,p), where p is a fixed real number in (0,1), are investigated. We show that with probability tending to 1 as n → ∞, the total and independent domination numbers concentrate on the domination number of G(n,p).
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 2; 335-343
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A New Upper Bound for the Perfect Italian Domination Number of a Tree
Autorzy:
Nazari-Moghaddam, Sakineh
Chellali, Mustapha
Powiązania:
https://bibliotekanauki.pl/articles/32304138.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Italian domination
Roman domination
perfect Italian domination
Opis:
A perfect Italian dominating function (PIDF) on a graph $G$ is a function $ f : V (G) \rightarrow \{ 0, 1, 2 \} $ satisfying the condition that for every vertex u with $f(u) = 0$, the total weight of $f$ assigned to the neighbors of $u$ is exactly two. The weight of a PIDF is the sum of its functions values over all vertices. The perfect Italian domination number of $G$, denoted $ \gamma_I^p (G) $, is the minimum weight of a PIDF of $G$. In this paper, we show that for every tree $T$ of order $ n \ge 3 $, with $ \mathcal{l} (T) $ leaves and $s(T)$ support vertices, \( \gamma_I^p (T) \ge \tfrac {4n- \mathscr{l}(T) + 2s (T) - 1}{5} \), improving a previous bound given by T.W. Haynes and M.A. Henning in [Perfect Italian domination in trees, Discrete Appl. Math. 260 (2019) 164–177].
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 1005-1022
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A characterization of (γₜ,γ₂)-trees
Autorzy:
Lu, You
Hou, Xinmin
Xu, Jun-Ming
Li, Ning
Powiązania:
https://bibliotekanauki.pl/articles/744036.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
2-domination
(λ,μ)-tree
Opis:
Let γₜ(G) and γ₂(G) be the total domination number and the 2-domination number of a graph G, respectively. It has been shown that: γₜ(T) ≤ γ₂(T) for any tree T. In this paper, we provide a constructive characterization of those trees with equal total domination number and 2-domination number.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 425-435
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Full domination in graphs
Autorzy:
Brigham, Robert
Chartrand, Gary
Dutton, Ronald
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/743419.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
full domination
full star domination
full closed domination
full open domination
Opis:
For each vertex v in a graph G, let there be associated a subgraph $H_v$ of G. The vertex v is said to dominate $H_v$ as well as dominate each vertex and edge of $H_v$. A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number $γ_{FH}(G)$. A full dominating set of G of cardinality $γ_{FH}(G)$ is called a $γ_{FH}$-set of G. We study three types of full domination in graphs: full star domination, where $H_v$ is the maximum star centered at v, full closed domination, where $H_v$ is the subgraph induced by the closed neighborhood of v, and full open domination, where $H_v$ is the subgraph induced by the open neighborhood of v.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 1; 43-62
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Total k-Domination in Graphs
Autorzy:
Bermudo, Sergio
Hernández-Gómez, Juan C.
Sigarreta, José M.
Powiązania:
https://bibliotekanauki.pl/articles/31342422.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k -domination
total k -domination
k -tuple domination
k -tuple total domination
Opis:
Let G=(V, E) be a graph; a set S ⊆ V is a total k-dominating set if every vertex v ∈ V has at least k neighbors in S. The total k-domination number γkt(G) is the minimum cardinality among all total k-dominating sets. In this paper we obtain several tight bounds for the total k-domination number of a graph. In particular, we investigate the relationship between the total k-domination number of a graph and the order, the size, the girth, the minimum and maximum degree, the diameter, and other domination parameters of the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 301-317
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Protection of Lexicographic Product Graphs
Autorzy:
Klein, Douglas J.
Rodríguez-Velázquez, Juan A.
Powiązania:
https://bibliotekanauki.pl/articles/32361746.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
lexicographic product
weak Roman domination
secure domination
total domination
double total domination
Opis:
In this paper, we study the weak Roman domination number and the secure domination number of lexicographic product graphs. In particular, we show that these two parameters coincide for almost all lexicographic product graphs. Furthermore, we obtain tight bounds and closed formulas for these parameters.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 139-158
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on a relation between the weak and strong domination numbers of a graph
Autorzy:
Boutrig, R.
Chellali, M.
Powiązania:
https://bibliotekanauki.pl/articles/255983.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
weak domination
strong domination
Opis:
In a graph G = (V, E) a vertex is said to dominate itself and all its neighbors. A set D ⊆ V is a weak (strong, respectively) dominating set of G if every vertex v ∈ V - S is adjacent to a vertex u ∈ D such that dG(v) ≥ dG(u) (dG(v) ≤ dG(u), respectively). The weak (strong, respectively) domination number of G, denoted by ϒw(G) (ϒs(G), respectively), is the minimum cardinality of a weak (strong, respectively) dominating set of G. In this note we show that if G is a connected graph of order n ≥ 3, then ϒw(G) + tϒs(G) ≤ n, where t = 3/(Δ+1) if G is an arbitrary graph, t = 3/5 if G is a block graph, and t = 2/3 if G is a claw free graph.
Źródło:
Opuscula Mathematica; 2012, 32, 2; 235-238
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Efficient (j,k)-domination
Autorzy:
Rubalcaba, Robert
Slater, Peter
Powiązania:
https://bibliotekanauki.pl/articles/743411.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
efficient domination
multiple domination
Opis:
A dominating set S of a graph G is called efficient if |N[v]∩ S| = 1 for every vertex v ∈ V(G). That is, a dominating set S is efficient if and only if every vertex is dominated exactly once. In this paper, we investigate efficient multiple domination. There are several types of multiple domination defined in the literature: k-tuple domination, {k}-domination, and k-domination. We investigate efficient versions of the first two as well as a new type of multiple domination.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 409-423
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree
Autorzy:
Henning, Michael A.
Marcon, Alister J.
Powiązania:
https://bibliotekanauki.pl/articles/31341173.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
semitotal domination
trees
Opis:
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G) ≤ γt2(G) ≤ γt(G). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 71-93
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some Progress on the Double Roman Domination in Graphs
Autorzy:
Rad, Nader Jafari
Rahbani, Hadi
Powiązania:
https://bibliotekanauki.pl/articles/31343730.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination
double Roman domination
Opis:
For a graph $ G = (V,E) $, a double Roman dominating function (or just DRDF) is a function $ f : V \rightarrow {0, 1, 2, 3} $ having the property that if $ f(v) = 0 $ for a vertex $ v $, then $ v $ has at least two neighbors assigned 2 under $ f $ or one neighbor assigned 3 under $ f $, and if $ f(v) = 1 $, then vertex $ v $ must have at least one neighbor $ w $ with $ f(w) \ge 2 $. The weight of a DRDF $f$ is the sum $f(V) = \Sigma_{ v \in V } f(v) $, and the minimum weight of a DRDF on $G$ is the double Roman domination number of $G$, denoted by $ \gamma_{dR} (G) $. In this paper, we derive sharp upper and lower bounds on $ \gamma_{dR} (G) + \gamma_{dR} ( \overline{G} ) $ and also $ \gamma_{dR} (G ) \gamma_{dR} ( \overline{G} ) $, where $ \overline{G} $ is the complement of graph $G$. We also show that the decision problem for the double Roman domination number is NP- complete even when restricted to bipartite graphs and chordal graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 41-53
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Roman {2}-Domination Problem in Graphs
Autorzy:
Chen, Hangdi
Lu, Changhong
Powiązania:
https://bibliotekanauki.pl/articles/32314051.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman {2}-domination
domination
algorithms
Opis:
For a graph G = (V, E), a Roman {2}-dominating function (R2DF) f : V → {0, 1, 2} has the property that for every vertex v ∈ V with f(v) = 0, either there exists a neighbor u ∈ N(v), with f(u) = 2, or at least two neighbors x, y ∈ N(v) having f(x) = f(y) = 1. The weight of an R2DF f is the sum f(V) = ∑v∈V f(v), and the minimum weight of an R2DF on G is the Roman {2}-domination number γ{R2}(G). An R2DF is independent if the set of vertices having positive function values is an independent set. The independent Roman {2}-domination number i{R2}(G) is the minimum weight of an independent Roman {2}-dominating function on G. In this paper, we show that the decision problem associated with γ{R2}(G) is NP-complete even when restricted to split graphs. We design a linear time algorithm for computing the value of i{R2}(T) in any tree T, which answers an open problem raised by Rahmouni and Chellali [Independent Roman {2}-domination in graphs, Discrete Appl. Math. 236 (2018) 408–414]. Moreover, we present a linear time algorithm for computing the value of γ{R2}(G) in any block graph G, which is a generalization of trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 641-660
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Spanning Trees with Disjoint Dominating and 2-Dominating Sets
Autorzy:
Miotk, Mateusz
Żyliński, Paweł
Powiązania:
https://bibliotekanauki.pl/articles/32361736.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
2-domination
spanning tree
Opis:
In this paper, we provide a structural characterization of graphs having a spanning tree with disjoint dominating and 2-dominating sets.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 299-308
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ł:
Total domination versus paired domination
Autorzy:
Schaudt, Oliver
Powiązania:
https://bibliotekanauki.pl/articles/743224.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
upper total domination
paired domination
upper paired domination
generalized claw-free graphs
Opis:
A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ.
In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_{1,r}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 2 - 2/(Δ+1), where Δ is the maximum degree. We also show for each r ≥ 2 that ${C₅,T_r}$-free graphs fulfill the sharp bound γₚ/γₜ ≤ 2 - 2/r, where $T_r$ is obtained from $K_{1,r}$ by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_{1,r}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 435-447
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The paired-domination and the upper paired-domination numbers of graphs
Autorzy:
Ulatowski, W.
Powiązania:
https://bibliotekanauki.pl/articles/255585.pdf
Data publikacji:
2015
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
paired-domination
paired-domination number
upper paired-domination number
Opis:
In this paper we continue the study of paired-domination in graphs. A paired-dominating set, abbreviated PDS, of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γP(G), is the minimum cardinality of a PDS of G. The upper paired-domination number of G, denoted by ΓP(G), is the maximum cardinality of a minimal PDS of G. Let G be a connected graph of order n ≥ 3. Haynes and Slater in [Paired-domination in graphs, Networks 32 (1998), 199-206], showed that γ P(G) ≤ n— 1 and they determine the extremal graphs G achieving this bound. In this paper we obtain analogous results for ΓP(G). Dorbec, Henning and McCoy in [Upper total domination versus upper paired-domination, Questiones Mathematicae 30 (2007), 1-12] determine Γp(Pn), instead in this paper we determine Γp(Cn). Moreover, we describe some families of graphs G for which the equality γP(G) = ΓP(G) holds.
Źródło:
Opuscula Mathematica; 2015, 35, 1; 127-135
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Secure domination and secure total domination in graphs
Autorzy:
Klostermeyer, William
Mynhardt, Christina
Powiązania:
https://bibliotekanauki.pl/articles/743322.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
secure domination
total domination
secure total domination
clique covering
Opis:
A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X-{x}) ∪ {u}$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_s(G)(γ_{st}(G))$. We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_{st}(G) ≤ γ_s(G)$. We also show that $γ_{st}(G)$ is at most twice the clique covering number of G, and less than three times the independence number. With the exception of the independence number bound, these bounds are sharp.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 2; 267-284
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination and leaf density in graphs
Autorzy:
Pedersen, Anders
Powiązania:
https://bibliotekanauki.pl/articles/744357.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bounds
domination number
leaves
partioned domination
total domination number
Opis:
The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are obtained for the total domination number and the partition domination number.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 251-259
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the (2,2)-domination number of trees
Autorzy:
Lu, You
Hou, Xinmin
Xu, Jun-Ming
Powiązania:
https://bibliotekanauki.pl/articles/744559.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
total domination number
(2,2)-domination number
Opis:
Let γ(G) and $γ_{2,2}(G)$ denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that $(2(γ(T)+1))/3 ≤ γ_{2,2}(T) ≤ 2γ(T)$. Moreover, we characterize all the trees achieving the equalities.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 2; 185-199
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Roman {2}-Dominating Functions in Graphs
Autorzy:
Ahangar, H. Abdollahzadeh
Chellali, M.
Sheikholeslami, S.M.
Valenzuela-Tripodoro, J.C.
Powiązania:
https://bibliotekanauki.pl/articles/32304142.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination
Roman {2}-domination
total Roman {2}-domination
Opis:
A Roman {2}-dominating function (R2F) is a function f : V → {0, 1, 2} with the property that for every vertex v ∈ V with f(v) = 0 there is a neighbor u of v with f(u) = 2, or there are two neighbors x, y of v with f(x) = f(y) = 1. A total Roman {2}-dominating function (TR2DF) is an R2F f such that the set of vertices with f(v) > 0 induce a subgraph with no isolated vertices. The weight of a TR2DF is the sum of its function values over all vertices, and the minimum weight of a TR2DF of G is the total Roman {2}-domination number γtR2(G). In this paper, we initiate the study of total Roman {2}-dominating functions, where properties are established. Moreover, we present various bounds on the total Roman {2}-domination number. We also show that the decision problem associated with γtR2(G) is possible to compute this parameter in linear time for bounded clique-width graphs (including trees).
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 937-958
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ł:
All graphs with paired-domination number two less than their order
Autorzy:
Ulatowski, W.
Powiązania:
https://bibliotekanauki.pl/articles/255220.pdf
Data publikacji:
2013
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
paired-domination
paired-domination number
Opis:
Let G = (V,E) be a graph with no isolated vertices. A set S ⊆ V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number Υρ (G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199–206] Haynes and Slater described graphs G with Υρ (G) = n and also graphs with Υρ (G) = n − 1. In this paper we show all graphs for which Υρ (G) = n − 2.
Źródło:
Opuscula Mathematica; 2013, 33, 4; 763-783
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On stratification and domination in graphs
Autorzy:
Gera, Ralucca
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/743948.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
stratified graph
F-domination
domination
Opis:
A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number $γ_F(G)$ is the minimum number of red vertices in an F-coloring of G. In this paper, we study F-domination, where F is a 2-stratified red-blue-blue path of order 3 rooted at a blue end-vertex. We present characterizations of connected graphs of order n with F-domination number n or 1 and establish several realization results on F-domination number and other domination parameters.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 249-272
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Exact double domination in graphs
Autorzy:
Chellali, Mustapha
Khelladi, Abdelkader
Maffray, Frédéric
Powiązania:
https://bibliotekanauki.pl/articles/744364.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
double domination
exact double domination
Opis:
In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive characterization of those trees that admit a doubly dominating set, and we establish a necessary and sufficient condition for the existence of an exact doubly dominating set in a connected cubic graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 291-302
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Relations between the domination parameters and the chromatic index of a graph
Autorzy:
Ulatowski, Włodzimierz
Powiązania:
https://bibliotekanauki.pl/articles/744471.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
domination parameters
chromatic index
Opis:
In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective equality holds.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 3; 615-627
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Relating 2-Rainbow Domination To Roman Domination
Autorzy:
Alvarado, José D.
Dantas, Simone
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/31341598.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
2-rainbow domination
Roman domination
Opis:
For a graph $G$, let $ \gamma_R (G)$ and $ \gamma_{r2} (G) $ denote the Roman domination number of $G$ and the 2-rainbow domination number of $G$, respectively. It is known that $ \gamma_{r2} (G) \le \gamma_R(G) \le 3/2 \gamma_{r2} (G) $. Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs $G$ for which $ \gamma_R (G) − \gamma_{r2} (G) = k $ for some integer $k$. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer $k$, the recognition of the connected $ K_4$-free graphs $G$ with $ \gamma_R (G) − \gamma_{r2} (G) = k $ is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs $ G $ such that $ \gamma_{r2} (H) = \gamma_R (H) $ for every induced subgraph $ H $ of $ G $, and collect several properties of the graphs $ G $ with $ \gamma_R (G) = 3/2 \gamma_{r2} (G) $.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 953-961
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hereditary Equality of Domination and Exponential Domination
Autorzy:
Henning, Michael A.
Jäger, Simon
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/31342424.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
exponential domination
hereditary class
Opis:
We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 275-285
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some results on total domination in direct products of graphs
Autorzy:
Dorbec, Paul
Gravier, Sylvain
Klavžar, Sandi
Spacapan, Simon
Powiązania:
https://bibliotekanauki.pl/articles/743885.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
direct product
total domination
k-tuple domination
open packing
domination
Opis:
Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 103-112
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination Subdivision and Domination Multisubdivision Numbers of Graphs
Autorzy:
Dettlaff, Magda
Raczek, Joanna
Topp, Jerzy
Powiązania:
https://bibliotekanauki.pl/articles/31343212.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
domination subdivision number
domination multisubdivision number
trees
computational complexity
Opis:
The domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T) ≤ 3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number of a nonempty graph G as a minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. We show that msd(G) ≤ 3 for any graph G. The domination subdivision number and the domination multisubdivision number of a graph are incomparable in general, but we show that for trees these two parameters are equal. We also determine the domination multisubdivision number for some classes of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 829-839
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Weak roman domination in graphs
Autorzy:
Roushini Leely Pushpam, P.
Malini Mai, T.
Powiązania:
https://bibliotekanauki.pl/articles/743835.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
weak Roman domination number
Opis:
Let G = (V,E) be a graph and f be a function f:V → {0,1,2}. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f': V → {0,1,2} defined by f'(u) = 1, f'(v) = f(v)-1 and f'(w) = f(w) if w ∈ V-{u,v}, has no undefended vertex. The weight of f is $w(f) = ∑_{v ∈ V}f(v)$. The weak Roman domination number, denoted by $γ_r(G)$, is the minimum weight of a WRDF in G. In this paper, we characterize the class of trees and split graphs for which $γ_r(G) = γ(G)$ and find $γ_r$-value for a caterpillar, a 2×n grid graph and a complete binary tree.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 161-170
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds On The Disjunctive Total Domination Number Of A Tree
Autorzy:
Henning, Michael A.
Naicker, Viroshan
Powiązania:
https://bibliotekanauki.pl/articles/31341124.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
disjunctive total domination
trees
Opis:
Let $G$ be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, $ \gamma_t(G) $. A set $S$ of vertices in $G$ is a disjunctive total dominating set of $G$ if every vertex is adjacent to a vertex of $S$ or has at least two vertices in $S$ at distance 2 from it. The disjunctive total domination number, $ \gamma_t^d (G) $, is the minimum cardinality of such a set. We observe that $ \gamma_t^d (G) \ge \gamma_t (G) $. A leaf of $G$ is a vertex of degree 1, while a support vertex of $G$ is a vertex adjacent to a leaf. We show that if $T$ is a tree of order $n$ with $ \mathcal{l} $ leaves and $s$ support vertices, then $ 2(n−\mathcal{l}+3) // 5 \le \gamma_t^d (T) \le (n+s−1)//2 $ and we characterize the families of trees which attain these bounds. For every tree $T$, we show have $ \gamma_t(T) // \gamma_t^d (T) <2 $ and this bound is asymptotically tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 153-171
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Block Graphs with Large Paired Domination Multisubdivision Number
Autorzy:
Mynhardt, Christina M.
Raczek, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/32083905.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
paired domination
domination subdivision number
domination multisubdivision number
block graph
Opis:
The paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 665-684
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Comparative Case Study on the Social Networking of the Second Year Under Graduate Mathematics Students of the M.D.T. Hindu College, Tirunelveli, Tamil Nadu, India Using Graph Theoretic Parameters
Autorzy:
Petchiammal, S.
Murugan, K.
Powiązania:
https://bibliotekanauki.pl/articles/1193041.pdf
Data publikacji:
2016
Wydawca:
Przedsiębiorstwo Wydawnictw Naukowych Darwin / Scientific Publishing House DARWIN
Tematy:
Sociometry
In-degree
out-degree
Domination
Digraphs
In-domination
Out-domination
Opis:
In this experimental case study, the social relationship of boys and girls studying second year under graduate Mathematics boys in The M.D.T Hindu College, Tirunelveli is compared using sociometry.
Źródło:
World Scientific News; 2016, 58; 1-14
2392-2192
Pojawia się w:
World Scientific News
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On domination multisubdivision number of unicyclic graphs
Autorzy:
Raczek, J.
Powiązania:
https://bibliotekanauki.pl/articles/255095.pdf
Data publikacji:
2018
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination number
domination subdivision number
domination multisubdivision number
trees
unicyclic graphs
Opis:
The paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622-628], we constructively characterize all connected unicyclic graphs with the domination multisubdivision number equal to 3. We end with further questions and open problems.
Źródło:
Opuscula Mathematica; 2018, 38, 3; 409-425
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
Autorzy:
Dettlaff, M.
Raczek, J.
Yero, I. G.
Powiązania:
https://bibliotekanauki.pl/articles/255785.pdf
Data publikacji:
2016
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination
paired domination
independent domination
edge subdivision
edge multisubdivision
corona graph
Opis:
Given a graph G = (V, E), the subdivision of an edge e = uv ∈ E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions which must be done in one edge such that the domination number increases. Moreover, the concepts of paired domination and independent domination subdivision (respectively multisubdivision) numbers are denned similarly. In this paper we study the domination, paired domination and independent domination (subdivision and multisubdivision) numbers of the generalized corona graphs.
Źródło:
Opuscula Mathematica; 2016, 36, 5; 575-588
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Domination Multisubdivision Number of a Graph
Autorzy:
Avella-Alaminos, Diana
Dettlaff, Magda
Lemańska, Magdalena
Zuazua, Rita
Powiązania:
https://bibliotekanauki.pl/articles/31339480.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
(total) domination
(total) domination subdivision number
(total) domination multisubdivision number
trees
Opis:
The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msdγt (G) of a graph G and we show that for any connected graph G of order at least two, msdγt (G) ≤ 3. We show that for trees the total domination multisubdivision number is equal to the known total domination subdivision number. We also determine the total domination multisubdivision number for some classes of graphs and characterize trees T with msdγt (T) = 1.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 315-327
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Protection of Lexicographic Product Graphs
Autorzy:
Martínez, Abel Cabrera
Rodríguez-Velázquez, Juan Alberto
Powiązania:
https://bibliotekanauki.pl/articles/32304140.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total weak Roman domination
secure total domination
total domination
lexicographic product
Opis:
Given a graph G with vertex set V (G), a function f : V (G) → {0, 1, 2} is said to be a total dominating function if Σu∈N(v) f(u) > 0 for every v ∈ V (G), where N(v) denotes the open neighbourhood of v. Let Vi = {x ∈ V (G) : f(x) = i}. A total dominating function f is a total weak Roman dominating function if for every vertex v ∈ V0 there exists a vertex u ∈ N(v) ∩ (V1 ∪ V2) such that the function f′, defined by f′(v) = 1, f′(u) = f(u) − 1 and f′(x) = f(x) whenever x ∈ V (G) \ {u, v}, is a total dominating function as well. If f is a total weak Roman dominating function and V2 = ∅, then we say that f is a secure total dominating function. The weight of a function f is defined to be ω(f) = Σv∈V (G) f(v). The total weak Roman domination number (secure total domination number) of a graph G is the minimum weight among all total weak Roman dominating functions (secure total dominating functions) on G. In this article, we show that these two parameters coincide for lexicographic product graphs. Furthermore, we obtain closed formulae and tight bounds for these parameters in terms of invariants of the factor graphs involved in the product.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 967-984
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterization of trees with equal 2-domination number and domination number plus two
Autorzy:
Chellali, Mustapha
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743587.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
2-domination number
domination number
trees
Opis:
Let G = (V(G),E(G)) be a simple graph, and let k be a positive integer. A subset D of V(G) is a k-dominating set if every vertex of V(G) - D is dominated at least k times by D. The k-domination number γₖ(G) is the minimum cardinality of a k-dominating set of G. In [5] Volkmann showed that for every nontrivial tree T, γ₂(T) ≥ γ₁(T)+1 and characterized extremal trees attaining this bound. In this paper we characterize all trees T with γ₂(T) = γ₁(T)+2.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 4; 687-697
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Roman bondage in graphs
Autorzy:
Rad, Nader
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743601.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
Roman domination
Roman bondage number
Opis:
A Roman dominating function on a graph G is a function f:V(G) → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f(V(G)) = ∑_{u ∈ V(G)}f(u)$. The Roman domination number, $γ_R(G)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R(G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E' ⊆ E(G) for which $γ_R(G -E') > γ_R(G)$. We determine the Roman bondage number in several classes of graphs and give some sharp bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 4; 763-773
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the Locating Roman Domination Number in Trees
Autorzy:
Jafari Rad, Nader
Rahbani, Hadi
Powiązania:
https://bibliotekanauki.pl/articles/16647912.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination number
locating domination number
locating Roman domination number
tree
Opis:
A Roman dominating function (or just RDF) on a graph G = (V, E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = ∑u∈V(G) f(u). An RDF f can be represented as f = (V0, V1, V2), where Vi = {v ∈ V : f(v) = i} for i = 0, 1, 2. An RDF f = (V0, V1, V2) is called a locating Roman dominating function (or just LRDF) if N(u) ∩ V2 ≠ N(v) ∩ V2 for any pair u, v of distinct vertices of V0. The locating Roman domination number $\gamma _R^L (G)$ is the minimum weight of an LRDF of G. In this paper, we study the locating Roman domination number in trees. We obtain lower and upper bounds for the locating Roman domination number of a tree in terms of its order and the number of leaves and support vertices, and characterize trees achieving equality for the bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 49-62
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the Locating Roman Domination Number in Trees
Autorzy:
Jafari Rad, Nader
Rahbani, Hadi
Powiązania:
https://bibliotekanauki.pl/articles/31342446.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination number
locating domination number
locating Roman domination number
tree
Opis:
A Roman dominating function (or just RDF) on a graph $ G = (V, E) $ is a function $ f : V \rightarrow \{ 0, 1, 2 \} $ satisfying the condition that every vertex $u$ for which $ f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of an RDF $f$ is the value $ f(V (G)) = \Sigma_{ u \in V (G) } f(u) $. An RDF $f$ can be represented as $ f = (V_0, V_1, V_2) $, where $ V_i = \{ v \in V : f(v) = i \} $ for $ i = 0, 1, 2 $. An RDF $ f = (V_0, V_1, V_2) $ is called a locating Roman dominating function (or just LRDF) if $ N(u) \cap V_2 \ne N(v) \cap V_2 $ for any pair $u$, $v$ of distinct vertices of $ V_0 $. The locating Roman domination number $ \gamma_R^L (G) $ is the minimum weight of an LRDF of $G$. In this paper, we study the locating Roman domination number in trees. We obtain lower and upper bounds for the locating Roman domination number of a tree in terms of its order and the number of leaves and support vertices, and characterize trees achieving equality for the bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 49-62
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination Game Critical Graphs
Autorzy:
Bujtás, Csilla
Klavžar, Sandi
Košmrlj, Gašper
Powiązania:
https://bibliotekanauki.pl/articles/31234048.pdf
Data publikacji:
2015-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
domination game
domination game critical graphs
powers of cycles
trees
Opis:
The domination game is played on a graph $G$ by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on $G$ and both players play optimally is the graph invariant $ \gamma_g (G) $, named the game domination number. Here we study the $ \gamma_g$-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize $ \gamma_g$-critical graphs with $ \gamma_g = 2$ and with $ \gamma_g = 3$, moreover for each n we identify the (infinite) class of all $\gamma_g$-critical ones among the $n$th powers $ C_N^n$ of cycles. Along the way we determine $\gamma_{g} ( C_N^n ) $ for all $n$ and $N$. Results of a computer search for $ \gamma_g$-critical trees are presented and several problems and research directions are also listed.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 4; 781-796
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An upper bound on the total outer-independent domination number of a tree
Autorzy:
Krzywkowski, M.
Powiązania:
https://bibliotekanauki.pl/articles/255991.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
total outer-independent domination
total domination
tree
Opis:
A total outer-independent dominating set of a graph G = (V (G),E(G)) is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V (G) \ D is independent. The total outer-independent domination number of a graph G, denoted by [formula], is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every tree T of order n ≥ 4, with l leaves and s support vertices we have [formula], and we characterize the trees attaining this upper bound.
Źródło:
Opuscula Mathematica; 2012, 32, 1; 153-158
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Digraphs with isomorphic underlying and domination graphs: connected $UG^c(d)$
Autorzy:
Factor, Kim
Langley, Larry
Powiązania:
https://bibliotekanauki.pl/articles/743665.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination graph
domination
graph isomorphism
underlying graph
Opis:
The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 51-67
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Gallai-type equality for the total domination number of a graph
Autorzy:
Zhou, Sanming
Powiązania:
https://bibliotekanauki.pl/articles/744259.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
total domination number
Gallai equality
Opis:
We prove the following Gallai-type equality
γₜ(G) + εₜ(G) = p
for any graph G with no isolated vertex, where p is the number of vertices of G, γₜ(G) is the total domination number of G, and εₜ(G) is the maximum integer s such that there exists a spanning forest F with s the number of pendant edges of F minus the number of star components of F.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 539-543
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On locating-domination in graphs
Autorzy:
Chellali, Mustapha
Mimouni, Malika
Slater, Peter
Powiązania:
https://bibliotekanauki.pl/articles/744569.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
upper locating-domination number
locating-domination number
Opis:
A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number $γ_L(G)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, $Γ_L(G)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on $Γ_L(G)$ and $γ_L(G)$.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 2; 223-235
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Accurate Domination in Graphs
Autorzy:
Cyman, Joanna
Henning, Michael A.
Topp, Jerzy
Powiązania:
https://bibliotekanauki.pl/articles/31343372.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
accurate domination number
tree
corona
Opis:
A dominating set of a graph G is a subset D ⊆ VG such that every vertex not in D is adjacent to at least one vertex in D. The cardinality of a smallest dominating set of G, denoted by γ(G), is the domination number of G. The accurate domination number of G, denoted by γa(G), is the cardinality of a smallest set D that is a dominating set of G and no |D|-element subset of VG \ D is a dominating set of G. We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees G for which γa(G) = γ(G) are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 615-627
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Restrained Domination in Self-Complementary Graphs
Autorzy:
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/32083901.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
complement
restrained domination
self-complementary graph
Opis:
A self-complementary graph is a graph isomorphic to its complement. A set S of vertices in a graph G is a restrained dominating set if every vertex in V(G) \ S is adjacent to a vertex in S and to a vertex in V(G) \ S. The restrained domination number of a graph G is the minimum cardinality of a restrained dominating set of G. In this paper, we study restrained domination in self-complementary graphs. In particular, we characterize the self-complementary graphs having equal domination and restrained domination numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 633-645
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the Double Italian Domination Number of a Graph
Autorzy:
Azvin, Farzaneh
Rad, Nader Jafari
Powiązania:
https://bibliotekanauki.pl/articles/32222552.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Italian domination
double Italian domination
probabilistic methods
Opis:
For a graph G, a Roman {3}-dominating function is a function f : V → {0, 1, 2, 3} having the property that for every vertex u ∈ V, if f(u) ∈ {0, 1}, then f(N[u]) ≥ 3. The weight of a Roman {3}-dominating function is the sum w(f) = f(V) = Σv∈V f(v), and the minimum weight of a Roman {3}-dominating function is the Roman {3}-domination number, denoted by γ{R3}(G). In this paper, we present a sharp lower bound for the double Italian domination number of a graph, and improve previous bounds given in [D.A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math. 283 (2022) 555–564]. We also present a probabilistic upper bound for a generalized version of double Italian domination number of a graph, and show that the given bound is asymptotically best possible.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1129-1137
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Two Short Proofs on Total Domination
Autorzy:
Bickle, Allan
Powiązania:
https://bibliotekanauki.pl/articles/30146531.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
Opis:
A set of vertices of a graph G is a total dominating set if each vertex of G is adjacent to a vertex in the set. The total domination number of a graph γt (G) is the minimum size of a total dominating set. We provide a short proof of the result that γt (G) ≤ 2/3n for connected graphs with n ≥ 3 and a short characterization of the extremal graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 457-459
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on bipartite graphs whose [1, k]-domination number equal to their number of vertices
Autorzy:
Ghareghani, Narges
Peterin, Iztok
Sharifani, Pouyeh
Powiązania:
https://bibliotekanauki.pl/articles/256007.pdf
Data publikacji:
2020
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination
[1, k]-domination number
[l,k]-total domination number
bipartite graphs
Opis:
A subset D of the vertex set V of a graph G is called an [1, k]-dominating set if every vertex from V — D is adjacent to at least one vertex and at most fc vertices of D. A [1, k]-dominating set with the minimum number of vertices is called a [formula]-set and the number of its vertices is the [1, k]-domination number [formula] of G. In this short note we show that the decision problem whether [formula] is an NP-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph G of order n satisfying [formula] is given for every integer n ≥ (k + l)(2k + 3).
Źródło:
Opuscula Mathematica; 2020, 40, 3; 375-382
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Paired- and induced paired-domination in {E,net}-free graphs
Autorzy:
Schaudt, Oliver
Powiązania:
https://bibliotekanauki.pl/articles/743226.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
paired-domination
induced paired-domination
induced matchings
{E,net}-free graphs
Opis:
A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study.
We focus on graphs that do not contain the net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (obtained by attaching a pendant vertex to each vertex of the path on three vertices) as induced subgraphs. This graph class is a natural generalization of {claw, net}-free graphs, which are intensively studied with respect to their nice properties concerning domination and hamiltonicity. We show that any connected {E, net}-free graph has a paired-dominating set that, roughly, contains at most half of the vertices of the graph. This bound is a significant improvement to the known general bounds.
Further, we show that any {E, net, C₅}-free graph has an induced paired-dominating set, that is a paired-dominating set that forms an induced matching, and that such set can be chosen to be a minimum paired-dominating set. We use these results to obtain a new characterization of {E, net, C₅}-free graphs in terms of the hereditary existence of induced paired-dominating sets. Finally, we show that the induced matching formed by an induced paired-dominating set in a {E, net, C₅}-free graph can be chosen to have at most two times the size of the smallest maximal induced matching possible.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 473-485
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Fractional global domination in graphs
Autorzy:
Arumugam, Subramanian
Karuppasamy, Kalimuthu
Hamid, Ismail
Powiązania:
https://bibliotekanauki.pl/articles/744509.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
global domination
dominating function
global dominating function
fractional global domination number
Opis:
Let G = (V,E) be a graph. A function g:V → [0,1] is called a global dominating function (GDF) of G, if for every v ∈ V, $g(N[v]) = ∑_{u ∈ N[v]}g(u) ≥ 1$ and $g(\overline{N(v)}) = ∑_{u ∉ N(v)}g(u) ≥ 1$. A GDF g of a graph G is called minimal (MGDF) if for all functions f:V → [0,1] such that f ≤ g and f(v) ≠ g(v) for at least one v ∈ V, f is not a GDF. The fractional global domination number $γ_{fg}(G)$ is defined as follows: $γ_{fg}(G)$ = min{|g|:g is an MGDF of G } where $|g| = ∑_{v ∈ V} g(v)$. In this paper we initiate a study of this parameter.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 33-44
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Power Domination in Knödel Graphs and Hanoi Graphs
Autorzy:
Varghese, Seethu
Vijayakumar, A.
Hinz, Andreas M.
Powiązania:
https://bibliotekanauki.pl/articles/16647915.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
power domination
Knödel graph
Hanoi graph
Opis:
In this paper, we study the power domination problem in Knödel graphs WΔ,2ν and Hanoi graphs $H_p^n $. We determine the power domination number of W3,2ν and provide an upper bound for the power domination number of Wr+1,2r+1 for r ≥ 3. We also compute the k-power domination number and the k-propagation radius of $H_p^2$.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 63-74
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination parameters of a graph with added vertex
Autorzy:
Zwierzchowski, M.
Powiązania:
https://bibliotekanauki.pl/articles/2050876.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
total domination number
strong domination number
subdivision
Opis:
Let $G = (V, E)$ be a graph. A subset $D \subseteq V$ is a total dominating set of $G$ if for every vertex $y \in V$ there is a vertex $x \in D$ with $xy \in E$. A subset $D \subseteq V$ is a strong dominating set of G if for every vertex $y \in V - D$ there is a vertex $x \in D$ with $xy \in E and deg_{G}(x) \geq deg_{G}(y)$. The total domination number $\gamma_{t}(G)$ (the strong domination number $\gamma_{S}(G)$) is defined as the minimum cardinality of a total dominating set (a strong dominating set) of $G$. The concept of total domination was first defined by Cockayne, Dawes and Hedetniemi in 1980 [1], while the strong domination was introduced by Sampathkumar and Pushpa Latha in 1996 [3]. By a subdivision of an edge $uv \in E$ we mean removing edge $uv$, adding a new vertex $x$, and adding edges $ux$ and $vx$. A graph obtained from $G$ by subdivision an edge $uv \in E$ is denoted by $G \oplus uxvx$. The behaviour of the total domination number and the strong domination number of a graph $G \oplus u_{x}v_{x}$ is developed.
Źródło:
Opuscula Mathematica; 2004, 24, 2; 231-234
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on the independent Roman domination in unicyclic graphs
Autorzy:
Chellali, M.
Rad, N. J.
Powiązania:
https://bibliotekanauki.pl/articles/255989.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
Roman domination
independent Roman domination
strong equality
Opis:
A Roman dominating function (RDF) on a graph G= (V, E) is a function ƒ : V → {0, 1, 2} satisfying the condition that every vertex u for which ƒ(u) = 0 is adjacent to at least one vertex v for which ƒ(v)=2. The weight of an RDF is the value [formula]. An RDF ƒ in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number ΥR (G) (respectively, the independent Roman domination number ΥR(G) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that ΥR(G) strongly equals iR(G), denoted by ΥR(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this note we characterize all unicyclic graphs G with ΥR(G) ≡ iR(G).
Źródło:
Opuscula Mathematica; 2012, 32, 4; 715-718
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On locating and differentiating-total domination in trees
Autorzy:
Chellali, Mustapha
Powiązania:
https://bibliotekanauki.pl/articles/743043.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
locating-total domination
differentiating-total domination
trees
Opis:
A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γₜ^L(G)$ and $γₜ^D(G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total dominating set of G, respectively. We show that for a nontrivial tree T of order n, with l leaves and s support vertices, $γₜ^L(T) ≥ max{2(n+l-s+1)/5,(n+2-s)/2}$, and for a tree of order n ≥ 3, $γₜ^D(T) ≥ 3(n+l-s+1)/7$, improving the lower bounds of Haynes, Henning and Howard. Moreover we characterize the trees satisfying $γₜ^L(T) = 2(n+l- s+1)/5$ or $γₜ^D(T) = 3(n+l-s+1)/7$.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 3; 383-392
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ł:
Graphs with large double domination numbers
Autorzy:
Henning, Michael
Powiązania:
https://bibliotekanauki.pl/articles/744277.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bounds
domination
double domination
minimum degree two
Opis:
In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{×2}(G)$. If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that $γ_{×2}(G) ≤ 3n/4$ and we characterize those graphs achieving equality.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 13-28
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total domination subdivision numbers of graphs
Autorzy:
Haynes, Teresa
Henning, Michael
Hopkins, Lora
Powiązania:
https://bibliotekanauki.pl/articles/744561.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination number
total domination subdivision number
Opis:
A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number for some families of graphs. Then we show that the total domination subdivision number of a graph can be arbitrarily large.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 457-467
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Total Domination in the Cartesian Product of Graphs
Autorzy:
Brešar, Boštjan
Hartinger, Tatiana Romina
Kos, Tim
Milanič, Martin
Powiązania:
https://bibliotekanauki.pl/articles/31342240.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
Cartesian product
total domination quotient
Opis:
Ho proved in [A note on the total domination number, Util. Math. 77 (2008) 97–100] that the total domination number of the Cartesian product of any two graphs without isolated vertices is at least one half of the product of their total domination numbers. We extend a result of Lu and Hou from [Total domination in the Cartesian product of a graph and $ K_2 $ or $ C_n $, Util. Math. 83 (2010) 313–322] by characterizing the pairs of graphs $G$ and $H$ for which $ \gamma_t (G \square H)=1/2 \gamma_t (G) \gamma_t (H) $, whenever $ \gamma_t (H) = 2 $. In addition, we present an infinite family of graphs $ G_n $ with $ \gamma_t (G_n) = 2n $, which asymptotically approximate equality in $ \gamma_t (G_n \square H_n ) \ge 1/2 \gamma_t (G_n)^2 $.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 963-976
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Power Domination in Knödel Graphs and Hanoi Graphs
Autorzy:
Varghese, Seethu
Vijayakumar, A.
Hinz, Andreas M.
Powiązania:
https://bibliotekanauki.pl/articles/31342442.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
power domination
Knödel graph
Hanoi graph
Opis:
In this paper, we study the power domination problem in Knödel graphs $ W_{ \Delta,2 \nu } $ and Hanoi graphs $ H_p^n $. We determine the power domination number of $ W_{3,2 \nu } $ and provide an upper bound for the power domination number of $ W_{r+1,2^{r+1}} $ for $ r \ge 3 $. We also compute the $k$-power domination number and the k-propagation radius of $ H_p^2 $.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 63-74
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Independent Domination in Planar Cubic Graphs
Autorzy:
Abrishami, Gholamreza
Henning, Michael A.
Rahbarnia, Freydoon
Powiązania:
https://bibliotekanauki.pl/articles/31343229.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independent domination number
domination number
cubic graphs
Opis:
A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i(G)$, of $G$ is the minimum cardinality of an independent dominating set. Goddard and Henning [Discrete Math. 313 (2013) 839–854] posed the conjecture that if \( G \not\in \{ K_{3,3}, C_5 \square K_2 \} \) is a connected, cubic graph on $n$ vertices, then $i(G) \le 3/8 n $, where $ C_5 \square K_2 $ is the 5-prism. As an application of known result, we observe that this conjecture is true when $G$ is 2-connected and planar, and we provide an infinite family of such graphs that achieve the bound. We conjecture that if $G$ is a bipartite, planar, cubic graph of order $n$, then $ i(G) \le 1/3 n $, and we provide an infinite family of such graphs that achieve this bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 841-853
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination Subdivision Numbers
Autorzy:
Haynes, Teresa
Hedetniemi, Sandra
Hedetniemi, Stephen
Jacobs, David
Knisely, James
van der Merwe, Lucas
Powiązania:
https://bibliotekanauki.pl/articles/743491.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
subdivision
Opis:
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $sd_γ(G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 ≤ sd_γ(G) ≤ 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that $sd_γ(G) ≤ γ(G)+1$ for any graph G without isolated vertices, and give constant upper bounds on $sd_γ(G)$ for several families of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 239-253
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On domination in graphs
Autorzy:
Göring, Frank
Harant, Jochen
Powiązania:
https://bibliotekanauki.pl/articles/744282.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph
domination
Opis:
For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 7-12
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree
Autorzy:
Edwards, Michelle
MacGillivray, Gary
Nasserasr, Shahla
Powiązania:
https://bibliotekanauki.pl/articles/31342281.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
reconfiguration
Opis:
We consider γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. We answer three open questions about γ-graphs of trees by providing upper bounds on the maximum degree, the diameter, and the number of minimum dominating sets. The latter gives an upper bound on the order of the γ-graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 703-716
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Trees with equal restrained domination and total restrained domination numbers
Autorzy:
Raczek, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/743684.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total restrained domination number
restrained domination number
trees
Opis:
For a graph G = (V,E), a set D ⊆ V(G) is a total restrained dominating set if it is a dominating set and both ⟨D⟩ and ⟨V(G)-D⟩ do not have isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. A set D ⊆ V(G) is a restrained dominating set if it is a dominating set and ⟨V(G)-D⟩ does not contain an isolated vertex. The cardinality of a minimum restrained dominating set in G is the restrained domination number. We characterize all trees for which total restrained and restrained domination numbers are equal.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 83-91
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Grundy Total Domination Number in Product Graphs
Autorzy:
Brešar, Boštjan
Bujtás, Csilla
Gologranc, Tanja
Klavžar, Sandi
Košmrlj, Gašper
Marc, Tilen
Patkós, Balázs
Tuza, Zsolt
Vizer, Máté
Powiązania:
https://bibliotekanauki.pl/articles/32083828.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
Grundy total domination number
graph product
Opis:
A longest sequence $(v_1, . . ., v_k)$ of vertices of a graph $G$ is a Grundy total dominating sequence of $G$ if for all $i$, \(N(υ_i)\backslash\bigcup_{j=1}^{i-1}N(υ_j)≠∅\). The length $k$ of the sequence is called the Grundy total domination number of $G$ and denoted $\gamma_{gr}^t(G)$. In this paper, the Grundy total domination number is studied on four standard graph products. For the direct product we show that $\gamma_{gr}^t(G×H)≥\gamma_{gr}^t(G)\gamma_{gr}^t(H)$, conjecture that the equality always holds, and prove the conjecture in several special cases. For the lexicographic product we express $\gamma_{gr}^t(G∘H)$ in terms of related invariant of the factors and find some explicit formulas for it. For the strong product, lower bounds on $\gamma_{gr}^t(G⊠H)$ are proved as well as upper bounds for products of paths and cycles. For the Cartesian product we prove lower and upper bounds on the Grundy total domination number when factors are paths or cycles.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 225-247
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees
Autorzy:
Chellali, Mustapha
Rad, Nader Jafari
Powiązania:
https://bibliotekanauki.pl/articles/30146596.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination
independent Roman domination
strong equality
trees
Opis:
A Roman dominating function (RDF) on a graph $G = (V,E)$ is a function $ f : V \rightarrow {0, 1, 2} $ satisfying the condition that every vertex $ u $ for which $ f(u) = 0 $ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of an RDF is the value $ f(V (G)) = \Sigma_{u \in V (G) } f(u) $. An RDF $f$ in a graph $G$ is independent if no two vertices assigned positive values are adjacent. The Roman domination number $ \gamma_R (G) $ (respectively, the independent Roman domination number $ i_R(G) $) is the minimum weight of an RDF (respectively, independent RDF) on $G$. We say that $ \gamma_R(G)$ strongly equals $ i_R(G)$, denoted by $ \gamma_R (G) \equiv i_R(G)$, if every RDF on $G$ of minimum weight is independent. In this paper we provide a constructive characterization of trees $T$ with $ \gamma_R(T) \equiv i_R(T) $.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 337-346
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Concepts Arising from Strong Efficient Domination Number. Part I
Autorzy:
Meena, N.
Gayathri, A.
Powiązania:
https://bibliotekanauki.pl/articles/1030980.pdf
Data publikacji:
2020
Wydawca:
Przedsiębiorstwo Wydawnictw Naukowych Darwin / Scientific Publishing House DARWIN
Tematy:
domination
strong efficient bondage number
strong efficient domination
Opis:
Let G=(V,E) be a simple graph. A subset S of V(G) is called a strong (weak) efficient dominating set of G if for every v∈V(G),|N_s [v]∩S|=1.(|N_w [v]∩S|=1) , where N_s [v]={u∈V(G) ∶uv ∈E(G),deg〖u ≥degv 〗 }. (N_w [v]={u∈V(G) ∶uv ∈E(G), degv ≥degu The minimum cardinality of a strong (weak) efficient dominating set of G is called the strong (weak) efficient dominating set of G and is denoted by γ_se (G) (γ_we (G)). A graph G is strong efficient if there exists a strong efficient dominating set of G. The strong efficient bondage number b_se (G) of a non empty graph G is the minimum cardinality among all sets of edges X⊆E such that γ_se (G-X)>γ_se (G). In this paper, the strong efficient bondage number of some path related graphs and some special graphs are studied.
Źródło:
World Scientific News; 2020, 145; 342-353
2392-2192
Pojawia się w:
World Scientific News
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Trees with equal total domination and total restrained domination numbers
Autorzy:
Chen, Xue-Gang
Shiu, Wai
Chen, Hong-Yu
Powiązania:
https://bibliotekanauki.pl/articles/743513.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination number
total restrained domination number
tree
Opis:
For a graph G = (V,E), a set S ⊆ V(G) is a total dominating set if it is dominating and both ⟨S⟩ has no isolated vertices. The cardinality of a minimum total dominating set in G is the total domination number. A set S ⊆ V(G) is a total restrained dominating set if it is total dominating and ⟨V(G)-S⟩ has no isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. We characterize all trees for which total domination and total restrained domination numbers are the same.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 59-66
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Roman Domination of Digraphs
Autorzy:
Chen, Xiaodan
Hao, Guoliang
Xie, Zhihong
Powiązania:
https://bibliotekanauki.pl/articles/31343785.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination number
domination number
digraph
Nordhaus-Gaddum
Opis:
A vertex subset $S$ of a digraph $D$ is called a dominating set of $D$ if every vertex not in $S$ is adjacent from at least one vertex in $S$. The domination number of a digraph $D$, denoted by $ \gamma(D) $, is the minimum cardinality of a dominating set of $D$. A Roman dominating function (RDF) on a digraph $D$ is a function $ f : V (D) \rightarrow {0, 1, 2} $ satisfying the condition that every vertex $v$ with $f(v) = 0$ has an in-neighbor $u$ with $f(u) = 2$. The weight of an RDF $f$ is the value $ \omega (f) = \Sigma_{ v \in V(D) } f(v) $. The Roman domination number of a digraph $D$, denoted by $ \gamma_R (D) $, is the minimum weight of an RDF on $D$. In this paper, for any integer $k$ with $ 2 \le k \le \gamma(D) $, we characterize the digraphs $D$ of order $ n \ge 4 $ with $ \delta − (D) \ge 1 $ for which $ \gamma_R(D) = (D) + k $ holds. We also characterize the digraphs $D$ of order $ n \ge k $ with $ \gamma_R(D) = k $ for any positive integer $k$. In addition, we present a Nordhaus-Gaddum bound on the Roman domination number of digraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 13-21
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Extremal Graphs for a Bound on the Roman Domination Number
Autorzy:
Bouchou, Ahmed
Blidia, Mostafa
Chellali, Mustapha
Powiązania:
https://bibliotekanauki.pl/articles/31513493.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination
Roman domination number
Nordhaus-Gaddum inequalities
Opis:
A Roman dominating function on a graph G = (V, E) is a function f:V (G) → {0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least one vertex v with f(v) = 2. The weight of a Roman dominating function is the value w(f) = Σu∈V(G) f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). In 2009, Chambers, Kinnersley, Prince and West proved that for any graph G with n vertices and maximum degree Δ, γR(G) ≤ n + 1 − Δ. In this paper, we give a characterization of graphs attaining the previous bound including trees, regular and semiregular graphs. Moreover, we prove that the problem of deciding whether γR(G) = n + 1 − Δ is co-complete. Finally, we provide a characterization of extremal graphs of a Nordhaus–Gaddum bound for γR(G) + γR (Ḡ), where Ḡ is the complement graph of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 771-785
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination Number, Independent Domination Number and 2-Independence Number in Trees
Autorzy:
Dehgardi, Nasrin
Sheikholeslami, Seyed Mahmoud
Valinavaz, Mina
Aram, Hamideh
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/32083746.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
2-independence number
domination number
independent domination number
Opis:
For a graph $G$, let $\gamma(G)$ be the domination number, $i(G)$ be the independent domination number and $\beta_2(G)$ be the 2-independence number. In this paper, we prove that for any tree $T$ of order $n ≥ 2, 4\beta_2(T) − 3\gamma(T) ≥ 3i(T)$, and we characterize all trees attaining equality. Also we prove that for every tree $T$ of order \(n ≥ 2, i(T)≤\frac{3\beta_2(T)}{4}\), and we characterize all extreme trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 39-49
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Roman {2}-Bondage Number of a Graph
Autorzy:
Moradi, Ahmad
Mojdeh, Doost Ali
Sharifi, Omid
Powiązania:
https://bibliotekanauki.pl/articles/32083773.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
Roman {2}-domination
Roman {2}-bondage number
Opis:
For a given graph G=(V, E), a Roman {2}-dominating function f : V (G) → {0, 1, 2} has the property that for every vertex u with f(u) = 0, either u is adjacent to a vertex assigned 2 under f, or is adjacent to at least two vertices assigned 1 under f. The Roman {2}-domination number of G, γ{R2}(G), is the minimum of Σu∈V (G) f(u) over all such functions. In this paper, we initiate the study of the problem of finding Roman {2}-bondage number of G. The Roman {2}-bondage number of G, b{R2}, is defined as the cardinality of a smallest edge set E′ ⊆ E for which γ{R2}(G − E′) > γ{R2}(G). We first demonstrate complexity status of the problem by proving that the problem is NP-Hard. Then, we derive useful parametric as well as fixed upper bounds on the Roman {2}-bondage number of G. Specifically, it is known that the Roman bondage number of every planar graph does not exceed 15 (see [S. Akbari, M. Khatirinejad and S. Qajar, A note on the Roman bondage number of planar graphs, Graphs Combin. 29 (2013) 327–331]). We show that same bound will be preserved while computing the Roman {2}-bondage number of such graphs. The paper is then concluded by computing exact value of the parameter for some classes of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 255-268
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Fractional distance domination in graphs
Autorzy:
Arumugam, S.
Mathew, Varughese
Karuppasamy, K.
Powiązania:
https://bibliotekanauki.pl/articles/743206.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
distance k-domination
distance k-dominating function
k-packing
fractional distance k-domination
Opis:
Let G = (V,E) be a connected graph and let k be a positive integer with k ≤ rad(G). A subset D ⊆ V is called a distance k-dominating set of G if for every v ∈ V - D, there exists a vertex u ∈ D such that d(u,v) ≤ k. In this paper we study the fractional version of distance k-domination and related parameters.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 449-459
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the total k-domination number of graphs
Autorzy:
Kazemi, Adel
Powiązania:
https://bibliotekanauki.pl/articles/743228.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total k-domination (k-tuple total domination) number
k-tuple domination number
k-transversal number
Opis:
Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{×k}(G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $|N_G[v] ∩ S| ≥ k$. Also the total k-domination number $γ_{×k,t}(G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $|N_G(v) ∩ S| ≥ k$. The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H).
We know that for any graph G of order n with minimum degree at least k, $γ_{×k}(G) ≤ γ_{×k,t}(G) ≤ n$. Obviously for every k-regular graph, the upper bound n is sharp. Here, we give a sufficient condition for $γ_{×k,t}(G) < n$. Then we characterize complete multipartite graphs G with $γ_{×k}(G) = γ_{×k,t}(G)$. We also state that the total k-domination number of a graph is the k -transversal number of its open neighborhood hypergraph, and also the domination number of a graph is the transversal number of its closed neighborhood hypergraph. Finally, we give an upper bound for the total k -domination number of the cross product graph G×H of two graphs G and H in terms on the similar numbers of G and H. Also, we show that this upper bound is strict for some graphs, when k = 1.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 419-426
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Slater and Sub-k-Domination Number of a Graph with Applications to Domination and k-Domination
Autorzy:
Amos, David
Asplund, John
Brimkov, Boris
Davila, Randy
Powiązania:
https://bibliotekanauki.pl/articles/32083827.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Slater number
domination number
sub- k -domination number
k -domination number
degree sequence index strategy
Opis:
In this paper we introduce and study a new graph invariant derived from the degree sequence of a graph G, called the sub-k-domination number and denoted subk(G). This invariant serves as a generalization of the Slater number; in particular, we show that subk(G) is a computationally efficient sharp lower bound on the k-domination number of G, and improves on several known lower bounds. We also characterize the sub-k-domination numbers of several families of graphs, provide structural results on sub-k-domination, and explore properties of graphs which are subk(G)-critical with respect to addition and deletion of vertices and edges.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 209-225
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Strong Efficient Co-Bondage Number of Some Graphs
Autorzy:
Meena, N.
Vignesh, M. Madhan
Powiązania:
https://bibliotekanauki.pl/articles/1030836.pdf
Data publikacji:
2020
Wydawca:
Przedsiębiorstwo Wydawnictw Naukowych Darwin / Scientific Publishing House DARWIN
Tematy:
domination
strong efficient co-bondage number
strong efficient domination
Opis:
Let G = (V, E) be a simple graph. A subset S of V(G) is called a strong (weak) efficient dominating set of G if for every v ∈ V(G), |N_s [v]∩ S|=1. (|N_w [v]∩ S|=1), where N_s (v) = {u ∈V(G) : uv∈ E(G), deg u ≥ deg v}. (N_w (v) = {u ∈V(G) : uv∈ E(G), deg v ≥ deg u}). The minimum cardinality of a strong (weak) efficient dominating set of G is called the strong (weak) efficient domination number of G and is denoted by γ_se(G) (γ_we(G)). A graph G is strong efficient if there exists a strong efficient dominating set of G. The strong efficient co-bondage number 〖bc〗_se(G) is the maximum cardinality of all sets of edges X ⊆ E such that γ_se (G+X) γ_se(G). In this paper, the strong efficient co-bondage number of some standard graphs and some special graphs are determined.
Źródło:
World Scientific News; 2020, 145; 234-244
2392-2192
Pojawia się w:
World Scientific News
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Concepts Arising from Strong Efficient Domination Number. Part – III
Autorzy:
Vignesh, M. Madhan
Meena, N.
Powiązania:
https://bibliotekanauki.pl/articles/1031631.pdf
Data publikacji:
2020
Wydawca:
Przedsiębiorstwo Wydawnictw Naukowych Darwin / Scientific Publishing House DARWIN
Tematy:
domination
strong efficient co-bondage number
strong efficient domination
Opis:
Let G = (V, E) be a simple graph. A subset S of V(G) is called a strong (weak) efficient dominating set of G if for every v ∈ V(G), |N_s[] ∩ S|=1. (|N_w [] ∩ S|=1), where N_s () = {u ∈V(G) : uv ∈ E(G), deg u ≥ deg v}. (N_w () = {u ∈V(G) : uv ∈ E(G), deg v ≥ deg u}). The minimum cardinality of a strong (weak) efficient dominating set of G is called the strong (weak) efficient domination number of G and is denoted by γ_se(G) (γ_we(G)). A graph G is strong efficient if there exists a strong efficient dominating set of G. The strong efficient co-bondage number (G) is the maximum cardinality of all sets of edges X ⊆ E such that γ_se( + ) ≤ γ_se(G). In this paper, further results on strong efficient co-bondage number of some special graphs are determined.
Źródło:
World Scientific News; 2020, 146; 110-120
2392-2192
Pojawia się w:
World Scientific News
Dostawca treści:
Biblioteka Nauki
Artykuł
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ł:
Partitioning a graph into a dominating set, a total dominating set, and something else
Autorzy:
Henning, Michael
Löwenstein, Christian
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/744065.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
domatic number
vertex partition
Petersen graph
Opis:
A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 563-574
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Note on the split domination number of the Cartesian product of paths
Autorzy:
Zwierzchowski, Maciej
Powiązania:
https://bibliotekanauki.pl/articles/744304.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
split domination number
Cartesian product of graphs
Opis:
In this note the split domination number of the Cartesian product of two paths is considered. Our results are related to [2] where the domination number of Pₘ ☐ Pₙ was studied. The split domination number of P₂ ☐ Pₙ is calculated, and we give good estimates for the split domination number of Pₘ ☐ Pₙ expressed in terms of its domination number.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 79-84
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Non-Dominating Set Partitions in Graphs
Autorzy:
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/31340558.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
non-dominating partition
nontotal dominating partition
Opis:
A set $S$ of vertices of a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex of $S$ and is a total dominating set if every vertex of $G$ is adjacent to a vertex of $S$. The cardinality of a minimum dominating (total dominating) set of $G$ is called the domination (total domination) number. A set that does not dominate (totally dominate) $G$ is called a non-dominating (non-total dominating) set of $G$. A partition of the vertices of $G$ into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph $G$ equals the total domination number of its complement $ \overline{G} $ and the minimum number of sets in a non-total dominating set partition of $G$ equals the domination number of $ \overline{G} $. This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 1043-1050
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some Toughness Results in Independent Domination Critical Graphs
Autorzy:
Ananchuen, Nawarat
Ananchuen, Watcharaphong
Powiązania:
https://bibliotekanauki.pl/articles/31339252.pdf
Data publikacji:
2015-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination critical
toughness
Opis:
A subset $ S $ of $ V (G) $ is an independent dominating set of $ G $ if $ S $ is independent and each vertex of $ G $ is either in $ S $ or adjacent to some vertex of $ S $. Let $ i(G) $ denote the minimum cardinality of an independent dominating set of $ G $. A graph $ G $ is $k$-$i$-critical if $ i(G) = k $, but $ i(G+uv) < k $ for any pair of non-adjacent vertices $ u $ and $ v $ of $ G $. In this paper, we establish that if $ G $ is a connected 3-$i$-critical graph and $S$ is a vertex cutset of $G$ with $ |S| ≥ 3 $, then $ \omega ( G - S ) \leq \frac{1+\sqrt{8|S|+1}}{2} $, improving a result proved by Ao [3], where $\omega(G−S)$ denotes the number of components of $G−S$. We also provide a characterization of the connected 3-$i$-critical graphs $G$ attaining the maximum number of $ \omega(G − S)$ when $S$ is a minimum cutset of size 2 or 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 4; 703-713
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Characterization of Hypergraphs with Large Domination Number
Autorzy:
Henning, Michael A.
Löwenstein, Christian
Powiązania:
https://bibliotekanauki.pl/articles/31340924.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
transversal
hypergraph
Opis:
Let $ H = (V, E) $ be a hypergraph with vertex set $ V $ and edge set $ E $. A dominating set in $ H $ is a subset of vertices $ D \subseteq V $ such that for every vertex $ v \in V \ \backslash \ D $ there exists an edge $ \mathcal{e} \in E $ for which $ v \in \mathcal{e} $ and $ \mathcal{e} \cap D \ne \emptyset $. The domination number $ \gamma (H) $ is the minimum cardinality of a dominating set in $ H $. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for $ k \ge 5 $, if $ H $ is a hypergraph of order $ n $ and size $ m $ with all edges of size at least $ k $ and with no isolated vertex, then $ \gamma (H) \ge (n + \floor{ (k − 3)//2 } m) // ( \floor{ 3(k − 1)//2 } ) $. In this paper, we apply a recent result of the authors on hypergraphs with large transversal number [M.A. Henning and C. Löwenstein, A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem, Discrete Math. 323 (2014) 69-75] to characterize the hypergraphs achieving equality in this bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 427-438
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Convex and Weakly Convex Domination in Prism Graphs
Autorzy:
Rosicka, Monika
Powiązania:
https://bibliotekanauki.pl/articles/31343291.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
prism graphs
Opis:
For a given graph G = (V;E) and permutation π : V ↦ V the prism πG of G is defined as follows: V (πG) = V (G) ∪ V (G′), where G′ is a copy of G, and E(πG) = E(G) ∪ E(G′) ∪ Mπ, where Mπ = {uv′ : u ∈ V (G); v = π (u)} and v′ denotes the copy of v in G′. We study and compare the properties of convex and weakly convex dominating sets in prism graphs. In particular, we characterize prism γcon-fixers and -doublers. We also show that the differences γwcon(G) – γwcon(πG) and γwcon (πG) – 2γwcon (G) can be arbitrarily large, and that the convex domination number of πG cannot be bounded in terms of γcon (G).
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 741-755
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-100 z 328

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