Search

The metric betweenness of a connected graph and arbitrary graphs is FO definable. Moreover, several interesting classes of graphs with strong distance properties are shown to be FO definable using metric betweenness. However, there are different classes that do not possess such an FO axiomatization. The main goal of this note is to show that certain classes of graphs do not allow an axiomatization in First-Order Logic with Betweenness (FOLB).

AbstractInterval function of a graph is a well-known notion in metric graph theory and the axiomatic characterization using a set of first order axioms of different graph classes is an interesting problem in this area. Partial cubes and partial Hamming graphs form one of the central graph class that can be embedded into hypercubes and Hamming graphs respectively. In this paper we present an axiomatic characterization of the interval function of partial cubes and partial Hamming graphs, using different first order axioms. Further, we give an axiomatic characterization of the interval function of these graphs using axioms on an arbitrary function R on V.

AbstractIn a graph G, the all-paths transit function A(u, v), consists of the set of all vertices in the graph G which lies in some path connecting u and v. Convexity obtained by the all-paths transit function is called all-paths convexity. A partition of a set P of vertices of a graph G into two disjoint non-empty subsets is called a Radon partition if the convex hulls of the subsets intersect. A Radon partition (P0, Q0) of P into nonempty subsets is called t-tolerant Radon partition, if for any set [Formula: see text] with [Formula: see text], the intersection of the convex hulls [Formula: see text]. Here we study the t-tolerant Radon number of G with respect to all-paths convexity. It is the minimum number k such that any collection of k vertices of G has t-tolerant Radon partition. We prove that if G has only one block, then [Formula: see text] whenever [Formula: see text]. Finally, we prove that if the block-cut vertex tree representation of G is a path then [Formula: see text], and if the block-cut vertex tree representation of G is a tree that is not a path then [Formula: see text].

The interval function and the induced path function are two well studied class of set functions of a connected graph having interesting properties and applications to convexity, metric graph theory. Both these functions can be framed as special instances of a general set function termed as a transit function defined on the Cartesian product of a non-empty set \(V\) to the power set of \(V\) satisfying the expansive, symmetric and idempotent axioms. In this paper, we propose a set of independent first order betweenness axioms on an arbitrary transit function and provide characterization of the interval function of Ptolemaic graphs and the induced path function of chordal graphs in terms of an arbitrary transit function. This in turn gives new characterizations of the Ptolemaic and chordal graphs.

-point crossover operators and their recombination sets are studied from different perspectives. We show that transit functions of -point crossover generate, for all , the same convexity as the interval function of the underlying graph. This settles in the negative an open problem by Mulder about whether the geodesic convexity of a connected graph is uniquely determined by its interval function . The conjecture of Gitchoff and Wagner that for each transit set distinct from a hypercube there is a unique pair of parents from which it is generated is settled affirmatively. Along the way we characterize transit functions whose underlying graphs are Hamming graphs, and those with underlying partial cube graphs. For general values of it is shown that the transit sets of -point crossover operators are the subsets with maximal Vapnik–Chervonenkis dimension.

Betweenness is a universal notion present in several disciplines of mathematics. The notion of betweenness has a profound history and many pioneers like Euclid, Pasch, Hilbert have studied betweenness axiomatically. In discrete mathematics too, betweenness is present and several authors have worked on this concept from an axiomatic view. In graph theory, betweenness is developed mainly as metric betweenness, studied using the shortest path metric in a connected graph, thus resulting in the notion of the interval function. Many interesting results are available in graph theory using the interval function. The interval function is generalized to induced path function by replacing shortest paths by induced paths. The induced path betweenness also captured attention among graph theorists with several interesting results to date. From an axiomatic point of view, two pertinent questions can be framed on these functions. Is it possible to axiomatically characterize the interval function of some special graphs using some set of first order axioms defined on an arbitrary transit function? Is it possible to characterize the graphs with the help of their interval functions? In this paper, we survey the results as answers to these questions available from the research papers.