Convexity in oriented graphs |
| |
Institution: | 1. Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008-5152, USA;2. Department of Mathematics and Statistics, The University of Michigan-Dearborn, USA |
| |
Abstract: | For vertices u and v in an oriented graph D, the closed interval Iu,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), IS] is the union of all closed intervals Iu,v] with u,v∈S. A set S is convex if IS]=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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|