Maximal Rectilinear Crossing of Cycles | Zendy

Furry W. H. | Zendy; Kleitman D. J. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Maximal Rectilinear Crossing of Cycles

Author(s) -

Furry W. H.,

Kleitman D. J.

Publication year - 1977

Publication title -

studies in applied mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 46

eISSN - 1467-9590

pISSN - 0022-2526

DOI - 10.1002/sapm1977562159

Subject(s) - combinatorics , mathematics , crossing number (knot theory) , integer (computer science) , graph , wheel graph , plane (geometry) , discrete mathematics , geometry , line graph , computer science , graph power , intersection (aeronautics) , engineering , programming language , aerospace engineering

We address the following question: In drawing a cycle on n vertices (or a graph all of whose degrees are 2) in the plane with straight line arcs, how many crossings can there be? A complete answer is given; namely, if n is odd, the number of crossings can be anything up to n ( n −3)/2 except n ( n −3)/2−1. For n even, the number of crossings in one cycle can be any integer up to n ( n −4)/2+1; general bivalent even graphs can achieve any integer up to n (2 n −7)/4 as the number of crossings.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research