An Euler-type formula for median graphs

✍ Scribed by Sandi Klavzar; Henry Martyn Mulder; Riste Sˇkrekovski

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 180 KB
• Volume: 187
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00019-3

✦ Synopsis

Let G be a median graph on n vertices and m edges and let k be the number of equivalence classes of the Djokovi6's relation ~9 defined on the edge-set of G. Then 2n-m-k ~< 2. Moreover, 2n-m-k = 2 if and only if G is cube-free. (~) 1998 Elsevier Science B.V. All rights reserved A median graph is a connected graph such that, for every triple of vertices u, v, w, there is a unique vertex x lying on a geodesic (i.e. shortest path) between each pair of u, v, w. By now, the class of median graphs is well studied and a rich structure theory is available, see e.g. [5]. In this note, we present an Euler-type formula for median graphs, which involves the number of vertices n, the number of edges m, and the number of ~9-classes k (or, equivalenty, the number of cutsets in the cutset coloring, cf. [6,7]). The formula is an inequality, where equality is attained if and only if the median graph is cube-free.

all shortest paths between u and v belong to H. Clearly, a convex subgraph is connected. The Djokovi6's relation O introduced in [1] is defined on the edge-set of a graph in the following way. Two edges e = xy and f = uv of a graph G are in relation ~9 if do(x,u) + do(y,v) ¢ dc(x,v) + dc(y,u).