Premium
Subcube Coverings of Random Spanning Subgraphs of the n ‐Cube
Author(s) -
Weber Karl
Publication year - 1985
Publication title -
mathematische nachrichten
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.913
H-Index - 50
eISSN - 1522-2616
pISSN - 0025-584X
DOI - 10.1002/mana.19851200128
Subject(s) - combinatorics , mathematics , social connectedness , vertex (graph theory) , cube (algebra) , discrete mathematics , random graph , minimum degree spanning tree , graph , psychology , psychotherapist
Let G(n, p) denote the probability space consisting of all spanning subgraphs g of the n ‐cube E n , and the probability is defined as P ( g ) = p M (1– p ) n 2 n –1– Mif g contains exactly M edges, 0 < M < n 2 n –1 . Erdös and Spencer investigated the connectedness of such random graphs for fixed probability p , 0 < p < 1 (cf. [1]). In this paper we study coverings of the vertex set of g ϵ G ( n , p ) by subcubes of E n being also subgraphs of g . Note the analogy between such coverings and coverings of the vertex set of spanning subgraphs of the complete graph K n by cliques.