The k-rainbow domatic number of a graph

Seyyed Mahmoud Sheikholeslami; Lutz Volkmann

Displaying similar documents to “The k-rainbow domatic number of a graph”

Full domination in graphs

Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang (2001)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v in a graph G, let there be associated a subgraph $H_{v}$ of G. The vertex v is said to dominate $H_{v}$ as well as dominate each vertex and edge of $H_{v}$ . A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number $γ_{F H} (G)$ . A full dominating set of G of cardinality $γ_{F H} (G)$ is called a $γ_{F H}$ -set of G. We study three types of full domination in...

On locating-domination in graphs

Mustapha Chellali, Malika Mimouni, Peter J. Slater (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number $γ_{L} (G)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, $Γ_{L} (G)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on $Γ_{L} (G)$ and $γ_{L} (G)$ .

The total {k}-domatic number of digraphs

Seyed Mahmoud Sheikholeslami, Lutz Volkmann (2012)

Discussiones Mathematicae Graph Theory

Similarity:

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 $\sum_{u \in N^{-} (v)} f (u) \geq 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 $\sum_{i = 1}^{d} f_{i} (v) \leq 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...

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s d_{γ} (G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 \leq s d_{γ} (G) \leq 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

Similarity:

We consider, for a positive integer $k$ , induced subgraphs in which each component has order at most $k$ . Such a subgraph is said to be $k$ -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$ -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for...

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{\times k} (G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $| N_{G} [v] \cap S | \geq k$ . Also the total k-domination number $γ_{\times k, t} (G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $| N_{G} (v) \cap S | \geq k$ . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number $s d_{γ} (G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

On double domination in graphs

Jochen Harant, Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{\times 2} (G)$ . A function f(p) is defined, and it is shown that $γ_{\times 2} (G) = m i n f (p)$ , where the minimum is taken over the n-dimensional cube $C ⁿ = p = (p ₁, . . ., p ₙ) | p_{i} \in I R, 0 \leq p_{i} \leq 1, i = 1, . . ., n$ . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_{\times 2} (G) \leq ((l n (1 + d) + l n δ + 1) / δ) n$ .

Some remarks on α-domination

Franz Dahme, Dieter Rautenbach, Lutz Volkmann (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let α ∈ (0,1) and let $G = (V_{G}, E_{G}$ ) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D \subseteq V_{G}$ is called an α-dominating set of G, if $| N_{G} (u) \cap D | \geq α d_{G} (u)$ for all $u \in V_{G} ∖ D$ . We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.

Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás, Zsolt Tuza, Vitaly Voloshin (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = E₁,...,Eₘ, together with integers $s_{i}$ and $t_{i}$ satisfying $1 \leq s_{i} \leq t_{i} \leq | E_{i} |$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_{i}$ satisfies $s_{i} \leq | φ (E_{i}) | \leq t_{i}$ . The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a “host graph”, that means a graph G on the same vertex set X as ℋ, such that each $E_{i}$ induces a connected subgraph in G....

Roman bondage in graphs

Nader Jafari Rad, Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

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)) = \sum_{u \in 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)...

Secure domination and secure total domination in graphs

William F. Klostermeyer, Christina M. Mynhardt (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X - x) \cup u$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_{s} (G) (γ_{s t} (G))$ . We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_{s t} (G) \leq γ_{s} (G)$ . We also show that $γ_{s t} (G)$ is at most twice the clique covering...

Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles

Donghan Zhang (2022)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V (G), E (G))$ be a simple graph and $E_{G} (v)$ denote the set of edges incident with a vertex $v$ . A neighbor sum distinguishing (NSD) total coloring $φ$ of $G$ is a proper total coloring of $G$ such that $\sum_{z \in E_{G} (u) \cup {u}} φ (z) \neq \sum_{z \in E_{G} (v) \cup {v}} φ (z)$ for each edge $u v \in E (G)$ . Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree $Δ$ admits an NSD total $(Δ + 3)$ -coloring. We prove that the list version of this conjecture holds for any IC-planar graph with $Δ \geq 11$ but without $5$ -cycles by applying the Combinatorial Nullstellensatz.

On $g_{c}$ -colorings of nearly bipartite graphs

Yuzhuo Zhang, Xia Zhang (2018)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a simple graph, let $d (v)$ denote the degree of a vertex $v$ and let $g$ be a nonnegative integer function on $V (G)$ with $0 \leq g (v) \leq d (v)$ for each vertex $v \in V (G)$ . A $g_{c}$ -coloring of $G$ is an edge coloring such that for each vertex $v \in V (G)$ and each color $c$ , there are at least $g (v)$ edges colored $c$ incident with $v$ . The $g_{c}$ -chromatic index of $G$ , denoted by $χ_{g_{c}}^{'} (G)$ , is the maximum number of colors such that a $g_{c}$ -coloring of $G$ exists. Any simple graph $G$ has the $g_{c}$ -chromatic index equal to $δ_{g} (G)$ or $δ_{g} (G) - 1$ , where $δ_{g} (G) = {min}_{v \in V (G)} ⌊ d (v) / g (v) ⌋$ . A graph $G$ is nearly bipartite,...

The sum number of d-partite complete hypergraphs

Hanns-Martin Teichert (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph $⁺_{d} (S) = (V,)$ , where V = S and $= v ₁, . . ., v_{d} : (i \neq j \Rightarrow v_{i} \neq v_{j}) \land \sum_{i = 1}^{d} v_{i} \in S$ . For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $w ₁, . . ., w_{σ} \notin V$ such that $\cup w ₁, . . ., w_{σ}$ is a sum hypergraph. In this paper, we prove $σ (_{n ₁, . . ., n_{d}}^{d}) = 1 + \sum_{i = 1}^{d} (n_{i} - 1) + m i n 0, ⌈ 1 / 2 (\sum_{i = 1}^{d - 1} (n_{i} - 1) - n_{d}) ⌉$ , where $_{n ₁, . . ., n_{d}}^{d}$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

Indestructible colourings and rainbow Ramsey theorems

Lajos Soukup (2009)

Fundamenta Mathematicae

Similarity:

We show that if a colouring c establishes ω₂ ↛ [(ω₁:ω)]² then c establishes this negative partition relation in each Cohen-generic extension of the ground model, i.e. this property of c is Cohen-indestructible. This result yields a negative answer to a question of Erdős and Hajnal: it is consistent that GCH holds and there is a colouring c:[ω₂]² → 2 establishing ω₂ ↛ [(ω₁:ω)]₂ such that some colouring g:[ω₁]² → 2 does not embed into c. It is also consistent that $2^{ω ₁}$ is arbitrarily large,...

Signed domination and signed domatic numbers of digraphs

Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

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 $\sum_{x \in N ¯ [v]} f (x) \geq 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...

Turán number of two vertex-disjoint copies of cliques

Caiyun Hu (2024)

Czechoslovak Mathematical Journal

Similarity:

The Turán number of a given graph $H$ , denoted by $ex (n, H)$ , is the maximum number of edges in an $H$ -free graph on $n$ vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number $ex (n, K_{p} \cup K_{q}$ ) of a vertex-disjoint union of cliques $K_{p}$ and $K_{q}$ for all values of $n$ .