Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 34

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available remote

Signed k-independence in graphs

100%
Volkmann L.
Open Mathematics
|
2014
|
tom 12
|
nr 3
517-528
EN
Let k ≥ 2 be an integer. A function f: V(G) → {−1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k − 1. That is, Σx∈N[v] f(x) ≤ k − 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σv∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α sk(G) of G. In this work, we mainly present upper bounds on α sk (G), as for example α sk(G) ≤ n − 2⌈(Δ(G) + 2 − k)/2⌉, and we prove the Nordhaus-Gaddum type inequality $$\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$$, where n is the order, Δ(G) the maximum degree and $$\bar G$$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.
2
Content available remote

Signed Roman Edgek-Domination in Graphs

100%
Asgharsharghi L., Sheikholeslami S. M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
39-53
EN
Let k ≥ 1 be an integer, and G = (V, E) be a finite and simple graph. The closed neighborhood NG[e] of an edge e in a graph G is the set consisting of e and all edges having a common end-vertex with e. A signed Roman edge k-dominating function (SREkDF) on a graph G is a function f : E → {−1, 1, 2} satisfying the conditions that (i) for every edge e of G, ∑x∈NG[e] f(x) ≥ k and (ii) every edge e for which f(e) = −1 is adjacent to at least one edge e′ for which f(e′) = 2. The minimum of the values ∑e∈E f(e), taken over all signed Roman edge k-dominating functions f of G is called the signed Roman edge k-domination number of G, and is denoted by γ′sRk(G). In this paper we initiate the study of the signed Roman edge k-domination in graphs and present some (sharp) bounds for this parameter.
3
Content available remote

Power Domination in Knödel Graphs and Hanoi Graphs

100%
Varghese S., Vijayakumar A., Hinz A. M.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
63-74
EN
In this paper, we study the power domination problem in Knödel graphs WΔ,2ν and Hanoi graphs [...] Hpn $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 [...] Hp2 $H_p^2$ .
4
Content available remote

Bounds on the Locating Roman Domination Number in Trees

100%
Jafari Rad N., Rahbani H.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
49-62
EN
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 [...] γRL(G) $\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.
5
Content available remote

A Note on the Locating-Total Domination in Graphs

100%
Miller M., Rajan R. S., Jayagopal R., Rajasingh I., Manuel P.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
745-754
EN
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.
6
Content available remote

Eternal Domination: Criticality and Reachability

100%
Klostermeyer W. F., MacGillivray G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
63-77
EN
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.
7
Content available remote

Bounds On The Disjunctive Total Domination Number Of A Tree

100%
Henning M. A., Naicker V.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
153-171
EN
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, γ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, [...] γtd(G) $\gamma _t^d (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G) $\gamma _t^d (G) \le \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 ℓ leaves and s support vertices, then [...] 2(n−ℓ+3)/5≤γtd(T)≤(n+s−1)/2 $2(n - \ell + 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 [...] γt(T)/γtd(T)<2 $\gamma _t (T)/\gamma _t^d (T) < 2$ and this bound is asymptotically tight.
8
Content available remote

Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

100%
Henning M. A., Marcon A. J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
71-93
EN
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.
9
Content available remote

Domination Parameters of a Graph and its Complement

100%
Desormeaux W. J., Haynes T. W., Henning M. A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
203-215
EN
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.
10
Content available remote

Hereditary Equality of Domination and Exponential Domination

100%
Henning M. A., Jäger S., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
275-285
EN
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.
11
Content available remote

On the Totalk-Domination in Graphs

100%
Bermudo S., Hernández-Gómez J. C., Sigarreta J. M.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
301-317
EN
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.
12
Content available remote

Gamma Graphs Of Some Special Classes Of Trees

100%
Bień A.
Annales Mathematicae Silesianae
|
2015
|
tom 29
|
nr 1
25-34
EN
A set S ⊂ V is a dominating set of a graph G = (V, E) if every vertex υ ∈ V which does not belong to S has a neighbour in S. The domination number γ(G) of the graph G is the minimum cardinality of a dominating set in G. A dominating set S is a γ-set in G if |S| = γ(G). Some graphs have exponentially many γ-sets, hence it is worth to ask a question if a γ-set can be obtained by some transformations from another γ-set. The study of gamma graphs is an answer to this reconfiguration problem. We give a partial answer to the question which graphs are gamma graphs of trees. In the second section gamma graphs γ.T of trees with diameter not greater than five will be presented. It will be shown that hypercubes Qk are among γ.T graphs. In the third section γ.T graphs of certain trees with three pendant vertices will be analysed. Additionally, some observations on the diameter of gamma graphs will be presented, in response to an open question, published by Fricke et al., if diam(T (γ)) = O(n)?
13
Content available remote

On the total domination subdivision numbers in graphs

100%
Sheikholeslami S.
Open Mathematics
|
2010
|
tom 8
|
nr 3
468-473
EN
A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (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 total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sdγ t(G) ≤ 2γ t(G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sdγ t(G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sdγ t(G)=2γt(G)−1.
14
Content available remote

A lower bound for the packing chromatic number of the Cartesian product of cycles

100%
Jacobs Y., Jonck E., Joubert E.
Open Mathematics
|
2013
|
tom 11
|
nr 7
1344-1357
EN
Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9 ≤ χρ(C 4 □ C q). We will also show that if t is a multiple of four, then χρ(C 4 □ C q) = 9.
15
Content available remote

Dominating and total dominating partitions in cubic graphs

100%
Southey J., Henning M.
Open Mathematics
|
2011
|
tom 9
|
nr 3
699-708
EN
In this paper, we continue the study of domination and total domination in cubic graphs. It is known [Henning M.A., Southey J., A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 2008, 89, 159–162] that every cubic graph has a dominating set and a total dominating set which are disjoint. In this paper we show that every connected cubic graph on nvertices has a total dominating set whose complement contains a dominating set such that the cardinality of the total dominating set is at most (n+2)/2, and this bound is essentially best possible.
16
Content available remote

Cubic Graphs with Total Domatic Number at Least Two

81%
Akbari S., Motiei M., Mozaffari S., Yazdanbod S.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
75-82
EN
Let G be a graph with no isolated vertex. A total dominating set of G is a set S of vertices of G such that every vertex is adjacent to at least one vertex in S. The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of G. In this paper we provide a criterion under which a cubic graph has total domatic number at least two.
17
Content available remote

Regularity and Planarity of Token Graphs

81%
Carballosa W., Fabila-Monroy R., Leaños J., Rivera L. M.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
573-586
EN
Let G = (V, E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph.
18
Content available remote

Signed Total Roman Domination in Digraphs

81%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
261-272
EN
Let D be a finite and simple digraph with vertex set V (D). A signed total Roman dominating function (STRDF) on a digraph D is a function f : V (D) → {−1, 1, 2} satisfying the conditions that (i) ∑x∈N−(v) f(x) ≥ 1 for each v ∈ V (D), where N−(v) consists of all vertices of D from which arcs go into v, and (ii) every vertex u for which f(u) = −1 has an inner neighbor v for which f(v) = 2. The weight of an STRDF f is w(f) = ∑v∈V (D) f(v). The signed total Roman domination number γstR(D) of D is the minimum weight of an STRDF on D. In this paper we initiate the study of the signed total Roman domination number of digraphs, and we present different bounds on γstR(D). In addition, we determine the signed total Roman domination number of some classes of digraphs. Some of our results are extensions of known properties of the signed total Roman domination number γstR(G) of graphs G.
19
Content available remote

A Characterization for 2-Self-Centered Graphs

81%
Shekarriz M. H., Mirzavaziri M., Mirzavaziri K.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
27-37
EN
A graph is called 2-self-centered if its diameter and radius both equal to 2. In this paper, we begin characterizing these graphs by characterizing edge-maximal 2-self-centered graphs via their complements. Then we split characterizing edge-minimal 2-self-centered graphs into two cases. First, we characterize edge-minimal 2-self-centered graphs without triangles by introducing specialized bi-independent covering (SBIC) and a structure named generalized complete bipartite graph (GCBG). Then, we complete characterization by characterizing edge-minimal 2-self-centered graphs with some triangles. Hence, the main characterization is done since a graph is 2-self-centered if and only if it is a spanning subgraph of some edge-maximal 2-self-centered graphs and, at the same time, it is a spanning supergraph of some edge-minimal 2-self-centered graphs.
20
Content available remote

Bounding the Openk-Monopoly Number of Strong Product Graphs

81%
Kuziak D., Peterin I., Yero I. G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
287-299
EN
Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ {1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋} be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k $\delta _M (v) \ge {{\delta _G (v)} \over 2} + k$ , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this article we study the open k-monopoly number of strong product graphs. We present general lower and upper bounds for the open k-monopoly number of strong product graphs. Moreover, we study in addition the open 0-monopolies of several specific families of strong product graphs.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.