3 citations · 9 across the 20 of their papers we have counts for
9 papers · 1 filter
Exact enumeration of satisfiable 2-SAT formulae
Sergey Dovgal, Élie de Panafieu, Vlady Ravelomanana
We obtain exact expressions counting the satisfiable 2-SAT formulae and describe the structure of associated implication digraphs. Our approach is based on generating function mani…
Generating Functions of Some Families of Directed Uniform Hypergraphs
Vonjy Rasendrahasina, Vlady Ravelomanana
In this paper, we count acyclic and strongly connected uniform directed labeled hypergraphs. For these combinatorial structures, we introduce a specific generating function allowin…
Cycles of given lengths in unicyclic components in sparse random graphs
Marc Noy, Vonjy Rasendrahasina, Vlady Ravelomanana +1
Let be subset of and let be the number of cycles belonging to unicyclic components whose length is in in the random graph . We find…
Threshold functions for small subgraphs in simple graphs and multigraphs
Gwendal Collet, Élie de Panafieu, Danièle Gardy +2
We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce th…
Threshold functions for small subgraphs: an analytic approach
Gwendal Collet, Élie de Panafieu, Danièle Gardy +2
We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, including the case of constrained degrees. Our approach relies heavily on…
Shifting the Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints
Sergey Dovgal, Vlady Ravelomanana
We show that by restricting the degrees of the vertices of a graph to an arbitrary set \( Δ\), the threshold point of the phase transition for a random graph with ve…