Currently displaying 1 – 20 of 40

Showing per page

Order by Relevance | Title | Year of publication

Signed k-independence in graphs

Lutz Volkmann — 2014

Open Mathematics

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...

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

Lutz Volkmann — 2015

Discussiones Mathematicae Graph Theory

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...

Bounds on the Signed 2-Independence Number in Graphs

Lutz Volkmann — 2013

Discussiones Mathematicae Graph Theory

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),...

Signed domination and signed domatic numbers of digraphs

Lutz Volkmann — 2011

Discussiones Mathematicae Graph Theory

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...

Connected global offensive k-alliances in graphs

Lutz Volkmann — 2011

Discussiones Mathematicae Graph Theory

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...

A bound on the k -domination number of a graph

Lutz Volkmann — 2010

Czechoslovak Mathematical Journal

Let G be a graph with vertex set V ( G ) , and let k 1 be an integer. A subset D V ( G ) is called a if every vertex v V ( G ) - D has at least k neighbors in D . The k -domination number γ k ( G ) of G is the minimum cardinality of a k -dominating set in G . If G is a graph with minimum degree δ ( G ) k + 1 , then we prove that γ k + 1 ( G ) | V ( G ) | + γ k ( G ) 2 . In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

The Signed Total Roman k-Domatic Number Of A Graph

Lutz Volkmann — 2017

Discussiones Mathematicae Graph Theory

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...

Signed Total Roman Domination in Digraphs

Lutz Volkmann — 2017

Discussiones Mathematicae Graph Theory

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...

On perfect and unique maximum independent sets in graphs

Lutz Volkmann — 2004

Mathematica Bohemica

A perfect independent set I of a graph G is defined to be an independent set with the property that any vertex not in I has at least two neighbors in I . For a nonnegative integer k , a subset I of the vertex set V ( G ) of a graph G is said to be k -independent, if I is independent and every independent subset I ' of G with | I ' | | I | - ( k - 1 ) is a subset of I . A set I of vertices of G is a super k -independent set of G if I is k -independent in the graph G [ I , V ( G ) - I ] , where G [ I , V ( G ) - I ] is the bipartite graph obtained from G by deleting all edges...

A lower bound for the irredundance number of trees

Michael PoschenLutz Volkmann — 2006

Discussiones Mathematicae Graph Theory

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. ...

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

Adriana HansbergLutz Volkmann — 2007

Discussiones Mathematicae Graph Theory

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...

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

Mustapha ChellaliLutz Volkmann — 2011

Discussiones Mathematicae Graph Theory

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.

The k -domatic number of a graph

Karsten KämmerlingLutz Volkmann — 2009

Czechoslovak Mathematical Journal

Let k be a positive integer, and let G be a simple graph with vertex set V ( G ) . A of the graph G is a subset D of V ( G ) such that every vertex of V ( G ) - D is adjacent to at least k vertices in D . A of G is a partition of V ( G ) into k -dominating sets. The maximum number of dominating sets in a k -domatic partition of G is called the d k ( G ) . In this paper, we present upper and lower bounds for the k -domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical...

Cycles with a given number of vertices from each partite set in regular multipartite tournaments

Lutz VolkmannStefan Winzen — 2006

Czechoslovak Mathematical Journal

If x is a vertex of a digraph D , then we denote by d + ( x ) and d - ( x ) the outdegree and the indegree of x , respectively. A digraph D is called regular, if there is a number p such that d + ( x ) = d - ( x ) = p for all vertices x of D . A c -partite tournament is an orientation of a complete c -partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether...

On the order of certain close to regular graphs without a matching of given size

Sabine KlinkenbergLutz Volkmann — 2007

Czechoslovak Mathematical Journal

A graph G is a { d , d + k } -graph, if one vertex has degree d + k and the remaining vertices of G have degree d . In the special case of k = 0 , the graph G is d -regular. Let k , p 0 and d , n 1 be integers such that n and p are of the same parity. If G is a connected { d , d + k } -graph of order n without a matching M of size 2 | M | = n - p , then we show in this paper the following: If d = 2 , then k 2 ( p + 2 ) and (i) n k + p + 6 . If d 3 is odd and t an integer with 1 t p + 2 , then (ii) n d + k + 1 for k d ( p + 2 ) , (iii) n d ( p + 3 ) + 2 t + 1 for d ( p + 2 - t ) + t k d ( p + 3 - t ) + t - 3 , (iv) n d ( p + 3 ) + 2 p + 7 for k p . If d 4 is even, then (v) n d + k + 2 - η for k d ( p + 3 ) + p + 4 + η , (vi) n d + k + p + 2 - 2 t = d ( p + 4 ) + p + 6 for k = d ( p + 3 ) + 4 + 2 t and p 1 , (vii) n d + k + p + 4 for...

Page 1 Next

Download Results (CSV)