Currently displaying 1 – 11 of 11

Showing per page

Order by Relevance | Title | Year of publication

A note on the double Roman domination number of graphs

Xue-Gang Chen — 2020

Czechoslovak Mathematical Journal

For a graph G = ( V , E ) , a double Roman dominating function is a function f : V { 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 ) 2 . The weight of a double Roman dominating function f is the sum f ( V ) = v 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 upper bound...

Connected domination critical graphs with respect to relative complements

Xue-Gang ChenLiang Sun — 2006

Czechoslovak Mathematical Journal

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G . The minimum number of vertices in a connected dominating set of G is called the connected domination number of G , and is denoted by γ c ( G ) . Let G be a spanning subgraph of K s , s and let H be the complement of G relative to K s , s ; that is, K s , s = G H is a factorization of K s , s . The graph G is k - γ c -critical relative to K s , s if γ c ( G ) = k and γ c ( G + e ) < k for each edge e E ( H ) . First, we discuss some classes of graphs whether they are γ c -critical relative...

Trees with equal total domination and total restrained domination numbers

Xue-Gang ChenWai Chee ShiuHong-Yu Chen — 2008

Discussiones Mathematicae Graph Theory

For a graph G = (V,E), a set S ⊆ V(G) is a total dominating set if it is dominating and both ⟨S⟩ has no isolated vertices. The cardinality of a minimum total dominating set in G is the total domination number. A set S ⊆ V(G) is a total restrained dominating set if it is total dominating and ⟨V(G)-S⟩ has no isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. We characterize all trees for which total domination and total restrained...

On total restrained domination in graphs

De-xiang MaXue-Gang ChenLiang Sun — 2005

Czechoslovak Mathematical Journal

In this paper we initiate the study of total restrained domination in graphs. Let G = ( V , E ) be a graph. A total restrained dominating set is a set S V where every vertex in V - S is adjacent to a vertex in S as well as to another vertex in V - S , and every vertex in S is adjacent to another vertex in S . The total restrained domination number of G , denoted by γ r t ( G ) , is the smallest cardinality of a total restrained dominating set of G . First, some exact values and sharp bounds for γ r t ( G ) are given in Section 2. Then the Nordhaus-Gaddum-type...

An upper bound for domination number of 5-regular graphs

Hua Ming XingLiang SunXue-Gang Chen — 2006

Czechoslovak Mathematical Journal

Let G = ( V , E ) be a simple graph. A subset S V is a dominating set of G , if for any vertex u V - S , there exists a vertex v S such that u v E . The domination number, denoted by γ ( G ) , is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ ( G ) 5 14 n .

On signed majority total domination in graphs

Hua Ming XingLiang SunXue-Gang Chen — 2005

Czechoslovak Mathematical Journal

We initiate the study of signed majority total domination in graphs. Let G = ( V , E ) be a simple graph. For any real valued function f V and S V , let f ( S ) = v S f ( v ) . A signed majority total dominating function is a function f V { - 1 , 1 } such that f ( N ( v ) ) 1 for at least a half of the vertices v V . The signed majority total domination number of a graph G is γ m a j t ( G ) = min { f ( V ) f is a signed majority total dominating function on G } . We research some properties of the signed majority total domination number of a graph G and obtain a few lower bounds of γ m a j t ( G ) .

On signed distance- k -domination in graphs

Hua Ming XingLiang SunXue-Gang Chen — 2006

Czechoslovak Mathematical Journal

The signed distance- k -domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G , the open k -neighborhood of v , denoted by N k ( v ) , is the set N k ( v ) = { u u v and d ( u , v ) k } . N k [ v ] = N k ( v ) { v } is the closed k -neighborhood of v . A function f V { - 1 , 1 } is a signed distance- k -dominating function of G , if for every vertex v V , f ( N k [ v ] ) = u N k [ v ] f ( u ) 1 . The signed distance- k -domination number, denoted by γ k , s ( G ) , is the minimum weight of a signed distance- k -dominating function on G . The values of γ 2 , s ( G ) are found for graphs with small diameter,...

On the total restrained domination number of direct products of graphs

Wai Chee ShiuHong-Yu ChenXue-Gang ChenPak Kiu Sun — 2012

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V∖S is adjacent to a vertex in S as well as to another vertex in V∖S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by γ r t ( G ) , is the smallest cardinality of a total restrained dominating set of G. We determine lower and upper bounds on the total restrained domination number of the direct product of two graphs. Also, we show that these bounds...

A note on the independent domination number of subset graph

Xue-Gang ChenDe-xiang MaHua Ming XingLiang Sun — 2005

Czechoslovak Mathematical Journal

The independent domination number i ( G ) (independent number β ( G ) ) is the minimum (maximum) cardinality among all maximal independent sets of G . Haviland (1995) conjectured that any connected regular graph G of order n and degree δ 1 2 n satisfies i ( G ) 2 n 3 δ 1 2 δ . For 1 k l m , the subset graph S m ( k , l ) is the bipartite graph whose vertices are the k - and l -subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i ( S m ( k , l ) ) and prove that...

Page 1

Download Results (CSV)