**排序方式：**共有6条查询结果，搜索用时 109 毫秒

**1**

1.

We show that every 4-representative graph embedding in the double torus contains a noncontractible cycle that separates the
surface into two pieces. As a special case, every triangulation of the double torus in which every noncontractible cycle has
length at least 4 has a noncontractible cycle that separates the surface into two pieces.
Received: May 22, 2001 Final version received: August 22, 2002
RID="*"
ID="*" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070613
RID="†"
ID="†" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070430 相似文献

2.

Serge Lawrencenko Michael D. Plummer Xiaoya Zha 《Discrete and Computational Geometry》2002,28(3):313-330

**Abstract.**Let

*G*be an infinite locally finite plane graph with one end and let

*H*be a finite plane subgraph of

*G*. Denote by

*a(H)*the number of finite faces of

*H*and by

*l*(

*H*) the number of the edges of

*H*that are on the boundary of the infinite face or a finite face not in

*H*. Define the isoperimetric constant

*h (G)*to be inf

_{ H }

*l*(

*H*) /

*a(H)*and define the isoperimetric constant

*h (δ)*to be inf

_{ G }

*h (G)*where the infimum is taken over all infinite locally finite plane graphs

*G*having minimum degree

*δ*and exactly one end. We establish the following bounds on

*h (δ)*for

*δ ≥ 7*:

3.

A closed 2-cell embedding of a graph embedded in some surface is an embedding such that each face is bounded by a cycle in the graph. The strong embedding conjecture says that every 2-connected graph has a closed 2-cell embedding in some surface. In this paper, we prove that any 2-connected graph without

*V*_{8}(the Möbius 4-ladder) as a minor has a closed 2-cell embedding in some surface. As a corollary, such a graph has a cycle double cover. The proof uses a classification of internally-4-connected graphs with no*V*_{8}-minor (due to Kelmans and independently Robertson), and the proof depends heavily on such a characterization. 相似文献4.

We prove the existence of certain spanning subgraphs of graphs embedded in the torus and the Klein bottle. Matheson and Tarjan proved that a triangulated disc with

*n*vertices can be dominated by a set of no more than*n*/3 of its vertices and thus, so can any finite graph which triangulates the plane. We use our existence theorems to prove results closely allied to those of Matheson and Tarjan, but for the torus and the Klein bottle. 相似文献5.

We prove new upper bounds for the thickness and outerthickness of a graph in terms of its orientable and nonorientable genus by applying the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness. We also show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This implies that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. Finally, we show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5. 相似文献

6.

We prove that if

*G*is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then*G*contains a subdivision of*K*_{5}. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of*K*_{5}. Moreover, we prove that if*G*is 6‐connected and embedded with face‐width at least 5, then for every*v*∈*V*(G),*G*contains a subdivision of*K*_{5}whose branch vertices are*v*and four neighbors of*v*. 相似文献**1**