5 papers
Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths
Ararat Harutyunyan, Colin McDiarmid, Gil Puig i Surroca
Given a digraph , we denote by the maximum size of an acyclic set of (i.e. a set of vertices which induces a subdigraph with no directed cycles), and by $\vecχ(D)…
Note on edge expansion and modularity in preferential attachment graphs
Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman +1
Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and…
Modularity and random graphs
Colin McDiarmid, Fiona Skerman
This work will appear as a chapter in a forthcoming volume titled `Topics in Probabilistic Graph Theory'. For a given graph , each partition of the vertices has a modularity sco…
Modularity and Graph Expansion
Baptiste Louf, Colin McDiarmid, Fiona Skerman
We relate two important notions in graph theory: expanders which are highly connected graphs, and modularity a parameter of a graph that is primarily used in community detection. M…
On graphs with modularity zero or near-zero
Colin McDiarmid, Fiona Skerman
It is known that complete graphs and complete multipartite graphs have modularity zero. We show that the least number of edges we may delete from the complete graph to obtain…