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: 24

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

Bounds on the Signed 2-Independence Number in Graphs

100%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 4
709-715
EN
Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds on α2s(G), as for example α2s(G) ≤ n−2 [∆ (G)/2], and we prove the Nordhaus-Gaddum type inequality α2s (G) + α2s(G) ≤ n+1, where n is the order and ∆ (G) is the maximum degree of the graph G. Some of our theorems improve well-known results on the signed 2-independence number.
2
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.
3
Content available remote

Upper Bounds on the Signed Total (K, K)-Domatic Number of Graphs

100%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
641-650
EN
Let G be a graph with vertex set V (G), and let f : V (G) → {−1, 1} be a two-valued function. If k ≥ 1 is an integer and Σx∈N(v) f(x) ≥ k for each v ∈ V (G), where N(v) is the neighborhood of v, then f is a signed total k-dominating function on G. A set {f1, f2, . . . , fd} of distinct signed total k-dominating functions on G with the property that Σdi=1 fi(x) ≤ k for each x ∈ V (G), is called a signed total (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed total (k, k)-dominating family on G is the signed total (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed total (k, k)- domatic number, in particular for regular graphs.
4
Content available remote

The Signed Total Roman k-Domatic Number Of A Graph

100%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 4
1027-1038
EN
Let k ≥ 1 be an integer. A signed total Roman k-dominating function on a graph G is a function f : V (G) → {−1, 1, 2} such that Ʃu2N(v) f(u) ≥ k for every v ∈ V (G), where N(v) is the neighborhood of v, and every vertex u ∈ V (G) for which f(u) = −1 is adjacent to at least one vertex w for which f(w) = 2. A set {f1, f2, . . . , fd} of distinct signed total Roman k-dominating functions on G with the property that Ʃdi=1 fi(v) ≤ k for each v ∈ V (G), is called a signed total Roman k-dominating family (of functions) on G. The maximum number of functions in a signed total Roman k-dominating family on G is the signed total Roman k-domatic number of G, denoted by dkstR(G). In this paper we initiate the study of signed total Roman k-domatic numbers in graphs, and we present sharp bounds for dkstR(G). In particular, we derive some Nordhaus-Gaddum type inequalities. In addition, we determine the signed total Roman k-domatic number of some graphs.
5
Content available remote

Signed Total Roman Domination in Digraphs

100%
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.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Connected global offensive k-alliances in graphs

100%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
699-707
EN
We consider finite graphs G with vertex set V(G). For a subset S ⊆ V(G), we define by G[S] the subgraph induced by S. By n(G) = |V(G) | and δ(G) we denote the order and the minimum degree of G, respectively. Let k be a positive integer. A subset S ⊆ V(G) is a connected global offensive k-alliance of the connected graph G, if G[S] is connected and |N(v) ∩ S | ≥ |N(v) -S | + k for every vertex v ∈ V(G) -S, where N(v) is the neighborhood of v. The connected global offensive k-alliance number $γₒ^{k,c}(G)$ is the minimum cardinality of a connected global offensive k-alliance in G. In this paper we characterize connected graphs G with $γₒ^{k,c}(G) = n(G)$. In the case that δ(G) ≥ k ≥ 2, we also characterize the family of connected graphs G with $γₒ^{k,c}(G) = n(G) - 1$. Furthermore, we present different tight bounds of $γₒ^{k,c}(G)$.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Signed domination and signed domatic numbers of digraphs

100%
Volkmann L.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
415-427
EN
Let D be a finite and simple digraph with the vertex set V(D), and let f:V(D) → {-1,1} be a two-valued function. If $∑_{x ∈ N¯[v]}f(x) ≥ 1$ for each v ∈ V(D), where N¯[v] consists of v and all vertices of D from which arcs go into v, then f is a signed dominating function on D. The sum f(V(D)) is called the weight w(f) of f. The minimum of weights w(f), taken over all signed dominating functions f on D, is the signed domination number $γ_S(D)$ of D. A set ${f₁,f₂,...,f_d}$ of signed dominating functions on D with the property that $∑_{i = 1}^d f_i(x) ≤ 1$ for each x ∈ V(D), is called a signed dominating family (of functions) on D. The maximum number of functions in a signed dominating family on D is the signed domatic number of D, denoted by $d_S(D)$. In this work we show that $4-n ≤ γ_S(D) ≤ n$ for each digraph D of order n ≥ 2, and we characterize the digraphs attending the lower bound as well as the upper bound. Furthermore, we prove that $γ_S(D) + d_S(D) ≤ n + 1$ for any digraph D of order n, and we characterize the digraphs D with $γ_S(D) + d_S(D) = n + 1$. Some of our theorems imply well-known results on the signed domination number of graphs.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A lower bound for the irredundance number of trees

64%
Poschen M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
209-215
EN
Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of Lemańska's result.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Characterization of block graphs with equal 2-domination number and domination number plus one

64%
Hansberg A., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
93-103
EN
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.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Characterization of trees with equal 2-domination number and domination number plus two

64%
Chellali M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
687-697
EN
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.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The k-rainbow domatic number of a graph

64%
Sheikholeslami S., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 1
129-140
EN
For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set {1,2, ...,k} such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ⋃_{u ∈ N(v)}f(u) = {1,2, ...,k} is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set ${f₁,f₂, ...,f_d}$ of k-rainbow dominating functions on G with the property that $∑_{i = 1}^d |f_i(v)| ≤ k$ for each v ∈ V(G), is called a k-rainbow dominating family (of functions) on G. The maximum number of functions in a k-rainbow dominating family on G is the k-rainbow domatic number of G, denoted by $d_{rk}(G)$. Note that $d_{r1}(G)$ is the classical domatic number d(G). In this paper we initiate the study of the k-rainbow domatic number in graphs and we present some bounds for $d_{rk}(G)$. Many of the known bounds of d(G) are immediate consequences of our results.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The total {k}-domatic number of digraphs

64%
Sheikholeslami S., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 3
461-471
EN
For a positive integer k, a total {k}-dominating function of a digraph D is a function f from the vertex set V(D) to the set {0,1,2, ...,k} such that for any vertex v ∈ V(D), the condition $∑_{u ∈ N^{ -}(v)}f(u) ≥ k$ is fulfilled, where N¯(v) consists of all vertices of D from which arcs go into v. A set ${f₁,f₂, ...,f_d}$ of total {k}-dominating functions of D with the property that $∑_{i = 1}^d f_i(v) ≤ k$ for each v ∈ V(D), is called a total {k}-dominating family (of functions) on D. The maximum number of functions in a total {k}-dominating family on D is the total {k}-domatic number of D, denoted by $dₜ^{{k}}(D)$. Note that $dₜ^{{1}}(D)$ is the classic total domatic number $dₜ(D)$. In this paper we initiate the study of the total {k}-domatic number in digraphs, and we present some bounds for $dₜ^{{k}}(D)$. Some of our results are extensions of well-know properties of the total domatic number of digraphs and the total {k}-domatic number of graphs.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Roman bondage in graphs

64%
Rad N., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
763-773
EN
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.
14
Content available remote

On the Signed (Total) K-Independence Number in Graphs

52%
Khodkar A., Samadi B., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
651-662
EN
Let G be a graph. A function f : V (G) → {−1, 1} is a signed k- independence function if the sum of its function values over any closed neighborhood is at most k − 1, where k ≥ 2. The signed k-independence number of G is the maximum weight of a signed k-independence function of G. Similarly, the signed total k-independence number of G is the maximum weight of a signed total k-independence function of G. In this paper, we present new bounds on these two parameters which improve some existing bounds.
15
Content available remote

Signed Roman Edgek-Domination in Graphs

52%
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.
16
Content available remote

New Bounds on the Signed Total Domination Number of Graphs

52%
Moghaddam S. M. H., Mojdeh D. A., Samadi B., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
467-477
EN
In this paper, we study the signed total domination number in graphs and present new sharp lower and upper bounds for this parameter. For example by making use of the classic theorem of Turán [8], we present a sharp lower bound on Kr+1-free graphs for r ≥ 2. Applying the concept of total limited packing we bound the signed total domination number of G with δ(G) ≥ 3 from above by [...] . Also, we prove that γst(T) ≤ n − 2(s − s′) for any tree T of order n, with s support vertices and s′ support vertices of degree two. Moreover, we characterize all trees attaining this bound.
17
Content available remote

The k-Rainbow Bondage Number of a Digraph

52%
Amjadi J., Mohammadi N., Sheikholeslami S. M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
261-270
EN
Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF of D. The k-rainbow bondage number brk(D) of a digraph D with maximum in-degree at least two, is the minimum cardinality of all sets A′ ⊆ A for which γrk(D−A′) > γrk(D). In this paper, we establish some bounds for the k-rainbow bondage number and determine the k-rainbow bondage number of several classes of digraphs.
18
Content available remote

The signed k-domination number of directed graphs

52%
Atapour M., Sheikholeslami S., Hajypory R., Volkmann L.
Open Mathematics
|
2010
|
tom 8
|
nr 6
1048-1057
EN
Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d D− ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N −[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $$ \sum\nolimits_{v \in V} {f(v)} $$. The signed k-domination number for a digraph D is γkS(D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γkS(D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A remark on the (2,2)-domination number

52%
Korneffel T., Meierling D., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
361-366
EN
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.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Bounds on the global offensive k-alliance number in graphs

52%
Chellali M., Haynes T., Randerath B., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
597-613
EN
Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number $γₒ^k(G)$ is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on $γₒ^k(G)$ in terms of order, maximum degree, independence number, chromatic number and minimum degree.
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ć.