Zobrazeno 1 - 10
of 49
pro vyhledávání: '"Payne, Michael S."'
S. Negami conjectured in $1988$ that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It follows from the works of D. Archdeacon, M. Fellows, P. Hlin\v{e}n\'{y}, and S. Negami that this conjecture is true
Externí odkaz:
http://arxiv.org/abs/2311.01672
For an arrangement of $n$ lines in the real projective plane, we denote by $f$ the number of regions into which the real projective plane is divided by the lines. Using Bojanowski's inequality, we establish a new lower bound for $f$. In particular, w
Externí odkaz:
http://arxiv.org/abs/2205.09304
Publikováno v:
In Computational Geometry: Theory and Applications August 2024 121
Autor:
Harvey, Daniel J., Payne, Michael S.
We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if $\omega(G)$ is the clique number of a chordal graph $G$, then there is
Externí odkaz:
http://arxiv.org/abs/2012.07221
Overlaid oriented Voronoi diagrams (OOVDs) are known to provide useful data for the construction of optimal Euclidean $1$-Steiner trees. The theoretical time complexity of construction methods exploiting the OOVD is $O(n^2)$, but a computational stud
Externí odkaz:
http://arxiv.org/abs/2002.06752
Autor:
Harvey, Daniel J., Payne, Michael S.
Publikováno v:
In Discrete Mathematics April 2023 346(4)
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 3, Combinatorics (September 19, 2016) dmtcs:1367
We prove geometric Ramsey-type statements on collections of lines in 3-space. These statements give guarantees on the size of a clique or an independent set in (hyper)graphs induced by incidence relations between lines, points, and reguli in 3-space.
Externí odkaz:
http://arxiv.org/abs/1512.03236
Autor:
Payne, Michael S.
Given a set of red and blue points in the plane, a bichromatic line is a line containing at least one red and one blue point. We prove the following conjecture of Kleitman and Pinchasi (unpublished, 2003). Let P be a set of n red, and n or n-1 blue p
Externí odkaz:
http://arxiv.org/abs/1503.06281
We prove a new sufficient condition for a cubic 3-connected planar graph to be Hamiltonian. This condition is most easily described as a property of the dual graph. Let $G$ be a planar triangulation. Then the dual $G^*$ is a cubic 3-connected planar
Externí odkaz:
http://arxiv.org/abs/1312.3783
Autor:
Payne, Michael S., Wood, David R.
Publikováno v:
SIAM J. Discrete Math. 27:1727-1733, 2013
Let $f(n,\ell)$ be the maximum integer such that every set of $n$ points in the plane with at most $\ell$ collinear contains a subset of $f(n,\ell)$ points with no three collinear. First we prove that if $\ell \leq O(\sqrt{n})$ then $f(n,\ell)\geq \O
Externí odkaz:
http://arxiv.org/abs/1208.5289