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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-46 z 46
    Tytuł:
    Connected odd dominating sets in graphs
    Autorzy:
    Caro, Yair
    Klostermeyer, William
    Yuster, Raphael
    Powiązania:
    https://bibliotekanauki.pl/articles/744351.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    odd dominating set
    Opis:
    An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 3; 225-239
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Note on the Locating-Total Domination in Graphs
    Autorzy:
    Miller, Mirka
    Rajan, R. Sundara
    Jayagopal, R.
    Rajasingh, Indra
    Manuel, Paul
    Powiązania:
    https://bibliotekanauki.pl/articles/31341658.pdf
    Data publikacji:
    2017-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    total dominating set
    locating-dominating set
    locating-total dominating set
    regular graphs
    Opis:
    In this paper we obtain a sharp (improved) lower bound on the locating-total domination number of a graph, and show that the decision problem for the locating-total domination is NP-complete.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 3; 745-754
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Making a Dominating Set of a Graph Connected
    Autorzy:
    Li, Hengzhe
    Wu, Baoyindureng
    Yang, Weihua
    Powiązania:
    https://bibliotekanauki.pl/articles/31342251.pdf
    Data publikacji:
    2018-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    independent set
    dominating set
    connected dominating set
    Opis:
    Let $ G = (V,E) $ be a graph and $ S \subseteq V $. We say that $ S $ is a dominating set of $ G $, if each vertex in $ V \backlash S $ has a neighbor in $S$. Moreover, we say that $S$ is a connected (respectively, 2-edge connected or 2-connected) dominating set of $G$ if $ G[S] $ is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2-edge connected domination, or 2-connected domination) number of $G$ is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of $G$, and is denoted $ \gamma (G) $ (respectively $ \gamma_1 (G) $, or $ \gamma_2^′ (G) $, or $ \gamma_2 (G) $). A well-known result of Duchet and Meyniel states that $ \gamma_1 (G) \le 3 \gamma (G) − 2 $ for any connected graph $G$. We show that if $ \gamma (G) \ge 2 $, then $ \gamma_2^′ (G) \ge 5 \gamma (G) − 4 $ when $G$ is a 2-edge connected graph and $ \gamma_2 (G) \le 11 \gamma (G) − 13 $ when $G$ is a 2-connected triangle-free graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 4; 947-962
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Odd and residue domination numbers of a graph
    Autorzy:
    Caro, Yair
    Klostermeyer, William
    Goldwasser, John
    Powiązania:
    https://bibliotekanauki.pl/articles/743442.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    odd dominating set
    parity domination
    Opis:
    Let G = (V,E) be a simple, undirected graph. A set of vertices D is called an odd dominating set if |N[v] ∩ D| ≡ 1 (mod 2) for every vertex v ∈ V(G). The minimum cardinality of an odd dominating set is called the odd domination number of G, denoted by γ₁(G). In this paper, several algorithmic and structural results are presented on this parameter for grids, complements of powers of cycles, and other graph classes as well as for more general forms of "residue" domination.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 1; 119-136
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Eternal Domination: Criticality and Reachability
    Autorzy:
    Klostermeyer, William F.
    MacGillivray, Gary
    Powiązania:
    https://bibliotekanauki.pl/articles/31342174.pdf
    Data publikacji:
    2017-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    eternal dominating set
    critical graphs
    Opis:
    We show that for every minimum eternal dominating set, D, of a graph G and every vertex v ∈ D, there is a sequence of attacks at the vertices of G which can be defended in such a way that an eternal dominating set not containing v is reached. The study of the stronger assertion that such a set can be reached after a single attack is defended leads to the study of graphs which are critical in the sense that deleting any vertex reduces the eternal domination number. Examples of these graphs and tight bounds on connectivity, edge-connectivity and diameter are given. It is also shown that there exist graphs in which deletion of any edge increases the eternal domination number, and graphs in which addition of any edge decreases the eternal domination number.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 1; 63-77
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Hereditary Equality of Domination and Exponential Domination in Subcubic Graphs
    Autorzy:
    Chen, Xue-Gang
    Wang, Yu-Feng
    Wu, Xiao-Fei
    Powiązania:
    https://bibliotekanauki.pl/articles/32324524.pdf
    Data publikacji:
    2021-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    exponential dominating set
    subcubic graphs
    Opis:
    Let γ(G) and γe(G) denote the domination number and exponential domination number of graph G, respectively. Henning et al., in [Hereditary equality of domination and exponential domination, Discuss. Math. Graph Theory 38 (2018) 275–285] gave a conjecture: There is a finite set ℱ of graphs such that a graph G satisfies (H) = γe(H) for every induced subgraph H of G if and only if G is ℱ-free. In this paper, we study the conjecture for subcubic graphs. We characterize the class ℱ by minimal forbidden induced subgraphs and prove that the conjecture holds for subcubic graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1067-1075
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Independent transversal domination in graphs
    Autorzy:
    Hamid, Ismail
    Powiązania:
    https://bibliotekanauki.pl/articles/743635.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    independent set
    independent transversal dominating set
    Opis:
    A set S ⊆ V of vertices in a graph G = (V, E) is called a dominating set if every vertex in V-S is adjacent to a vertex in S. A dominating set which intersects every maximum independent set in G is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by $γ_{it}(G)$. In this paper we begin an investigation of this parameter.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 1; 5-17
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Quasiperfect domination in triangular lattices
    Autorzy:
    Dejter, Italo
    Powiązania:
    https://bibliotekanauki.pl/articles/743129.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    perfect dominating set
    quasiperfect dominating set
    triangular lattice
    Opis:
    A vertex subset S of a graph G is a perfect (resp. quasiperfect) dominating set in G if each vertex v of G∖S is adjacent to only one vertex ($d_v$ ∈ {1,2} vertices) of S. Perfect and quasiperfect dominating sets in the regular tessellation graph of Schläfli symbol {3,6} and in its toroidal quotients are investigated, yielding the classification of their perfect dominating sets and most of their quasiperfect dominating sets S with induced components of the form $K_ν$, where ν ∈ {1,2,3} depends only on S.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 1; 179-198
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Bounds on the Locating-Domination Number and Differentiating-Total Domination Number in Trees
    Autorzy:
    Rad, Nader Jafari
    Rahbani, Hadi
    Powiązania:
    https://bibliotekanauki.pl/articles/31342324.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    locating-dominating set
    differentiating-total dominating set
    tree
    Opis:
    A subset $S$ of vertices in a graph $G = (V,E)$ is a dominating set of $G$ if every vertex in $V − S$ has a neighbor in $S$, and is a total dominating set if every vertex in $V$ has a neighbor in $S$. A dominating set $S$ is a locating-dominating set of $G$ if every two vertices $ x, y \in V − S$ satisfy $N(x) \cap S \ne N(y) \cap S$. The locating-domination number $ \gamma_L (G) $ is the minimum cardinality of a locating-dominating set of $G$. A total dominating set $S$ is called a differentiating-total dominating set if for every pair of distinct vertices $u$ and $v$ of $G$, $ N[u] \cap S \ne N[v] \cap S $. The minimum cardinality of a differentiating-total dominating set of $G$ is the differentiating-total domination number of $G$, denoted by $ \gamma_t^D (G) $. We obtain new upper bounds for the locating-domination number, and the differentiating-total domination number in trees. Moreover, we characterize all trees achieving equality for the new bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 455-462
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Domination, Eternal Domination, and Clique Covering
    Autorzy:
    Klostermeyer, William F.
    Mynhardt, C.M.
    Powiązania:
    https://bibliotekanauki.pl/articles/31339487.pdf
    Data publikacji:
    2015-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    eternal dominating set
    independent set
    clique cover
    Opis:
    Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 2; 283-300
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On minimum intersections of certain secondary dominating sets in graphs
    Autorzy:
    Kosiorowska, Anna
    Michalski, Adrian
    Włoch, Iwona
    Powiązania:
    https://bibliotekanauki.pl/articles/29519420.pdf
    Data publikacji:
    2023
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    dominating set
    2-dominating set
    (1, 2)-dominating set
    proper (1, 2)-dominating set
    domination number
    (1,2)-intersection index
    Opis:
    In this paper we consider secondary dominating sets, also named as (1,k)-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the (1, 1)-dominating sets and proper (1, 2)-dominating sets. We introduce (1,2̅)-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.
    Źródło:
    Opuscula Mathematica; 2023, 43, 6; 813-827
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Edge Dominating Sets and Vertex Covers
    Autorzy:
    Dutton, Ronald
    Klostermeyer, William F.
    Powiązania:
    https://bibliotekanauki.pl/articles/30146532.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge dominating set
    matching
    total dominating set
    vertex cover
    Opis:
    Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 437-456
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Dominating Vertex Covers: The Vertex-Edge Domination Problem
    Autorzy:
    Klostermeyer, William F.
    Messinger, Margaret-Ellen
    Yeo, Anders
    Powiązania:
    https://bibliotekanauki.pl/articles/32083812.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    cubic graph
    dominating set
    vertex cover
    vertex-edge dominating set
    Opis:
    The vertex-edge domination number of a graph, γve(G), is defined to be the cardinality of a smallest set D such that there exists a vertex cover C of G such that each vertex in C is dominated by a vertex in D. This is motivated by the problem of determining how many guards are needed in a graph so that a searchlight can be shone down each edge by a guard either incident to that edge or at most distance one from a vertex incident to the edge. Our main result is that for any cubic graph G with n vertices, γve(G) ≤ 9n/26. We also show that it is NP-hard to decide if γve(G) = γ(G) for bipartite graph G.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 123-132
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A characterization of roman trees
    Autorzy:
    Henning, Michael
    Powiązania:
    https://bibliotekanauki.pl/articles/743366.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    Roman dominating function
    Opis:
    A Roman dominating function (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 f is $w(f) = ∑_{v ∈ V} f(v)$. The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number are called Roman graphs. At the Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications held at Western Michigan University in June 2000, Stephen T. Hedetniemi in his principal talk entitled "Defending the Roman Empire" posed the open problem of characterizing the Roman trees. In this paper, we give a characterization of Roman trees.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 2; 325-334
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Bounds on the Locating-Total Domination Number in Trees
    Autorzy:
    Wang, Kun
    Ning, Wenjie
    Lu, Mei
    Powiązania:
    https://bibliotekanauki.pl/articles/31867549.pdf
    Data publikacji:
    2020-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    tree
    total dominating set
    locating-total dominating set
    locating-total domination number
    Opis:
    Given a graph $G = (V, E)$ with no isolated vertex, a subset $S$ of $V$ is called a total dominating set of $G$ if every vertex in $V$ has a neighbor in $S$. A total dominating set $S$ is called a locating-total dominating set if for each pair of distinct vertices $u$ and $v$ in $V \ S, N(u) ∩ S ≠ N(v) ∩ S$. The minimum cardinality of a locating-total dominating set of $G$ is the locating-total domination number, denoted by $γ_t^L(G)$. We show that, for a tree $T$ of order $n ≥ 3$ and diameter $d$, \(\frac{d+1}{2}≤γ_t^L(T)≤n−\frac{d−1}{2}\), and if $T$ has $l$ leaves, $s$ support vertices and $s_1$ strong support vertices, then \(γ_t^L(T)≥max\Big\{\frac{n+l−s+1}{2}−\frac{s+s_1}{4},\frac{2(n+1)+3(l−s)−s_1}{5}\Big\}\). We also characterize the extremal trees achieving these bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 1; 25-34
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    False alarms in fault-tolerant dominating sets in graphs
    Autorzy:
    Nikodem, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/255949.pdf
    Data publikacji:
    2012
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    liar’s dominating set
    fault-tolerant dominating set
    false alarm
    hamming distance
    Opis:
    We develop the problem of fault-tolerant dominating sets (liar's dominating sets) in graphs. Namely, we consider a new kind of fault - a false alarm. Characterization of such fault-tolerant dominating sets in three different cases (dependent on the classification of the types of the faults) are presented.
    Źródło:
    Opuscula Mathematica; 2012, 32, 4; 751-760
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Mean value for the matching and dominating polynomial
    Autorzy:
    Arocha, Jorge
    Llano, Bernardo
    Powiązania:
    https://bibliotekanauki.pl/articles/743687.pdf
    Data publikacji:
    2000
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    matching
    matching polynomial
    dominating set
    Opis:
    The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2000, 20, 1; 57-69
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Domination hypergraphs of certain digraphs
    Autorzy:
    Sonntag, M.
    Teichert, H. M.
    Powiązania:
    https://bibliotekanauki.pl/articles/254767.pdf
    Data publikacji:
    2010
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    hypergraph
    dominating set
    directed graph
    Opis:
    If D = (V,A) is a digraph, its domination hypergraph DH(D) = (V, E) has the vertex set V and e ⊆ V is an edge of DH(D) if and only if e is a minimal dominating set of D. We investigate domination hypergraphs of special classes of digraphs, namely tournaments, paths and cycles. Finally, using a special decomposition/composition method we construct edge sets of domination hypergraphs of certain digraphs.
    Źródło:
    Opuscula Mathematica; 2010, 30, 2; 179-191
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On non-z(mod k) dominating sets
    Autorzy:
    Caro, Yair
    Jacobson, Michael
    Powiązania:
    https://bibliotekanauki.pl/articles/743399.pdf
    Data publikacji:
    2003
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    tree
    unicyclic graph
    Opis:
    For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 1, a subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x ∈ V(G), |N[x]∩D| ≢ z (mod k).For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with z < k and z ≠ 1, that a non-z(mod k) dominating set exist for all trees. Also, it will be shown that for k ≥ 4, z ≥ 1, 2 or 3 that any unicyclic graph contains a non-z(mod k) dominating set. We also give a few special cases of other families of graphs for which these dominating sets must exist.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2003, 23, 1; 189-199
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Highly connected counterexamples to a conjecture on α-domination
    Autorzy:
    Tuza, Zsolt
    Powiązania:
    https://bibliotekanauki.pl/articles/744177.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    dominating set
    α-domination
    Opis:
    An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 3; 435-440
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    NP-completeness of weakly convex and convex dominating set decision problems
    Autorzy:
    Raczek, J.
    Powiązania:
    https://bibliotekanauki.pl/articles/2050778.pdf
    Data publikacji:
    2004
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    dominating set
    NP-completeness
    distance
    convex set
    Opis:
    The convex domination number and the weakly convex domination number are new domination parameters. In this paper we show that the decision problems of convex and weakly convex dominating sets are NP-complete for bipartite and split graphs. Using a modified version of Warshall algorithm we can verify in polynomial time whether a given subset of vertices of a graph is convex or weakly convex.
    Źródło:
    Opuscula Mathematica; 2004, 24, 2; 189-196
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The domination number of $K_n^3$
    Autorzy:
    Georges, John
    Lin, Jianwei
    Mauro, David
    Powiązania:
    https://bibliotekanauki.pl/articles/30148694.pdf
    Data publikacji:
    2014-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Cartesian product
    dominating set
    domination number
    Opis:
    Let $K_n^3$ denote the Cartesian product $K_n□K_n□K_n$, where $K_n$ is the complete graph on $n$ vertices. We show that the domination number of $K_n^3$ is $⌈\frac{n^2}{2}⌉$.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 3; 629-632
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    M2-edge colorings of dense graphs
    Autorzy:
    Ivanco, J.
    Powiązania:
    https://bibliotekanauki.pl/articles/254913.pdf
    Data publikacji:
    2016
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    edge coloring
    dominating set
    dense graphs
    Opis:
    An edge coloring φ of a graph G is called an Mi-edge coloring if [formula] every vertex v of G, where φ (v) is the set of colors of edges incident with v. Let K1(G) denote the maximum number of colors used in an Mi-edge coloring of G. In this paper we establish some bounds of K.2(G), present some graphs achieving the bounds and determine exact values of K.2(G) for dense graphs.
    Źródło:
    Opuscula Mathematica; 2016, 36, 5; 603-612
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Domination Number of Graphs with Minimum Degree Five
    Autorzy:
    Bujtás, Csilla
    Powiązania:
    https://bibliotekanauki.pl/articles/32222697.pdf
    Data publikacji:
    2021-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    domination number
    discharging method
    Opis:
    We prove that for every graph G on n vertices and with minimum degree five, the domination number γ(G) cannot exceed n/3. The proof combines an algorithmic approach and the discharging method. Using the same technique, we provide a shorter proof for the known upper bound 4n/11 on the domination number of graphs of minimum degree four.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 3; 763-777
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Fault Tolerant Detectors for Distinguishing Sets in Graphs
    Autorzy:
    Seo, Suk J.
    Slater, Peter J.
    Powiązania:
    https://bibliotekanauki.pl/articles/31234046.pdf
    Data publikacji:
    2015-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    distinguishing sets
    fault tolerant detectors
    redundant distinguishing open-locating-dominating set
    detection distinguishing open-locating-dominating set
    Opis:
    For various domination-related parameters involving locating devices (distinguishing sets) that function as places from which detectors can determine information about the location of an “intruder”, several types of possible detector faults are identified. Two of these fault tolerant detector types for distinguishing sets are considered here, namely redundant distinguishing and detection distinguishing. Illustrating these concepts, we focus primarily on open-locating-dominating sets.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 4; 797-818
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On equality in an upper bound for the acyclic domination number
    Autorzy:
    Samodivkin, V.
    Powiązania:
    https://bibliotekanauki.pl/articles/255046.pdf
    Data publikacji:
    2008
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    dominating set
    acyclic set
    independent set
    acyclic domination number
    Opis:
    A subset A of vertices in a graph G is acyclic if the subgraph it induces contains no cycles. The acyclic domination number ϒa (G) of a graph G is the minimum cardinality of an acyclic dominating set of G. For any graph G with n vertices and maximum degree Δ(G), ϒa(G) ≤ n - Δ(G). In this paper we characterize the connected graphs and the connected triangle-free graphs which achieve this upper bound.
    Źródło:
    Opuscula Mathematica; 2008, 28, 3; 331-334
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    γ-paired dominating graphs of cycles
    Autorzy:
    Eakawinrujee, Pannawat
    Trakultraipruk, Nantapath
    Powiązania:
    https://bibliotekanauki.pl/articles/2048671.pdf
    Data publikacji:
    2022
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    paired dominating graph
    paired dominating set
    paired-domination number
    Opis:
    A paired dominating set of a graph G is a dominating set whose induced subgraph contains a perfect matching. The paired domination number, denoted by γpr(G), is the minimum cardinality of a paired dominating set of G. A γpr(G)-set is a paired dominating set of cardinality γpr(G). The γ-paired dominating graph of G, denoted by PDγ(G), as the graph whose vertices are γpr(G)-sets. Two γpr(G)-sets D1 and D2 are adjacent in PDγ(G) if there exists a vertex u ∈ D1 and a vertex v /∈ D1 such that D2 = (D1 \ {u}) ∪ {v}. In this paper, we present the γ-paired dominating graphs of cycles.
    Źródło:
    Opuscula Mathematica; 2022, 42, 1; 31-54
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Dominating sets and domination polynomials of certain graphs, II
    Autorzy:
    Alikhani, S.
    Yee-hock, P.
    Powiązania:
    https://bibliotekanauki.pl/articles/255942.pdf
    Data publikacji:
    2010
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    domination polynomial
    dominating set
    cycle
    theta graph
    Opis:
    The domination polynomial of a graph G of order n is the polynomial [formula] where d(G, i) is the number of dominating sets of G of size i, and ϒ (G) is the domination number of G. In this paper, we obtain some properties of the coefficients of D(G, x). Also, by study of the dominating sets and the domination polynomials of specific graphs denoted by G'(m), we obtain a relationship between the domination polynomial of graphs containing an induced path of length at least three, and the domination polynomial of related graphs obtained by replacing the path by shorter path. As examples of graphs G' (m), we study the dominating sets and domination polynomials of cycles and generalized theta graphs. Finally, we show that, if n ≡ 0, 2(mod 3) and D(G, x) = D(Cn, x), then G = Cn.
    Źródło:
    Opuscula Mathematica; 2010, 30, 1; 37-51
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Domination in partitioned graphs
    Autorzy:
    Tuza, Zsolt
    Vestergaard, Preben
    Powiązania:
    https://bibliotekanauki.pl/articles/743565.pdf
    Data publikacji:
    2002
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    dominating set
    domination number
    vertex partition
    Opis:
    Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2002, 22, 1; 199-210
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Mf-Edge Colorings of Graphs
    Autorzy:
    Ivančo, Jaroslav
    Onderko, Alfréd
    Powiązania:
    https://bibliotekanauki.pl/articles/32222570.pdf
    Data publikacji:
    2022-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge coloring
    anti-Ramsey number
    dominating set
    Opis:
    An edge coloring φ of a graph G is called an Mf-edge coloring if |φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let Kf (G) denote the maximum number of colors used in an Mf-edge coloring of G. In this paper we establish some bounds on Kf(G), present some graphs achieving the bounds and determine exact values of Kf(G) for some special classes of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1075-1088
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Weakly convex and convex domination numbers
    Autorzy:
    Lemańska, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/2050775.pdf
    Data publikacji:
    2004
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    dominating set
    connected domination number
    distance
    isometric set
    convex set
    Opis:
    Two new domination parameters for a connected graph G: the weakly convex domination number of G and the convex domination number of G are introduced. Relations between these parameters and the other domination parameters are derived. In particular, we study for which cubic graphs the convex domination number equals the connected domination number.
    Źródło:
    Opuscula Mathematica; 2004, 24, 2; 181-188
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Optimal Locating-Total Dominating Sets in Strips of Height 3
    Autorzy:
    Junnila, Ville
    Powiązania:
    https://bibliotekanauki.pl/articles/31339416.pdf
    Data publikacji:
    2015-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    locating-total dominating set
    domination
    square grid
    strip
    Opis:
    A set C of vertices in a graph G = (V,E) is total dominating in G if all vertices of V are adjacent to a vertex of C. Furthermore, if a total dominating set C in G has the additional property that for any distinct vertices u, v ∈ V \ C the subsets formed by the vertices of C respectively adjacent to u and v are different, then we say that C is a locating-total dominating set in G. Previously, locating-total dominating sets in strips have been studied by Henning and Jafari Rad (2012). In particular, they have determined the sizes of the smallest locating-total dominating sets in the finite strips of height 2 for all lengths. Moreover, they state as open question the analogous problem for the strips of height 3. In this paper, we answer the proposed question by determining the smallest sizes of locating-total dominating sets in the finite strips of height 3 as well as the smallest density in the infinite strip of height 3.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 3; 447-462
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Minimal Geodetic Domination in Graphs
    Autorzy:
    Nuenay, Hearty M.
    Jamil, Ferdinand P.
    Powiązania:
    https://bibliotekanauki.pl/articles/31339437.pdf
    Data publikacji:
    2015-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    minimal geodetic dominating set
    upper geodetic domination number
    Opis:
    Let $G$ be a connected graph. For two vertices $u$ and $v$ in $G$, a $u$-$v$ geodesic is any shortest path joining $u$ and $v$. The closed geodetic interval $ I_G[u, v] $ consists of all vertices of $G$ lying on any $u$-$v$ geodesic. For $ S \subseteq V (G) $, $S$ is a geodetic set in $G$ if \( \bigcup_{u,v \in S} I_G [u, v] = V (G) \). Vertices $u$ and $v$ of $G$ are neighbors if $u$ and $v$ are adjacent. The closed neighborhood $ N_G[v]$ of vertex $v$ consists of $v$ and all neighbors of $v$. For $S \subseteq V (G)$, $S$ is a dominating set in $G$ if \( \bigcup_{u \in S} N_G[u] = V (G) \). A geodetic dominating set in $G$ is any geodetic set in $G$ which is at the same time a dominating set in $G$. A geodetic dominating set in $G$ is a minimal geodetic dominating set if it does not have a proper subset which is itself a geodetic dominating set in $G$. The maximum cardinality of a minimal geodetic dominating set in $G$ is the upper geodetic domination number of $G$. This paper initiates the study of minimal geodetic dominating sets and upper geodetic domination numbers of connected graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 3; 403-418
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Counterexample to a conjecture on the structure of bipartite partitionable graphs
    Autorzy:
    Gibson, Richard
    Mynhardt, Christina
    Powiązania:
    https://bibliotekanauki.pl/articles/743437.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    prism fixer
    symmetric dominating set
    bipartite graph
    Opis:
    A graph G is called a prism fixer if γ(G×K₂) = γ(G), where γ(G) denotes the domination number of G. A symmetric γ-set of G is a minimum dominating set D which admits a partition D = D₁∪ D₂ such that $V(G)-N[D_i] = D_j$, i,j = 1,2, i ≠ j. It is known that G is a prism fixer if and only if G has a symmetric γ-set.
    Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004), 389-402] conjectured that if G is a connected, bipartite graph such that V(G) can be partitioned into symmetric γ-sets, then G ≅ C₄ or G can be obtained from $K_{2t,2t}$ by removing the edges of t vertex-disjoint 4-cycles. We construct a counterexample to this conjecture and prove an alternative result on the structure of such bipartite graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 3; 527-540
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Triangle-free planar graphs with minimum degree 3 have radius at least 3
    Autorzy:
    Kim, Seog-Jim
    West, Douglas
    Powiązania:
    https://bibliotekanauki.pl/articles/743089.pdf
    Data publikacji:
    2008
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar graph
    radius
    minimum degree
    triangle-free
    dominating set
    Opis:
    We prove that every triangle-free planar graph with minimum degree 3 has radius at least 3; equivalently, no vertex neighborhood is a dominating set.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2008, 28, 3; 563-566
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Distance 2-Domination in Prisms of Graphs
    Autorzy:
    Hurtado, Ferran
    Mora, Mercè
    Rivera-Campo, Eduardo
    Zuazua, Rita
    Powiązania:
    https://bibliotekanauki.pl/articles/31341963.pdf
    Data publikacji:
    2017-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    distance 2 dominating set
    prisms of graphs
    universal fixer
    Opis:
    A set of vertices D of a graph G is a distance 2-dominating set of G if the distance between each vertex u ∊ (V (G) − D) and D is at most two. Let γ2(G) denote the size of a smallest distance 2-dominating set of G. For any permutation π of the vertex set of G, the prism of G with respect to π is the graph πG obtained from G and a copy G′ of G by joining u ∊ V(G) with v′ ∊ V(G′) if and only if v′ = π(u). If γ2(πG) = γ2(G) for any permutation π of V(G), then G is called a universal γ2-fixer. In this work we characterize the cycles and paths that are universal γ2-fixers.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 2; 383-397
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Dominating bipartite subgraphs in graphs
    Autorzy:
    Bacsó, Gábor
    Michalak, Danuta
    Tuza, Zsolt
    Powiązania:
    https://bibliotekanauki.pl/articles/744313.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    dominating subgraph
    forbidden induced subgraph
    bipartite graph
    k-partite graph
    Opis:
    A graph G is hereditarily dominated by a class of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to . In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 85-94
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Compared Costs of Domination Location-Domination and Identification
    Autorzy:
    Hudry, Olivier
    Lobstein, Antoine
    Powiązania:
    https://bibliotekanauki.pl/articles/32083840.pdf
    Data publikacji:
    2020-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph theory
    dominating set
    locating-dominating code
    identifying code
    twin-free graph
    Opis:
    Let G = (V, E) be a finite graph and r ≥ 1 be an integer. For v ∈ V, let Br(v) = {x ∈ V : d(v, x) ≤ r} be the ball of radius r centered at v. A set C ⊆ V is an r-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅; it is an r-locating-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅, and for any two distinct non-codewords x ∈ V \ C, y ∈ V \ C, we have Br(x) ∩ C ≠ Br(y) ∩ C; it is an r-identifying code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅, and for any two distinct vertices x ∈ V, y ∈ V, we have Br(x) ∩ C ≠ Br(y) ∩ C. We denote by γr(G) (respectively, ldr(G) and idr(G)) the smallest possible cardinality of an r-dominating code (respectively, an r-locating-dominating code and an r-identifying code). We study how small and how large the three differences idr(G)−ldr(G), idr(G)−γr(G) and ldr(G) − γr(G) can be.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 1; 127-147
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On (k,l)-kernels in D-join of digraphs
    Autorzy:
    Szumny, Waldemar
    Włoch, Andrzej
    Włoch, Iwona
    Powiązania:
    https://bibliotekanauki.pl/articles/743421.pdf
    Data publikacji:
    2007
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    (k,l)-kernel
    k-independent set
    l-dominating set
    D-join
    counting
    Opis:
    In [5] the necessary and sufficient conditions for the existence of (k,l)-kernels in a D-join of digraphs were given if the digraph D is without circuits of length less than k. In this paper we generalize these results for an arbitrary digraph D. Moreover, we give the total number of (k,l)-kernels, k-independent sets and l-dominating sets in a D-join of digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2007, 27, 3; 457-470
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Trees whose 2-domination subdivision number is 2
    Autorzy:
    Atapour, M.
    Sheikholeslami, S. M.
    Khodkar, A.
    Powiązania:
    https://bibliotekanauki.pl/articles/254847.pdf
    Data publikacji:
    2012
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    2-dominating set
    2-domination number
    2-domination subdivision numbe
    Opis:
    A set S of vertices in a graph G = (V,E) is a 2-dominating set if every vertex of V \ S is adjacent to at least two vertices of S. The 2-domination number of a graph G, denoted by γ2(G), is the minimum size of a 2-dominating set of G. The 2-domination subdivision number sdγ2 (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 2-domination number. The authors have recently proved that for any tree T of order at least 3, 1 ≤ sdγ2 (T ) ≤ 2. In this paper we provide a constructive characterization of the trees whose 2-domination subdivision number is 2.
    Źródło:
    Opuscula Mathematica; 2012, 32, 3; 423-437
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Graph domination in distance two
    Autorzy:
    Bacsó, Gábor
    Tálos, Attila
    Tuza, Zsolt
    Powiązania:
    https://bibliotekanauki.pl/articles/744316.pdf
    Data publikacji:
    2005
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    dominating set
    connected domination
    distance domination
    forbidden induced subgraph
    Opis:
    Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $Dom Dom _u = Dom₂ _u$ holds for $_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, ₂ = {K₁} and ₃ = {all complete graphs}.) Some negative examples are also given.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 121-128
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A simple linear algorithm for the connected domination problem in circular-arc graphs
    Autorzy:
    Hung, Ruo-Wei
    Chang, Maw-Shang
    Powiązania:
    https://bibliotekanauki.pl/articles/744451.pdf
    Data publikacji:
    2004
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph algorithms
    circular-arc graphs
    connected dominating set
    shortest path
    Opis:
    A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2004, 24, 1; 137-145
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Rainbow Vertex-Connection
    Autorzy:
    Li, Xueliang
    Shi, Yongtang
    Powiązania:
    https://bibliotekanauki.pl/articles/30146636.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    rainbow vertex-connection
    vertex coloring
    minimum degree
    2-step dominating set
    Opis:
    A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It was proved that if $G$ is a graph of order $n$ with minimum degree $ \delta $, then $ rvc(G) < 11n//\delta$. In this paper, we show that $rvc(G) \le 3n//(δ+1)+5$ for $ \delta \ge \sqrt{n-1} -1 $ and $ n \le 290 $, while $ rvc(G) \le 4n//(δ + 1) + 5 $ for $ 16 \le \delta \le \sqrt{n-1}-2 $ and $ rvc(G) \le 4n//(\delta + 1) + C(\delta) $ for $6 \le \delta \le 15$, where $ C(\delta) = e^\frac{ 3 \log (\delta^3 + 2 \delta^2 +3)-3(\log 3 - 1)}{\delta - 3} - 2$. We also prove that $ rvc(G) \le 3n//4 − 2 $ for $ \delta = 3$, $ rvc(G) \le 3n//5 − 8//5$ for $\delta = 4$ and $rvc(G) \le n//2 − 2$ for $\delta = 5$. Moreover, an example constructed by Caro et al. shows that when $ \delta \ge \sqrt{n-1} - 1 $ and $ \delta = 3, 4, 5 $, our bounds are seen to be tight up to additive constants.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 307-313
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Spanning trees with many or few colors in edge-colored graphs
    Autorzy:
    Broersma, Hajo
    Li, Xueliang
    Powiązania:
    https://bibliotekanauki.pl/articles/971955.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-coloring
    spanning tree
    matroid (intersection)
    complexity
    NP-complete
    NP-hard
    polynomial algorithm
    (minimum) dominating set
    Opis:
    Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    An efficient connected dominating set algorithm in WSNs based on the induced tree of the crossed cube
    Autorzy:
    Zhang, J.
    Xu, L.
    Zhou, S. M.
    Wu, W.
    Ye, X.
    Powiązania:
    https://bibliotekanauki.pl/articles/330830.pdf
    Data publikacji:
    2015
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    wireless sensor networks
    connected dominating set
    induced tree
    approximation algorithm
    crossed cube
    bezprzewodowa sieć sensorowa
    podgrafy indukowane
    algorytm aproksymacyjny
    Opis:
    The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced tree of the crossed cube (ITCC) is presented. The ITCC is to find a maximal independent set (MIS), which is based on building an induced tree of the crossed cube network, and then to connect the MIS nodes to form a CDS. The priority of an induced tree is determined according to a new parameter, the degree of the node in the square of a graph. This paper presents the proof that the ITCC generates a CDS with a lower approximation ratio. Furthermore, it is proved that the cardinality of the induced trees is a Fibonacci sequence, and an upper bound to the number of the dominating set is established. The simulations show that the algorithm provides the smallest CDS size compared with some other traditional algorithms.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2015, 25, 2; 295-309
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Quest for A Characterization of Hom-Properties of Finite Character
    Autorzy:
    Broere, Izak
    Matsoha, Moroli D.V.
    Heidema, Johannes
    Powiązania:
    https://bibliotekanauki.pl/articles/31340894.pdf
    Data publikacji:
    2016-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    (countable) graph
    homomorphism (of graphs)
    property of graphs
    hom-property
    (finitely-)induced-hereditary property
    finitely determined property
    (weakly) finite character
    axiomatizable property
    compactness theorems
    core
    connectedness
    chromatic number
    clique number
    independence number
    dominating set
    Opis:
    A graph property is a set of (countable) graphs. A homomorphism from a graph \( G \) to a graph \( H \) is an edge-preserving map from the vertex set of \( G \) into the vertex set of \( H \); if such a map exists, we write \( G \rightarrow H \). Given any graph \( H \), the hom-property \( \rightarrow H \) is the set of \( H \)-colourable graphs, i.e., the set of all graphs \( G \) satisfying \( G \rightarrow H \). A graph property \( mathcal{P} \) is of finite character if, whenever we have that \( F \in \mathcal{P} \) for every finite induced subgraph \( F \) of a graph \( G \), then we have that \( G \in \mathcal{P} \) too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on \( H \) for \( \rightarrow H \) to be of finite character. A notable (but known) sufficient condition is that \( H \) is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those \( H \) for which \( \rightarrow H \) is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 2; 479-500
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-46 z 46

      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