论文标题
局部哈密顿图和最小图表上最小图表
Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
论文作者
论文摘要
我们证明，每个本地的Hamiltonian图表都有$ n \ ge 3 $顶点，并且可能具有多个边缘的$ 3N-6 $边缘，并且仅当三角形进行三角形时，均具有平等。结果，在某些二维表面$σ$（不一定是紧凑）上，图形$ g $图的每个边缘最大嵌入都具有至少$ 3N-6 $的边缘，并且仅当$ g $还会在$ g $中也将trianguling trianguling triangultianguling。此外，如果$ g $很简单，那么对于每个顶点$ V $，$σ$上$ V $的循环订购与$σ$上的$ v $相同，则与球体上$ V $左右的顺时针或抗锁方向相同。如果$ g $在4个顶点上没有完整的图形，并且至少有4个顶点，则在两个嵌入中，面束相同。
We prove that every locally Hamiltonian graph with $n\ge 3$ vertices and possibly with multiple edges has at least $3n-6$ edges with equality if and only if it triangulates the sphere. As a consequence, every edge-maximal embedding of a graph $G$ graph on some 2-dimensional surface $Σ$ (not necessarily compact) has at least $3n-6$ edges with equality if and only if $G$ also triangulates the sphere. If, in addition, $G$ is simple, then for each vertex $v$, the cyclic ordering of the edges around $v$ on $Σ$ is the same as the clockwise or anti-clockwise orientation around $v$ on the sphere. If $G$ contains no complete graph on 4 vertices and has at least 4 vertices, then the face-boundaries are the same in the two embeddings.
