13 citations · 13 across the 3 of their papers we have counts for
3 papers
math.CO2010
The Complexity of Two Graph Orientation Problems
N. Eggemann, S. D. Noble
We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. We show that it is NP-com…
math.CO2009★ 13 cited
k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4
Nicole Eggemann, Frédéric Havet, Steven D. Noble
A mapping from the vertex set of a graph G = (V,E) into an interval of integers {0,...,k} is an L(2,1)-labelling of G of span k if any two adjacent vertices are mapped onto integer…
math.CO2008
The Clustering Coefficient of a Scale-Free Random Graph
Nicole Eggemann, Steven D. Noble
We consider a random graph process in which, at each time step, a new vertex is added with m out-neighbours, chosen with probabilities proportional to their degree plus a strictly…