Affordable Access

Publisher Website

On [formula omitted]-tuple domination of random graphs

Authors
Journal
Applied Mathematics Letters
0893-9659
Publisher
Elsevier
Publication Date
Volume
22
Issue
10
Identifiers
DOI: 10.1016/j.aml.2009.02.004
Keywords
  • Domination
  • Random Graph
  • [Formula Omitted]-Tuple Domination

Abstract

Abstract In graph G = ( V , E ) , a vertex set D ⊆ V is called a domination set if any vertex u ∈ V ∖ D is connected to at least one vertex in D . Generally, for any natural number k , the k -tuple domination set D is a vertex set such that any vertex u ∈ V ∖ D is connected to at least k vertices in D . The k -tuple domination number is the minimum size of k -tuple domination sets. It is known that the 1-tuple domination number (i.e. domination number) of classical random graphs G ( n , p ) with fixed p ∈ ( 0 , 1 ) asymptotically almost surely ( a . a . s . ) has a two-point concentration [B. Wieland, A.P. Godbole, On the domination number of a random graph, Electron. J. Combin. 8 (2001) R37]. In this work, we prove that the 2-tuple domination number of G ( n , p ) with fixed p ∈ ( 0 , 1 ) a . a . s . has a two-point concentration.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

[formula omitted]-tuple total domination in graphs

on Discrete Applied Mathematics Jan 01, 2010

The upper bound on [formula omitted]-tuple dominat...

on European Journal of Combinator... Jan 01, 2008

Proof of a conjecture on [formula omitted]-tuple d...

on Applied Mathematics Letters Jan 01, 2008

New bounds on the [formula omitted]-domination num...

on Applied Mathematics Letters Jan 01, 2007
More articles like this..