Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0166-218X(00)00382-6 | Discrete Applied Mathematics |
Keywords | Field | DocType |
05c12,oriented graph,orientable convexity number,convex set,05c20,convexity number,connected graph,outerplanar graph | Graph theory,Discrete mathematics,Combinatorics,Convexity,Vertex (geometry),Bound graph,Directed graph,Convex set,Connectivity,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
116 | 1-2 | Discrete Applied Mathematics |
Citations | PageRank | References |
7 | 0.96 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gary Chartrand | 1 | 7 | 0.96 |
| John Frederick Fink | 2 | 82 | 12.34 |
| Ping Zhang | 3 | 292 | 47.70 |