102,029 research outputs found
PERFECT COUPLES OF GRAPHS
No full textWe, generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graph G with a probability distribution P on its vertex set. For any fixed P it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those of G and its complement GBAR iff G is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality
Different capacities of a digraph
No full textThe Shannon capacity of every induced subgraph of a perfect graph equals its clique number. However, for the co--normal powers of an odd cycle the super--multiplicativity of the clique number makes the determination of capacity one of the hardest problems in combinatorics. We study the asymptotic growth of induced subgraphs of some particular type in powers of a fixed graph. In case of a simple graph we investigate the asymptotic growth in its co--normal powers of the largest induced subgraph on which non--adjacency is an equivalence relation, (equivalence graphs). For directed graphs we introduce a natural generalization of the co--normal product called Sperner product and analyze the directed version of the problem of asymptotic growth both for the clique number (Sperner capacity) and for induced subgraphs corresponding to equivalence--subgraphs with a particular direction of their edges, called waterfalls
Reuseable memories in the light of the old arbitrarily varying and a new outputwise varying channel theory
No full textAhlswede R, Simonyi G. Reuseable memories in the light of the old arbitrarily varying and a new outputwise varying channel theory. IEEE transactions on information theory. 1991;37(4):1143-1150
Graph-different permutations
No full textFor a finite graph G whose vertices are different natural numbers we call two infinite permutations of the natural numbers G-different if they have two adjacent vertices of G somewhere in the same position. The maximum number of pairwise G-different permutations of the naturals is always finite. We study this maximum as a graph invariant and relate it to a problem of the first two authors on colliding permutations. An improvement on the lower bound for the maximum number of pairwise colliding permutations is obtained. © 2008 Society for Industrial and Applied Mathematics
On the optimal structure of recovering set pairs in lattices: the sandglass conjecture
No full textAhlswede R, Simonyi G. On the optimal structure of recovering set pairs in lattices: the sandglass conjecture. Discrete Mathematics. 1994;128(1-3):389-394.We present a conjecture concerning the optimal structure of a subset pair satisfying two dual requirements in a lattice that can be derived as the product of k finite length chains. The conjecture is proved for k=2
Adaptación a la alimentación natural de Gallotia simonyi (Sauria, Lacertidae) en cautividad
No full textEl lagarto gigante de El Hierro (Gallotia simonyi) es un lacértido endémico seriamente amenazado de extinción, y objeto de un plan de recuperación que consiste en la cría en cautividad y en la futura reintroducción en un nuevo hábitat. G. simonyi es una especie principalmente herbívora cuya dieta en cautividad no guardaba relación con los alimentos presentes en el área propuesta para la reintroducción. Se ha llevado a cabo una experiencia consistente en cambiar los hábitos alimenticios de un grupo de individuos de G. simonyi mantenidos en cautividad en el Centro de Recuperación del Lagarto Gigante de El Hierro. Se estableció un período de adaptación controlado para comprobar si consumían los elementos vegetales existentes en el área susceptible de ser colonizada.2061971
Vulnerabilidad de Gallotia simonyi (Sauria, Lacertidae) ante depredadores aéreos: influencia del tamaño corporal.
No full textLa predación por parte de las aves, especialmente por parte del cernícalo vulgar (Falco tinnunculus), muy abundante en la isla de El Hierro (Islas Canarias), es uno de los factores a tener en cuenta de cara a la reintroducción de Gallotia simonyi. En el presente trabajo evaluamos la presión de predación aérea potencial sobre G simonyi analizando la dieta de F. tinnunculus, y la tasa depredación estimada mediante modelos de plastilina. A su vez, tratamos de saber si existe una limitación del tamaño de la presa en la predación aérea F. tinnunculus parece ser el único potencial predador aéreo de G. simonyi, formando los lagartos parte importante de su dieta, aunque la presión depredación no sea alta.1481391
- …
