For every pair of xed 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 / G., Cohen; Fachini, Emanuela; Korner, Janos. - ELETTRONICO. - (2013). ( MM - AMS SPECIAL SESSION ON DISCRETE GEOMETRY AND ALGEBRAIC COMBINATORICS San Diego, USA January, 9-12, 2013).
Connector Families of Graphs
FACHINI, Emanuela;KORNER, JANOS
2013
Abstract
For every pair of xed 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.
