Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777323 | European Journal of Combinatorics | 2018 | 17 Pages |
Abstract
Finally, we consider analogous problems for circular orderings, where pairs of nonincident edges are separated unless their endpoints alternate. Let Ïâ(G) be the number of circular orderings needed to separate all pairs and Ïfâ(G) be the fractional version. Among our results: (1) Ïâ(G)=1 if and only G is outerplanar. (2) Ïâ(G)â¤2 when G is bipartite. (3) Ïâ(Kn)â¥log2log3(nâ1). (4) Ïfâ(G)â¤32 for every graph G, with equality if and only if K4âG. (5) Ïfâ(Km,m)=3mâ32mâ1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sarah J. Loeb, Douglas B. West,