The Maximum Genus on a 3-Vertex-Connected Graph

 This paper shows that the lower bound on the maximum genus for a 3-vertex-connected graph G, which may have multiple edges and loops, is at least ⅓β(G). This answers the question posed by the authors in [9]. Received: January 16, 1997 Revised: May 22, 1998     

图的最大亏损及围长

图的最大亏损主要由其参数Ｂｅｔｔｉ亏数确定（例如,见［３］）．本文给出了由图的独立数及围长所确定的Ｂｅｔｔｉ亏数的一个最好上界 ,从而即可得到关于图的最大亏格的一个新结果．     

The Maximum Genus of a Graph with Given Diameter and Connectivity

In this paper, we first review some of the known results about the maximum genus of a graph with given diameter or (and) connectivity. Then we prove that a 3-connected diameter 4 multigraph has Betti deficiency at most 2. Furthermore, we show this upper bound is sharp.     

平面Halin图的强最大亏格

本文给出了平面Halin图的可定向与不可定向强最大亏格．     

广义置换图的最大亏格(英文)

In this paper we prove that the generalized permutation graph G(n,k) is upper embeddable if it has at most two odd subcycles,and that the maximum genus of G(n,k) is more than[β(G(n,k))/3]in most cases.     

关于嵌入图的最大亏格

不依赖图的其它参数, 而主要依据图嵌入在定向曲面上的有关嵌入性质, 该文研究图的最大亏格.     

极大外平面图的不可定向强最大亏格

强嵌入猜想称:任意2-连通图都可以强嵌入到某一曲面上．本文通过分析极大外平面图的结构以及强嵌入的特征,讨论了该图类的不可定向强最大亏格,并给出了一个复杂度为O(nlogn)的算法．其中部分图类的强最大亏格嵌入提供该图的一个少双圈覆盖．     

嵌入图的面度与最大亏格

利用图在曲面上的嵌入特征,特别是面的度的大小,研究图的最大亏格下界或上可嵌入性．     

Face Size and the Maximum Genus of a Graph 1. Simple Graphs

This paper shows that a simple graph which can be cellularly embedded on some closed surface in such a way that the size of each face does not exceed 7 is upper embeddable. This settles one of two conjectures posed by Nedela and koviera (1990, in “Topics in Combinatorics and Graph Theory,” pp. 519–529, Physica Verlag, Heidelberg). The other conjecture will be proved in a sequel to this paper.     

边剖分、点扩张与图的最大亏格的可约性

设γM（G）是连通图G=（V，E）的最大亏格，记EM^-（G）={e∈E(G)|G\e连通，且γM（G\e）=γM（G）}。若EM^-(G)≠0，则称G是γ（G）-可约的；否则称G是γM（G）-不可约的。本文证明了边的剖分不改变图的最大亏格可约性，点的扩张不改变上可嵌入图的最大亏格可约性；并给出了两类满足EM^-（G）=E（G）的非4-边连通图。     

On the Maximum Matching Graph of a Graph

1IntroductionMatchingtheory,aswellastheassignmentprobleminlinearprogramming,hasawiderangeofapplicationinthetheoryandpracticeofoperationsresearch.Bysomepracticalmotivations,e.g.,forfindingalloptimalsolutions,peoplewanttoknowthestructurepropertiesofallmaximummatchingsofagraphG.InthecasethatGhasperfectmatchings,extensiveworkhasbeendoneontheso-calledperfectmatChinggrape(or1-factorgraph),inwhichtwoperfectmatchingsMIandMZaresaidtobeadjacentifMI~MZ@E(C)whereCisanMI-alternatingcycleofG.Therewer…     

单节点图的弱最大亏格

单节点图即只有一个点的图.本文讨论了该图类的三种嵌入.并得到了对应的最大亏格.对于这类图的弱嵌入.插值定理是成立的.     

Cochromatic Number and the Genus of a Graph

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G. In this paper we introduce the problem of determining for a surface S, z(S), which is the maximum cochromatic number among all graphs G that embed in S. Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z(S) is nonorientable of genus at least four, then z(S)≤χ(S). Here χ(S) denotes the chromatic number S. Exact results are obtained for the sphere, the Klein bottle, and for S. It is conjectured that z(S) is equal to the maximum n for which the graph G_n = K₁ ∪ K₂ ∪ … ∪ K_n embeds in S.     

最大匹配图的围长

将一个图的所有最大匹配作为顶点集,称两个最大匹配相邻,若它们之一通过交换一条边得到另一个,由引所得图为该图的最大匹配图。本文研究了最大匹配图的围长,从而给出了最大匹配图是树或完全图的条件。     

一类3-连通图的上可嵌入性

结合图的k-边形2-因子条件，确定了一类上可嵌入的3-连通图。     

根点自粘合后图的亏格分布

利用删点、加边原理,多种乘法法则,自粘合定理给出了一个双根图在其中一个根点的度为任意大的情形下根点自粘合后图的亏格分布,推广了Gross在文[Genus distribution of graph amalgamations:self-pasting at root-vertices,Aust.J.Comb.,2011,49:19-38]中两个根点度均为2的类似结果.     

直径为4的图的最大亏格

本文证明了如下结果:设G是直径为4的简单囹,若G不含3阶完全子图K3,则G的Betti亏数ξ(G)≤2,因此有G的最大亏格γM(G)≥1/2β(G)-1.而且,在这种意义下,所得到的界是最好的.     

Maximum Genus of Strong Embeddings

The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover.Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.     

具有最大度距离的单圈图

设U (n)是具有n个顶点的所有单圈图的集合,G(3; n- 3)是由一个三角形C3粘上一条悬挂路P_(n-3)得到的单圈图.本文将证明当n 5时具有最大度距离的单圈图是G(3; n - 3).