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.

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.

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

Sum labellings of cycle hypergraphs

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph $_{d ̲, [d ̅]} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ \leq | e | \leq [d ̅] \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y ₁, . . ., y_{σ} \notin V$ such that $\cup y ₁, . . ., y_{σ}$ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings...

Upper bounds for the domination numbers of toroidal queens graphs

Christina M. Mynhardt (2003)

Discussiones Mathematicae Graph Theory

Similarity:

We determine upper bounds for $γ (Q n^{t})$ and $i (Q ₙ^{t})$ , the domination and independent domination numbers, respectively, of the graph $Q ₙ^{t}$ obtained from the moves of queens on the n×n chessboard drawn on the torus.

Classes of hypergraphs with sum number one

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph $ℋ_{d ̲, d ̅} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ < | e | < d ̅ \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices $w ₁, . . ., w_{σ} \notin V$ such that $ℋ \cup w ₁, . . ., w_{σ}$ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition...

On the adjacent eccentric distance sum of graphs

Halina Bielak, Katarzyna Wolska (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum, Vol. 7 (2002) no. 26, 1289–1294]. The adjacent eccentric distance sum index of the graph $G$ is defined as $ξ^{s v} (G) = \sum_{v \in V (G)} \frac{ε (v) D (v)}{d e g (v)},$ where $ε (v)$ is the eccentricity of the vertex $v$ , $d e g (v)$ is the degree of the vertex $v$ and $D (v) = \sum_{u \in V (G)} d (u, v)$ is the sum of all distances from...

Coloring grids

Ramiro de la Vega (2015)

Fundamenta Mathematicae

Similarity:

A structure $= {(A; E_{i})}_{i \in n}$ where each $E_{i}$ is an equivalence relation on A is called an n-grid if any two equivalence classes coming from distinct $E_{i}$ ’s intersect in a finite set. A function χ: A → n is an acceptable coloring if for all i ∈ n, the $χ^{- 1} (i)$ intersects each $E_{i}$ -equivalence class in a finite set. If B is a set, then the n-cube Bⁿ may be seen as an n-grid, where the equivalence classes of $E_{i}$ are the lines parallel to the ith coordinate axis. We use elementary submodels of the universe to characterize...

The Turán number of the graph $3 P_{4}$

Halina Bielak, Sebastian Kieliszek (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let $e x (n, G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_{i}$ denote a path consisting of $i$ vertices and let $m P_{i}$ denote $m$ disjoint copies of $P_{i}$ . In this paper we count $e x (n, 3 P_{4})$ .

Generalized list colourings of graphs

Mieczysław Borowiecki, Ewa Drgas-Burchardt, Peter Mihók (1995)

Discussiones Mathematicae Graph Theory

Similarity:

We prove: (1) that $c h_{P} (G) - χ_{P} (G)$ can be arbitrarily large, where $c h_{P} (G)$ and $χ_{P} (G)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.

On locating and differentiating-total domination in trees

Mustapha Chellali (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γ ₜ^{L} (G)$ and $γ ₜ^{D} (G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

On the heterochromatic number of circulant digraphs

Hortensia Galeana-Sánchez, Víctor Neumann-Lara (2004)

Discussiones Mathematicae Graph Theory

Similarity:

The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes. For any two integers s and n with 1 ≤ s ≤ n, let $D_{n, s}$ be the oriented graph such that $V (D_{n, s})$ is the set of integers mod 2n+1 and $A (D_{n, s}) = (i, j) : j - i \in 1, 2, . . ., n ∖ s . .$ In this paper we prove that $h c (D_{n, s}) \leq 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number $χ_{D} (G)$ of G. Extending these concepts to infinite graphs we prove that $D (Q_{ℵ} ₀) = 2$ and $χ_{D} (Q_{ℵ} ₀) = 3$ , where $Q_{ℵ} ₀$ denotes the hypercube of countable dimension. We also show that $χ_{D} (Q ₄) = 4$ , thereby completing the investigation of finite hypercubes with respect to $χ_{D}$ . Our...