Connected domination in random graphs

Gábor Bacsó (), József Túri () and Zsolt Tuza ()
Additional contact information
Gábor Bacsó: Institute for Computer Science and Control
József Túri: University of Miskolc
Zsolt Tuza: Alfréd Rényi Institute of Mathematics

Indian Journal of Pure and Applied Mathematics, 2023, vol. 54, issue 2, 439-446

Abstract: Abstract Given a graph $$G=(V,E)$$ G = ( V , E ) , a dominating set is a subset $$D\subseteq V$$ D ⊆ V such that every vertex in $$V\setminus D$$ V \ D is adjacent with at least one vertex in D. The domination number of G, denoted by $$\gamma (G)$$ γ ( G ) , is the minimum cardinality of a dominating set in G. Assuming that the graph $$G=(V,E)$$ G = ( V , E ) is connected, a subset $$D\subseteq V$$ D ⊆ V is said to be a connected dominating set if it is a dominating set and the subgraph G[D] induced by D is connected. The minimum cardinality of a connected dominating set is termed the connected domination number, denoted by $$\gamma _c(G)$$ γ c ( G ) . Comparing $$\gamma (G)$$ γ ( G ) and $$\gamma _c(G)$$ γ c ( G ) for a random graph with constant edge probability p, we obtain that the two parameters are asymptotically equal with probability tending to 1 as the number of vertices gets large. We also consider nonconstant edge probability $$p_n$$ p n tending to zero (where n is the number of vertices). Among other results, we extend an asymptotic formula of Gilbert on the probability of connectivity.

Keywords: Random graph; Dominating set; Domination number; Connected dominating set; 05C80; 05C69 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13226-022-00265-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:indpam:v:54:y:2023:i:2:d:10.1007_s13226-022-00265-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/13226

DOI: 10.1007/s13226-022-00265-2

Access Statistics for this article

Indian Journal of Pure and Applied Mathematics is currently edited by Nidhi Chandhoke

More articles in Indian Journal of Pure and Applied Mathematics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().