44 citations · 327 across the 39 of their papers we have counts for
8 papers · 1 filter
Ramsey numbers of cycles versus general graphs
John Haslegrave, Joseph Hyde, Jaehoon Kim +1
The Ramsey number is the minimum number such that any -vertex graph either contains a copy of or its complement contains . Burr in 1981 proved a pleasingly g…
Determining triangulations and quadrangulations by boundary distances
John Haslegrave
We show that if a disc triangulation has all internal vertex degrees at least 6, then the full triangulation may be determined from the pairwise graph distance between boundary ver…
On the relationship between variable Wiener index and variable Szeged index
Stijn Cambie, John Haslegrave
We resolve two conjectures of Hriňáková, Knor and Škrekovski (2019) concerning the relationship between the variable Wiener index and variable Szeged index for a connected, non-com…
Crux and long cycles in graphs
John Haslegrave, Jie Hu, Jaehoon Kim +3
We introduce a notion of the \emph{crux} of a graph , measuring the order of a smallest dense subgraph in . This simple-looking notion leads to some generalisations of known…
Degrees in link graphs of regular graphs
Itai Benjamini, John Haslegrave
We analyse an extremal question on the degrees of the link graphs of a finite regular graph, that is, the subgraphs induced by non-trivial spheres. We show that if is -regul…
The number and average size of connected sets in graphs with degree constraints
John Haslegrave
The average size of connected vertex subsets of a connected graph generalises a much-studied parameter for subtrees of trees. For trees, the possible values of this parameter are c…
Sum index, difference index and exclusive sum number of graphs
John Haslegrave
We consider two recent conjectures of Harrington, Henninger-Voss, Karhadkar, Robinson and Wong concerning relationships between the sum index, difference index and exclusive sum nu…
The path minimises the average size of a connected induced subgraph
John Haslegrave
We prove that among all graphs of order n, the path uniquely minimises the average order of its connected induced subgraphs. This confirms a conjecture of Kroeker, Mol and Oellerma…