Search

Let D = ( V , E ) be a strongly connected digraph and let u and v be two vertices in D . The maximum distance md( u , v ) is defined as md( u , v ) = max{ d ( u , v ), d ( v , u )} , where d ( u , v ) denotes the length of a shortest directed u - v path in D . This is a metric. The boundary, contour, eccentricity and periphery sets of a strongly connected digraph D with respect to this metric have been defined. The boundary-type sets of the strong product of two digraphs is investigated in this article.

A set of vertices S of a graph G is geodesically convex if for every pair of vertices of S, all vertices of all shortest paths joining them also lie in S. The geodetic convex hull of S, denoted by 〈 S 〉 , is the minimum geodesically convex set of G containing S. We say that S is Caratheodory independent if 〈 S 〉 ∖ ( ⋃ a ∈ S 〈 S ∖ { a } 〉 ) ≠ ∅ and that S is exchange independent if | S | = 1 or there is p ∈ S such that 〈 S ∖ { p } 〉 ∖ ⋃ a ∈ S ∖ { p } 〈 S ∖ { a } 〉 ≠ ∅ . The Caratheodory number (exchange number) of G is the cardinality of a maximum Caratheodory (exchange) independent set. In this paper, we show that deciding whether a given graph has exchange number at most k is an NP -complete problem. We also present characterizations of the Caratheodory and exchange numbers for some graph classes, like unit interval graphs and powers of cycles, which allow us to determine these parameters in polynomial time.

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. Keywords: Betweenness, Interval function, Induced path function

Let \(D=(V,E)\) be a digraph and \(u ,v\in V(D)\). The metric, maximum distance is defined by \(md(u,v)=\max \{\overrightarrow{d}(u,v), \overrightarrow{d}(v,u)\}\) where \(\overrightarrow{d}(u,v)\) denote the length of a shortest directed \(u-v\) path in D. The relationship between the boundary-type sets of the lexicographic product of two digraphs and its factor graphs have been studied in this article.

Genetic Algorithms typically invoke crossover operators to produce offsprings that are a “mixture” of two parents x and y. On strings, k-point crossover breaks parental genotypes at at most k corresponding positions and concatenates alternating fragments for the two parents. The transit set Rk(x, y) comprises all offsprings of this form. It forms the tope set of an uniform oriented matroid with Vapnik-Chervonenkis dimension k + 1. The Topological Representation Theorem for oriented matroids thus implies a representation in terms of pseudosphere arrangements. This makes it possible to study 2-point crossover in detail and to characterize the partial cubes defined by the transit sets of two-point crossover.

The \(\varDelta \)-interval of \(u,v \in V (G)\), \(I_{\varDelta }(u,v)\), is the set formed by u, v and every w in V(G) such that \(\{u, v, w\}\) is a triangle \((K_3)\) of G. A set S of vertices such that \(I_{\varDelta } (S)=V(G)\) is called a \(\varDelta \)-set. \(\varDelta \)-number is the minimum cardinality of a \(\varDelta \)-set. \(\varDelta \)-graph is a graph with all the vertices lie on some triangles. If a block graph is a \(\varDelta \)-graph, then we say that it is a block \(\varDelta \)-graph. A set \(S\subseteq V (G)\) is \(\varDelta \)-convex if there is no vertex \(u \in V(G)\setminus S\) forming a triangle with two vertices of S. The convexity number of a graph G with respect to the \(\varDelta \)-convexity is the maximum cardinality of a proper convex subset of G. We have given an exact value for the convexity number of block \(\varDelta \)-graphs with diameter \({\le }3\), block \(\varDelta \)-graphs with diameter \({>}3\) and the two standard graph products (Strong, Lexicographic products), a bound for Cartesian product. Also discussed some bounds for \(\varDelta \)-number and a realization is done for the \(\varDelta \)-number and the hull number.

k -point crossover operators and their recombination sets are studied from different perspectives. We show that transit functions of k -point crossover generate, for all k > 1 , 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 G is uniquely determined by its interval function I . The conjecture of Gitchoff and Wagner that for each transit set R k ( x , y ) 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 k it is shown that the transit sets of k -point crossover operators are the subsets with maximal Vapnik–Chervonenkis dimension.

Suppose that $$D=(V,E)$$ is a strongly connected digraph. Let $$u, v \in V(D)$$ . The maximum distance md(u, v) defined as $$md(u,v)=max\{\overrightarrow{d}(u,v), \overrightarrow{d}(v,u)\}$$ is a metric, where $$\overrightarrow{d}(u,v)$$ denote the length of a shortest directed $$u-v$$ path in D. The boundary, contour, eccentricity and periphery sets of a strong digraph D are defined with respect to this metric. The main aim of this paper is to identify the above said metrically defined sets of a strong digraph D in terms of its prime factor decomposition with respect to Cartesian product.

Let I G ( x , y ) and J G ( x , y ) be the geodesic and induced path intervals between x and y in a connected graph G , respectively. The following three betweenness axioms are considered for a set V and R : V × V → 2 V : (i) x ∈ R ( u , y ) , y ∈ R ( x , v ) , x ≠ y , | R ( u , v ) | > 2 ⇒ x ∈ R ( u , v ) ; (ii) x ∈ R ( u , v ) ⇒ R ( u , x ) ∩ R ( x , v ) = { x } ; (iii) x ∈ R ( u , y ) , y ∈ R ( x , v ) , x ≠ y ⇒ x ∈ R ( u , v ) . We characterize the class of graphs for which I G satisfies (i), the class for which J G satisfies (ii) and the class for which I G or J G satisfies (iii). The characterization is given in terms of forbidden induced subgraphs. It turns out that the class of graphs for which I G satisfies (i) is a proper subclass of distance hereditary graphs and the class for which J G satisfies (ii) is a proper superclass of distance hereditary graphs. We also give an axiomatic characterization of chordal and Ptolemaic graphs.

Transit functions provide a unified approach to study notions of intervals, convexities, and betweenness. Recently, their scope has been extended to certain set systems associated with clustering. We characterize here the class of set systems that correspond to k-ary monotonic transit functions. Convexities form a subclass and are characterized in terms of transit functions by two additional axioms. We then focus on axiom systems associated with weak hierarchies as well as other generalizations of hierarchical set systems.

The concept of the k-Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping S:[email protected]?2^V such that S(u"1,...,u"k) consists of all vertices in G that lie on some Steiner tree with respect to a multiset W={u"1,...,u"k} of vertices from G. In this paper we obtain, for each k, a characterization of the class of graphs in which every k-Steiner interval S has the so-called union property, which says that S(u"1,...,u"k) coincides with the union of geodesic intervals I(u"i,u"j) between all pairs from W. It turns out that, as soon as k>3, this class coincides with the class of graphs in which the k-Steiner interval enjoys the monotone axiom (m), respectively (b2) axiom, the conditions from betweenness theory. Notably, S satisfies (m), if x"1,...,x"[email protected]?S(u"1,...,u"k) implies S(x"1,...,x"k)@?S(u"1,...,u"k), and S satisfies (b2) if [email protected]?S(u"1,u"2,...,u"k) implies S(x,u"2,...,u"k)@?S(u"1,...,u"k). In the case k=3, these three classes are different, and we give structural characterizations of graphs for which their Steiner interval S satisfies the union property as well as the monotone axiom (m). We also prove several partial observations on the class of graphs in which the 3-Steiner interval satisfies (b2), which lead to the conjecture that these are precisely the graphs in which every block is a geodetic graph with diameter at most two.

We discuss the convexity invariants, namely, the exchange and Helly numbers of the Steiner and geodesic convexity in lexicographic product of graphs. We use the structure of both the Steiner and geodesic convex sets in the lexicographic product for proving the results. Along the way the exchange number of the induced path convexity in arbitrary graphs is also determined.