2015/01/30 by Élie de Panafieu, de Panafieu, Élie
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1501.07775
10 pages (full format)
openalex publication_date 2015/01/30 · arxiv created 2015/11/05 · arxiv updated 2015/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We analyze a general model of weighted graphs, introduced by de Panafieu and Ravelomanana (2014) and similar to the "inhomogeneous graph model" of Söderberg (2002). Each vertex receives a "type" among a set of q possibilities as well as a "weight" corresponding to this type, and each edge is weighted according to the types of the vertices it links. The weight of the graph is then the product of the weights of its vertices and edges. We investigate the sum of the weights of such graphs and prove that when the number of edges is small, almost all of them contain no component with more than one cycle. Those results allow us to give a new proof in a more general setting of a theorem of Wright (1961) on the enumeration of properly colored graphs. We also discuss applications related to social networks.