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

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

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 1 , 2 , . . . , n s . . In this paper we prove that h c ( D n , s ) 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 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 b ( mod n ) . Let n = 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 P be such that P 1 P 2 = P and P 1 P 2 = . 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 p i P 2 p i and are relatively prime to all primes q 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...

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 γ × 2 ( G ) . A function f(p) is defined, and it is shown that γ × 2 ( G ) = m i n f ( p ) , where the minimum is taken over the n-dimensional cube C = p = ( p , . . . , p ) | p i I R , 0 p i 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 γ × 2 ( G ) ( ( l n ( 1 + d ) + l n δ + 1 ) / δ ) n .

The classification of finite groups by using iteration digraphs

Uzma Ahmad, Muqadas Moeen (2016)

Czechoslovak Mathematical Journal

Similarity:

A digraph is associated with a finite group by utilizing the power map f : G G defined by f ( x ) = x k for all x G , where k is a fixed natural number. It is denoted by γ G ( n , k ) . In this paper, the generalized quaternion and 2 -groups are studied. The height structure is discussed for the generalized quaternion. The necessary and sufficient conditions on a power digraph of a 2 -group are determined for a 2 -group to be a generalized quaternion group. Further, the classification of two generated 2 -groups as abelian...

On path-quasar Ramsey numbers

Binlong Li, Bo Ning (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let G 1 and G 2 be two given graphs. The Ramsey number R ( G 1 , G 2 ) is the least integer r such that for every graph G on r vertices, either G contains a G 1 or G ¯ contains a G 2 . Parsons gave a recursive formula to determine the values of R ( P n , K 1 , m ) , where P n is a path on n vertices and K 1 , m is a star on m + 1 vertices. In this note, we study the Ramsey numbers R ( P n , K 1 F m ) , where F m is a linear forest on m vertices. We determine the exact values of R ( P n , K 1 F m ) for the cases m n and m 2 n , and for the case that F m has no odd component. Moreover, we...

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 V G is called an α-dominating set of G, if | N G ( u ) D | α d G ( u ) for all u 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.

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

A note on solvable vertex stabilizers of s -transitive graphs of prime valency

Song-Tao Guo, Hailong Hou, Yong Xu (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph X , with a group G of automorphisms of X , is said to be ( G , s ) -transitive, for some s 1 , if G is transitive on s -arcs but not on ( s + 1 ) -arcs. Let X be a connected ( G , s ) -transitive graph of prime valency p 5 , and G v the vertex stabilizer of a vertex v V ( X ) . Suppose that G v is solvable. Weiss (1974) proved that | G v | p ( p - 1 ) 2 . In this paper, we prove that G v ( p m ) × n for some positive integers m and n such that n div m and m p - 1 .

On a problem of E. Prisner concerning the biclique operator

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

The symbol K ( B , C ) denotes a directed graph with the vertex set B C for two (not necessarily disjoint) vertex sets B , C in which an arc goes from each vertex of B into each vertex of C . A subdigraph of a digraph D which has this form is called a bisimplex in D . A biclique in D is a bisimplex in D which is not a proper subgraph of any other and in which B and C . The biclique digraph C ( D ) of D is the digraph whose vertex set is the set of all bicliques in D and in which there is an arc from K ( B 1 , C 1 ) into K ( B 2 , C 2 ) ...

Distance independence in graphs

J. Louis Sewell, Peter J. Slater (2011)

Discussiones Mathematicae Graph Theory

Similarity:

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number β D ( G ) is the maximum cardinality of a D-independent set. In particular, the independence number β ( G ) = β 1 ( G ) . Along with general results we consider, in particular, the odd-independence number β O D D ( G ) where ODD = 1,3,5,....