On the Convexity Number of Graphs

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.     

Characterization and representation problems for intersection betweennesses

For a set system M=(M_v)_v∈V indexed by the elements of a finite set V, the intersection betweenness B(M) induced by M consists of all triples (u,v,w)∈V³ with M_u∩M_w⊆M_v. Similarly, the strict intersection betweenness B_s(M) induced by M consists of all triples (u,v,w)∈B(M) such that u, v, and w are pairwise distinct. The notion of a strict intersection betweenness was introduced by Burigana [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Math. Soc. Sci. 185 (2009) 5-36]. We provide axiomatic characterizations of intersection betweennesses and strict intersection betweennesses. Our results yield a simple and efficient algorithm that constructs a representing set system for a given (strict) intersection betweenness. We study graphs whose strict shortest path betweenness is a strict intersection betweenness. Finally, we explain how the algorithmic problem related to Burigana’s notion of a partial tree representation can be solved efficiently using well-known algorithms.     

The Erdős–Pósa Property for Long Circuits

For an integer ? at least 3, we prove that if G is a graph containing no two vertex‐disjoint circuits of length at least ?, then there is a set X of at most vertices that intersects all circuits of length at least ?. Our result improves the bound due to Birmelé, Bondy, and Reed (The Erd?s–Pósa property for long circuits, Combinatorica 27 (2007), 135–145) who conjecture that ? vertices always suffice.     

Antiplasmodial and Cytotoxic Flavonoids from Pappea capensis (Eckl. & Zeyh.) Leaves

Ethnobotanical surveys indicate that the Masai and Kikuyu in Kenya, the Venda in South Africa, and the Gumuz people of Ethiopia use Pappea capensis for the treatment of malaria. The present study aimed to investigate the phytochemical and antiplasmodial properties of the plant leaves. The bioactive compounds were isolated using chromatographic techniques. The structures were established using NMR, HRMS, and UV spectroscopy. Antiplasmodial activity of P. capensis leaf extract and isolated compounds against chloroquine-sensitive 3D7 P. falciparum was evaluated using the parasite lactate dehydrogenase assay. Cytotoxicity against HeLa (human cervix adenocarcinoma) cells was determined using the resazurin assay. The extract inhibited the viability of Plasmodium falciparum by more than 80% at 50 µg/mL, but it was also cytotoxic against HeLa cells at the same concentration. Chromatographic purification of the extract led to the isolation of four flavonoid glycosides and epicatechin. The compounds displayed a similar activity pattern with the extract against P. falciparum and HeLa cells. The results from this study suggest that the widespread use of P. capensis in traditional medicine for the treatment of malaria might have some merits. However, more selectivity studies are needed to determine whether the leaf extract is cytotoxic against noncancerous cells.     

How local irregularity gets global in a graph

We prove asymptotically tight bounds on the difference between the maximum degree and the minimum degree of a simple graph in terms of its order and of the maximum difference between the degrees of adjacent vertices. Examples showing tightness and a conjecture are presented. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 18–23, 2002     

Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees

We derive closed formulas for the numbers of independent sets of size at most 4 and matchings of size at most 3 in graphs without small cycles that depend only on the degree sequence and the products of the degrees of adjacent vertices.

As a related problem we describe an algorithm that determines a tree of given degree sequence that maximizes the sum of the products of the degrees of adjacent vertices.     

Pairs of Disjoint Dominating Sets and the Minimum Degree of Graphs

For a connected graph G of order n and minimum degree δ we prove the existence of two disjoint dominating sets D ₁ and D ₂ such that, if δ ≥ 2, then ${|D_1\cup D_2|\leq \frac{6}{7}n}$ unless G = C ₄, and, if δ ≥ 5, then ${|D_1\cup D_2|\leq 2\frac{1+\ln(\delta+1)}{\delta+1}n}$ . While for the first estimate there are exactly six extremal graphs which are all of order 7, the second estimate is asymptotically best-possible.     

The cat and the noisy mouse

We consider a variant of a pursuit and evasion game studied independently by Britnell and Wildon as well as Haslegrave. In their game, a cat has to catch an invisible mouse that moves along the edges of some graph $G$. In our version, the cat receives partial information about its distance to the mouse, and we show that the cat has a winning strategy if and only if $G$ is a forest. Seager proposed a similar game with complete distance information whose rules cause some small yet important differences to the game we consider.