Edge-maximal graphs on surfaces
We prove that for every surface Σ of Euler genus g, every edgemaximal embedding of a graph in Σ is at most O(g) edges short of a triangulation of Σ. This provides the first answer to an open problem of Kainen (1974).
| मुख्य लेखकों: | , |
|---|---|
| स्वरूप: | Journal article |
| प्रकाशित: |
Canadian Mathematical Society
2017
|