纵横扩张的优化

得到了最小折数纵横扩张的判别准则．针对4-正则图的平面嵌入的纵横扩张的特殊性，给出了它的最小折数纵横扩张判别准则．     

图的k-单圈划分中的优化问题

图的划分问题曾引起图论界的广泛关注，在文献[4]中讨论了k-单圈划分，本文进一步研究基于k-单圈划分的优化问题，即在一个赋权图中求一个最小权可k-单圈划分的支撑子图，以及对一个不存在k-单圈划分支撑子图的图，如何添最少的边使得它有k-单圈划分的支撑子图。     

关于无环Euler平面地图数目的注记

本文提供了组合上不等价的有根无环Euler平面地图以边数为参数的的数目,同时对于几乎无环的情形也给出了一个计数显式.     

ENUMERATING ROOTED LOOPLESS PLANAR MAPS

This paper provides the following results.1.The equivalence between the method described by W.T.Tutte for determining parametricexpressions of certain enumerating functions and the one which the author used in [2] for findingthe parametric expression of the generating function of rooted general planar maps dependent on theedge number,is shown.2.The number of rooted boundary loop maps,i.e.,maps for each of which all the edges on theboundary of the outer face are loops,with the edge number given is found.3.The number of rooted nearly loopless planar maps,i.e.,loopless maps and maps having exactlyone loop which is just the rooted edge and does not form the boundary of the outer face,with givenedge number is also found.4.The recursive formula satisfied by the number of rooted loopless planar maps dependent onthe edge number is derived.5.In addition,the number of loop rooted maps,i.e.,maps in each of which there is only one loopwhich is just the rooted edge,dependent on the edge number is obtained at the sam     

图的直径与Betti亏数

对于任意的正数Ｍ以及正整数ｄ≥４,存在直径为ｄ的ｉ－边连通无环图Ｇ使得ζ（Ｇ）≥Ｍ,其中ζ（Ｇ）是Ｇ的Ｂｅｔｔｉ亏数,ｉ＝１,２,３。     

关于图的Hamilton性

凡未作解释的术语均可参考Bondy和Murty的书。 一个图G=(V,E),如果满足如下的性质A和B,则称之为核心图。所有核心图的集合记为。 性质A存在一个整数K≥1使得:(i)V=V_o V_1 … V_k;(ii)G[V-V_o)=G[V_1)     

COUNTING ROOTED EULERIAN MAPS ON THE PROJECTIVE PLANE

1IntroductionAsurfaceisacompactclosed2-manifold.Theorielltable(non-orielltable)surfaceofgenuskisthespherewitllkhandles(crosscaPs)denotedbySk(Nk).AmapMollSk(Nk)meansthatitsunderlyinggraphnlaybedrownou(embeddedin)itsuchthatllthpairofedgesintersectataninnerpoilltalldeachfaceishomeomorphictothedisc.Amapisrootedifanedgewithadirectiollalongtheedge,alldasideoftl1eedgeisdistinguisl1ed.Tworootedmapsareconsideredtobethesal11eifthereisanisomorphismpreserviIlgtl1erooting.ArootedEuleriall1llapissuchaon…     

A NOTE ON THE NUMBER OF BIPARTITE PLANAR MAPS

Let H_(n,m) be the number of rooted non-isomorphic bipartite planar maps with m edges and the valency of the rooted face being 2n. This note provides the following results:(Ⅰ)for n≥2,whereMeanwhile, the combinatorial identity(Ⅱ)is also found. In what mentioned above, α(s, t,) and β(s, t) are expressed by the following finite sums with all the terms positive:     

关于图的最大亏格的结果

提供了一类新的上可嵌入图类,并且得到了一类直径为2的二连通伪图以及一类直径为4的重图的最大亏格的紧下界,这推广了Skoviera的一个结果．     

关于3—正则子图问题的一个注记

这篇注记证明判断一个图是否有３－正则子图的问题，即使对于节点次不超过４的平面力，仍然是ＮＰ－完全的，而且，此结果是最好的可能。