The semi-arc k-visibility graph edge-maximization conjecture
The semi-arc k-visibility graph edge-maximization conjecture
A semi-arc -visibility graph is a graph represented by semi-arcs, with visibility allowing at most obstructing semi-arcs; let be the number of vertices. Semi-arc -visibility graph edge-maximization conjecture. The maximum number of edges in a semi-arc -visibility graph on vertices is
for . This conjecture would determine the extremal edge count beyond the open range identified in the paper; the stated bound is conjectured to be tight.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Matthew Babbitt, J. T. Geneson and Tanya Khovanova, “On k-visibility graphs”, arXiv:1305.0505 (2014).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.