Signed domination and signed domatic numbers of digraphs

Lutz Volkmann

Displaying similar documents to “Signed domination and signed domatic numbers of digraphs”

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

Self-diclique circulant digraphs

Marietjie Frick, Bernardo Llano, Rita Zuazua (2015)

Mathematica Bohemica

Similarity:

We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let $D = (V, A)$ be a reflexive digraph (or network). Consider $X$ and $Y$ (not necessarily disjoint) nonempty subsets of vertices (or nodes) of $D$ . A disimplex $K (X, Y)$ of $D$ is...

A note on a conjecture on niche hypergraphs

Pawaton Kaemawichanurat, Thiradet Jiarasuksakun (2019)

Czechoslovak Mathematical Journal

Similarity:

For a digraph $D$ , the niche hypergraph $N ℋ (D)$ of $D$ is the hypergraph having the same set of vertices as $D$ and the set of hyperedges $E (N ℋ (D)) = {e \subseteq V (D) : | e | \geq 2$ and there exists a vertex $v$ such that $e = N_{D}^{-} (v)$ or $e = N_{D}^{+} (v)}$ . A digraph is said to be acyclic if it has no directed cycle as a subdigraph. For a given hypergraph $ℋ$ , the niche number $\hat{n} (ℋ)$ is the smallest integer such that $ℋ$ together with $\hat{n} (ℋ)$ isolated vertices is the niche hypergraph of an acyclic digraph. C. Garske, M. Sonntag and H. M. Teichert (2016) conjectured that for a linear...

Majority choosability of 1-planar digraph

Weihao Xia, Jihui Wang, Jiansheng Cai (2023)

Czechoslovak Mathematical Journal

Similarity:

A majority coloring of a digraph $D$ with $k$ colors is an assignment $π : V (D) \to {1, 2, \dots, k}$ such that for every $v \in V (D)$ we have $π (w) = π (v)$ for at most half of all out-neighbors $w \in N^{+} (v)$ . A digraph $D$ is majority $k$ -choosable if for any assignment of lists of colors of size $k$ to the vertices, there is a majority coloring of $D$ from these lists. We prove that if $U (D)$ is a 1-planar graph without a 4-cycle, then $D$ is majority 3-choosable. And we also prove that every NIC-planar digraph is majority 3-choosable.

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

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 the tree structure of the power digraphs modulo $n$

Amplify Sawkmie, Madan Mohan Singh (2015)

Czechoslovak Mathematical Journal

Similarity:

For any two positive integers $n$ and $k \geq 2$ , let $G (n, k)$ be a digraph whose set of vertices is ${0, 1, ..., n - 1}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^{k} \equiv b (mod n)$ . Let $n = \prod_{i = 1}^{r} p_{i}^{e_{i}}$ be the prime factorization of $n$ . Let $P$ be the set of all primes dividing $n$ and let $P_{1}, P_{2} \subseteq P$ be such that $P_{1} \cup P_{2} = P$ and $P_{1} \cap P_{2} = \emptyset$ . A fundamental constituent of $G (n, k)$ , denoted by $G_{P_{2}}^{*} (n, k)$ , is a subdigraph of $G (n, k)$ induced on the set of vertices which are multiples of $\prod_{p_{i} \in P_{2}} p_{i}$ and are relatively prime to all primes $q \in P_{1}$ . L. Somer and M. Křížek proved that the trees attached...

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

A note on the double Roman domination number of graphs

Xue-Gang Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

For a graph $G = (V, E)$ , a double Roman dominating function is a function $f : V \to {0, 1, 2, 3}$ having the property that if $f (v) = 0$ , then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f (w) = 3$ , and if $f (v) = 1$ , then the vertex $v$ must have at least one neighbor with $f (w) \geq 2$ . The weight of a double Roman dominating function $f$ is the sum $f (V) = \sum_{v \in V} f (v)$ . The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by $γ_{dR} (G)$ . In this paper, we establish a new...

On upper bounds for total $k$ -domination number via the probabilistic method

Saylí Sigarreta, Saylé Sigarreta, Hugo Cruz-Suárez (2023)

Kybernetika

Similarity:

For a fixed positive integer $k$ and $G = (V, E)$ a connected graph of order $n$ , whose minimum vertex degree is at least $k$ , a set $S \subseteq V$ is a total $k$ -dominating set, also known as a $k$ -tuple total dominating set, if every vertex $v \in V$ has at least $k$ neighbors in $S$ . The minimum size of a total $k$ -dominating set for $G$ is called the total $k$ -domination number of $G$ , denoted by $γ_{k t} (G)$ . The total $k$ -domination problem is to determine a minimum total $k$ -dominating set of $G$ . Since the exact problem is in general quite difficult...

On short cycles in triangle-free oriented graphs

Yurong Ji, Shufei Wu, Hui Song (2018)

Czechoslovak Mathematical Journal

Similarity:

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $⌈ n / d ⌉$ . In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $α_{0}$ is the smallest real such that every $n$ -vertex digraph with minimum outdegree at least $α_{0} n$ contains a directed triangle. Let $ϵ < (3 - 2 α_{0}) / (4 - 2 α_{0})$ be a positive real. We show that if $D$ is an oriented graph...

Characterizing finite groups whose enhanced power graphs have universal vertices

David G. Costanzo, Mark L. Lewis, Stefano Schmidt, Eyob Tsegaye, Gabe Udell (2024)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group and construct a graph $Δ (G)$ by taking $G ∖ {1}$ as the vertex set of $Δ (G)$ and by drawing an edge between two vertices $x$ and $y$ if $〈 x, y 〉$ is cyclic. Let $K (G)$ be the set consisting of the universal vertices of $Δ (G)$ along the identity element. For a solvable group $G$ , we present a necessary and sufficient condition for $K (G)$ to be nontrivial. We also develop a connection between $Δ (G)$ and $K (G)$ when $| G |$ is divisible by two distinct primes and the diameter of $Δ (G)$ is 2.