Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
n-ary transit functions are introduced as a generalization of binary (2-ary) transit functions. We show that they can be associated with convexities in natural way and discuss the Steiner convexity as a natural n-ary generalization of geodesicaly convexity. Furthermore, we generalize the betweenness axioms to n-ary transit functions and discuss the connectivity conditions for underlying hypergraph. Also n-ary all paths transit function is considered.
Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ 1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋ be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this article we...
Download Results (CSV)