Title | ||
---|---|---|
Tight Descriptions of 3-Paths in Normal Plane Maps : Dedicated to Andre Raspaud on the occasion of his 70th birthday. |
Abstract | ||
---|---|---|
We prove that every normal plane map (NPM) has a path on three vertices (3-path) whose degree sequence is bounded from above by one of the following triplets: (3, 3, ), (3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), and (6,4,7). This description is tight in the sense that no its parameter can be improved and no term dropped. We also pose a problem of describing all tight descriptions of 3-paths in NPMs and make a modest contribution to it by showing that there exist precisely three one-term descriptions: (5, , 6), (5, 10, ), and (10, 5, ). (C) 2016 Wiley Periodicals, Inc. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1002/jgt.22051 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
plane graph,structural property,normal plane map,3-path | Normal plane,Combinatorics,Vertex (geometry),Structural property,Degree (graph theory),Mathematics,Planar graph,Bounded function | Journal |
Volume | Issue | ISSN |
85.0 | 1.0 | 0364-9024 |
Citations | PageRank | References |
2 | 0.39 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Oleg V. Borodin | 1 | 639 | 67.41 |
Anna O. Ivanova | 2 | 172 | 23.19 |
Alexandr V. Kostochka | 3 | 682 | 89.87 |