Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

The number of spanning trees in regular graphs

Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ?(k) that tends to zero as k tends to infinity such that for every connected, k-regular simple graph G on n vertices C(G) = {k[1 ? δ(G)]}ⁿ. where 0 ≤ δ(G) ≤ ?(k).     

Convex Sets Under Some Graph Operations

 Given a connected graph G, we say that a set C⊆V(G) is convex in G if, for every pair of vertices x,y∈C, the vertex set of every x-y geodesic in G is contained in C. The cardinality of a maximal proper convex set in G is the convexity number of G. In this paper, we characterize the convex sets of graphs resulting from some binary operations, and compute the convexity numbers of the resulting graphs. Received: October, 2001 Final version received: September 4, 2002 Acknowledgments. The authors would like to thank the referee for the helpful suggestions and useful comments.     

Expectation of random polytopes

A random polytopeP _n in a convex bodyC is the convex hull ofn identically and independently distributed points inC. Its expectation is a convex body in the interior ofC. We study the deviation of the expectation ofP _n fromC asn→∞: while forC of classC ^k+1,k≥1, precise asymptotic expansions for the deviation exist, the behaviour of the deviation is extremely irregular for most convex bodiesC of classC ¹. Dedicated to my teacher and friend Professor Edmund Hlawka on the occasion of his 80^th birthday     

Independent cycles with limited size in a graph

Letk and s be two positive integers with s≥3. LetG be a graph of ordern ≥sk. Writen =qk + r, 0 ≤r ≤k - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC ₁,C ₂,...,C _k such thats ≤l(C _i ) ≤q for 1 ≤i ≤r arnds ≤l(C _i ) ≤q + 1 fork -r <i ≤k, where l(C_i) denotes the length ofC _i .     

The Forcing Convexity Number of a Graph

For two vertices u and v of a connected graph G, the set I(u,v) consists of all those vertices lying on a u-v geodesic in G. For a set S of vertices of G, the union of all sets I(u,v) for u, v S is denoted by I(S). A set S is a convex set if I(S) = S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. A convex set S in G with |S| = con(G) is called a maximum convex set. A subset T of a maximum convex set S of a connected graph G is called a forcing subset for S if S is the unique maximum convex set containing T. The forcing convexity number f(S, con) of S is the minimum cardinality among the forcing subsets for S, and the forcing convexity number f(G, con) of G is the minimum forcing convexity number among all maximum convex sets of G. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph G, f(G, con) con(G). It is shown that every pair a, b of integers with 0 a b and b is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of H × K ₂ for a nontrivial connected graph H is studied.     

Graph minors. I. Excluding a forest

The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG₁,…,G_r each of which has at mostk + 1 vertices, by identifying some vertices ofG_i pairwise with some ofG_i+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width?k. This, together with results of other papers, yields a “good” algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite.     

An efficient algorithm for minimumk-covers in weighted graphs

Consider an edge-weighted graphG = (V, L), and define ak-cover C as a subset of the edgesL such that each vertex inV is incident to at least one edge ofC, and|C| = k. GivenG andk, the problem is to find ak-cover of minimum weight sum. This paper presents characterizations of minimumk-covers, and shows their weight to be convex with the parameterk. An efficient algorithm is presented which generates minimumk-covers continuously as the parameterk ranges over all feasible values, together with a proof of optimality. The computational order of this algorithm is found to be|V| ? |L| ².     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.     

Two comments on Dvoretzky’s sphericity theorem

For any two positive integersk, l and anyɛ>0 there exists anN(k, l, ɛ) so that given anyl convex bodiesC ₁, …,C _l symmetric about the origin inE ⁿ withn≧N there exists a subspaceE ^k so that eachC _i intersectsE ^k, or has a projection intoE ^k, in a set which is nearly spherical (asphericity <ɛ). The measure of the totality ofE ^k which intersect a given body inE ⁿ in a nearly ellipsoidal set is considered and an affine invariant measure is introduced for that purpose.     

The convexity spectra of graphs

Let D be a connected oriented graph. A set S⊆V(D) is convex in D if, for every pair of vertices x,y∈S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that S_C(G)={con(D):D is an orientation of G} and S_SC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_SC(G)={a,n-1} and there is no connected graph G of order n?3 with S_SC(G)={n-1}. Then, we determine that S_C(K₃)={1,2}, S_C(K₄)={1,3}, S_SC(K₃)=S_SC(K₄)={1}, S_C(K₅)={1,3,4}, S_C(K₆)={1,3,4,5}, S_SC(K₅)=S_SC(K₆)={1,3}, S_C(K_n)={1,3,5,6,…,n-1}, S_SC(K_n)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.     

A note on the upper bound for disjoint convex partitions

Let n(k, l,m), k ≤ l ≤ m, be the smallest integer such that any finite planar point set which has at least n(k, l,m) points in general position, contains an empty convex k-hole, an empty convex l-hole and an empty convex m-hole, in which the three holes are pairwise disjoint. In this article, we prove that n(4, 4, 5) ≤ 16.     

Graphs isomorphic to subgraphs of their iterated line graphs

A graphG is said to be embeddable into a graphH, if there is an isomorphism ofG into a subgraph ofH. It is shown in this paper that every unicycle or tree which is neither a path norK _1,3 embeds in itsn-th iterated line graph forn1 or 2, 3, and that every other connected graph that embeds in itsn-th iterated line graph may be constructed from such an embedded unicycle or tree in a natural way. A special kind of embedding of graph into itsn-th iterated line graph, called incidence embedding, is studied. Moreover, it is shown that for every positive integerk, there exists a graphG such that (G) = , where (G) is the leastn1 for whichG embeds inL ⁿ(G).     

A simple proof of an approximation theorem of H. Minkowski

It is proved that every convex bodyC inR ⁿ can be approximated by a sequenceC _k of convex bodies, whose boundary is the intersection of a level set of a homogeneous polynomial of degree 2k and a hyperplane. The Minkowski functional ofC _k is given explictly. Some further nice properties of the approximantsC _k are proved.Supported in part by BSF and Erwin Schrödinger Auslandsstipendium J0630.     

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.     

On a connection between the existence ofk-trees and the toughness of a graph

A graphG has toughnesst(G) ift(G) is the largest numbert such that for any subsetS of the vertices ofG, the number of vertices inS is at leastt times the number of components ofG on deletion of the vertices inS, provided that there is then more than one component. Ak-tree of a connected graph is a spanning tree with maximum degree at mostk. We show here that if , withk 3, thenG has ak-tree. The notion of ak-tree generalizes the casek = 2 of a hamiltonian path, so that this result, as we discuss, may be of some interest in connection with Chvátal's conjecture that, for somet, every graph with toughness at leastt is hamiltonian.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.