Aspects topologiques de la séperation dans les graphes infinis. II.
Associative graph products and their independence, domination and coloring numbers
Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity of a graph...
Associative Products of Graphs.
Asteroidal Quadruples in non Rooted Path Graphs
A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed...
Asymptotic bounds for bipartite Ramsey numbers.
Asymptotic comparison of two constructions for large digraphs of given degree and diameter
We compare the asymptotic growth of the order of the digraphs arising from a construction of Comellas and Fiol when applied to Faber-Moore digraphs versus plainly the Faber-Moore digraphs for the corresponding degree and diameter.
Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums.
Asymptotic enumeration of labelled graphs by genus.
Asymptotic equipartition properties for simple hierarchical and networked structures
We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...
Asymptotic equipartition properties for simple hierarchical and networked structures
We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...
Asymptotic evolution of acyclic random mappings.
Asymptotic expansions for the coefficients of analytic generating functions.
Asymptotic properties of random graphs [Book]
Asymptotic spectral analysis of generalized Erdős-Rényi random graphs
Motivated by the Watts-Strogatz model for a complex network, we introduce a generalization of the Erdős-Rényi random graph. We derive a combinatorial formula for the moment sequence of its spectral distribution in the sparse limit.
Asymptotic spectral analysis of growing graphs: odd graphs and spidernets
Two new examples are given for illustrating the method of quantum decomposition in the asymptotic spectral analysis for a growing family of graphs. The odd graphs form a growing family of distance-regular graphs and the two-sided Rayleigh distribution appears in the limit of vacuum spectral distribution of the adjacency matrix. For a spidernet as well as for a growing family of spidernets the vacuum distribution of the adjacency matrix is the free Meixner law. These distributions are calculated...
Asymptotic spectral distributions of distance k-graphs of large-dimensional hypercubes
We derive the asymptotic spectral distribution of the distance k-graph of N-dimensional hypercube as N → ∞.
Asymptotic spectral distributions of distance-k graphs of Cartesian product graphs
Let G be a finite connected graph on two or more vertices, and the distance-k graph of the N-fold Cartesian power of G. For a fixed k ≥ 1, we obtain explicitly the large N limit of the spectral distribution (the eigenvalue distribution of the adjacency matrix) of . The limit distribution is described in terms of the Hermite polynomials. The proof is based on asymptotic combinatorics along with quantum probability theory.
Asymptotical estimation of some characteristics of finite graphs
Asymptotically optimal tree-packings in regular graphs.
Asymptotics for rooted bipartite planar maps and scaling limits of two-type spatial trees.