Article ID Journal Published Year Pages File Type
5777323 European Journal of Combinatorics 2018 17 Pages PDF
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
, ,