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). (Intervento presentato al convegno MM - AMS SPECIAL SESSION ON DISCRETE GEOMETRY AND ALGEBRAIC COMBINATORICS tenutosi a San Diego, USA nel 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
