Displaying similar documents to “Full domination in graphs”

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

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

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 ) = v V ( G ) ε ( 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 ) = u V ( G ) d ( u , v ) is the sum of all distances from...

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 s d γ ( G ) 3 for any graph G. We give a counterexample to this conjecture. On the other hand,...

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

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

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

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang An, Liming Xiong, Runli Tian (2015)

Czechoslovak Mathematical Journal

Similarity:

An edge of G is singular if it does not lie on any triangle of G ; otherwise, it is non-singular. A vertex u of a graph G is called locally connected if the induced subgraph G [ N ( u ) ] by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph G of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex v of degree at least 3 in G , there is a nonnegative integer s such...

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

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

Some properties of generalized distance eigenvalues of graphs

Yuzheng Ma, Yan Ling Shao (2024)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple connected graph with vertex set V ( G ) = { v 1 , v 2 , , v n } and edge set E ( G ) , and let d v i be the degree of the vertex v i . Let D ( G ) be the distance matrix and let T r ( G ) be the diagonal matrix of the vertex transmissions of G . The generalized distance matrix of G is defined as D α ( G ) = α T r ( G ) + ( 1 - α ) D ( G ) , where 0 α 1 . Let λ 1 ( D α ( G ) ) λ 2 ( D α ( G ) ) ... λ n ( D α ( G ) ) be the generalized distance eigenvalues of G , and let k be an integer with 1 k n . We denote by S k ( D α ( G ) ) = λ 1 ( D α ( G ) ) + λ 2 ( D α ( G ) ) + ... + λ k ( D α ( G ) ) the sum of the k largest generalized distance eigenvalues. The generalized distance spread of a graph G is defined as D α S ( G ) = λ 1 ( D α ( G ) ) - λ n ( D α ( G ) ) ....

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

The vertex detour hull number of a graph

A.P. Santhakumaran, S.V. Ullas Chandran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), I D [ S ] = x , y S I D [ x , y ] . A set S of vertices is a detour convex set if I D [ S ] = S . The detour convex hull [ S ] D is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

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

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 .

Several quantitative characterizations of some specific groups

A. Mohammadzadeh, Ali Reza Moghaddamfar (2017)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let G be a finite group and let π ( G ) = { p 1 , p 2 , ... , p k } be the set of prime divisors of | G | for which p 1 < p 2 < < p k . The Gruenberg-Kegel graph of G , denoted GK ( G ) , is defined as follows: its vertex set is π ( G ) and two different vertices p i and p j are adjacent by an edge if and only if G contains an element of order p i p j . The degree of a vertex p i in GK ( G ) is denoted by d G ( p i ) and the k -tuple D ( G ) = ( d G ( p 1 ) , d G ( p 2 ) , ... , d G ( p k ) ) is said to be the degree pattern of G . Moreover, if ω π ( G ) is the vertex set of a connected component of GK ( G ) , then the largest ω -number which divides | G | , is...