For every pair of fixed natural numbers k > l we consider families of subgraphs of the complete graph Kn such that each graph in the family has at least k connected components while the union of any two has at most l. We show that the cardinality of such a family is at most exponential in n and determine the exact exponential growth of the largest such families for every value of k and l = 1.
Connector Families of Graphs / Gerard, Cohen; Fachini, Emanuela; Korner, Janos. - In: GRAPHS AND COMBINATORICS. - ISSN 0911-0119. - STAMPA. - 30:6(2014), pp. 1417-1425. [10.1007/s00373-013-1347-3]
Connector Families of Graphs
FACHINI, Emanuela;KORNER, JANOS
2014
Abstract
For every pair of fixed natural numbers k > l we consider families of subgraphs of the complete graph Kn such that each graph in the family has at least k connected components while the union of any two has at most l. We show that the cardinality of such a family is at most exponential in n and determine the exact exponential growth of the largest such families for every value of k and l = 1.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
