BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We investigate the problem of reaching majority agreement in a disconnected network. We obtain conditions under which such an agreement is certainly possible/impossible, and observe that these coincide in the ternary case.
We study the topic of "extremal" planar graphs, defining exP(n,H) to be the maximum number of edges possible in a planar graph on n vertices that does not contain a given graph H as a subgraph. In particular,we examine the case when H is a small cycle,obtaining exP(n,C4)≤715(n−2) for all n≥4 and exP(n,C5)≤512n−33 for all n≥11, and showing that both of these bounds are tight.
We investigate the problem of secure message transmission in the presence of a "fully generalised" adversary, who disrupts and listens to separate sets of communication wires. We extend previous results by considering the case when these sets may have arbitrary size, providing necessary and sufficient conditions for both one-way and two-way communication.
The topic of diversity is an interesting subject, both as a purely mathematical concept and also for its applications to important real-life situations. Unfortunately, although the meaning of diversity seems intuitively clear, no precise mathematical definition exists. In this paper, we adopt an axiomatic approach to the problem, and attempt to produce a satisfactory measure.
Random planar graphs have been the subject of much recent work. Many basic properties of the standard uniform random planar graph P_{n}, by which we mean a graph chosen uniformly at random from the set of all planar graphs with vertex set {1,2,...,n}, are now known, and variations on this standard random graph are also attracting interest. Prominent among the work on P_{n} have been asymptotic results for the probability that P_{n} will be connected or contain given components/subgraphs. Such progress has been achieved through a combination of counting arguments and a generating function approach. More recently, attention has turned to P_{n,m}, the graph taken uniformly at random from the set of all planar graphs on {1,2,...,n} with exactly m(n) edges (this can be thought of as a uniform random planar graph with a constraint on the average degree). The case when m(n) = qn for fixed q in (1,3) has been investigated, and results obtained for the events that P_{n,qn} will be connected and that P_{n,qn} will contain given subgraphs. In Part I of this thesis, we use elementary counting arguments to extend the current knowledge of P_{n,m}. We investigate the probability that P_{n,m} will contain given components, the probability that P_{n,m} will contain given subgraphs, and the probability that P_{n,m} will be connected, all for general m(n), and show that there is different behaviour depending on which `region' the ratio m(n)/n falls into. In Part II, we investigate the same three topics for a uniform random planar graph with constraints on the maximum and minimum degrees.
In this paper, we investigate a problem concerning quartets, which are a particular type of tree on four leaves. Loosely speaking, a set of quartets is said to be `definitive' if it completely encapsulates the structure of some larger tree, and `minimal' if it contains no redundant information. Here, we address the question of how large a minimal definitive quartet set on n leaves can be, showing that the maximum size is at least 2n-8 for all n>3. This is an enjoyable problem to work on, and we present a pretty construction, which employs symmetry.
Let P_{n,d,D} denote the graph taken uniformly at random from the set of all labelled planar graphs on {1,2,...,n} with minimum degree at least d(n) and maximum degree at most D(n). We use counting arguments to investigate the probability that P_{n,d,D} wll contain given components and subgraphs, showing exactly when this is bounded away from 0 and 1 as n tends to infinity.
We shall present an algorithm for determining whether or not a given planar graph H can ever be a subgraph of a 4-regular planar graph. The algorithm has running time O(|H|^{2.5}) and can be used to find an explicit 4-regular planar graph G containing H if such a graph exists. It shall not matter whether we specify that H and G must be simple graphs or allow them to be multigraphs.
Let P_{n,m} denote the graph taken uniformly at random from the set of all planar graphs on {1,2,..., n} with exactly m(n) edges. We use counting arguments to investigate the probability that P_{n,m} will contain given components and subgraphs, finding that there is different asymptotic behaviour depending on the ratio m/n.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.