检索结果-南通市图书馆

Nonseparating Independent Sets and maximum genus of Graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2022年第3期38卷 719-728页

作者： Chao YANG Han REN Er-ling WEI Center of Intelligent Computing and Applied Statistics School of MathematicsPhysics and StatisticsShanghai University of Engineering ScienceShanghai 201620China School of Mathematical Sciences East China Normal UniversityShanghai 200241China Shanghai Key Laboratory of PMMP Shanghai 200241China School of Mathematics Renmin University of ChinaBeijing 100872China

A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and G􀀀I is *** Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent *** this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular ***,we show a relationship between Z(G)and the maximum genus M(G)of a general ***,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.

关键词： nonseparating independent sets maximum genus graph embedding decycling set

A RELATIVE maximum genus GRAPH EMBEDDING AND ITS LOCAL maximum genus

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2000年第4期16卷 366-372页

作者：李德明刘彦佩 Department of Mathematics Capital Normal UniversityBeijing 100037China Department of Mathematics Northern Jiaotong UniversityBeijing 100044China

A relative embedding of a connected graph is an embedding of the graph in some surface with respect to some closed walks, each of which bounds a face of the embedding. The relative maximum genus of a connected graph is the maximum of integer k with the property that the graph has a relative embedding in the orientable surface with k handles. A polynomial algorithm is provided for constructing relative maximum genus embedding of a graph of the relative tree of the graph is planar. Under this condition, just like maximum genus embedding, a graph does not have any locally strict maximum genus.

关键词： Algorithm relative spanning tree relative embedding maximum genus

A TIGHT LOWER BOUND ON THE maximum genus OF 3-EDGE CONNECTED LOOPLESS GRAPHS

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 1999年第4期15卷 361-367页

作者：李德明刘彦佩 Department of Mathematics Capital Normal University Beijing China Department of Mathematics Northern Jiaotong University Beijing China

It is shown that the lower bound on the maximum genus of a 3-edge connected loopless graph is at least one-third of its cycle rank. Moreover, this lower bound is tight. There are infinitely such graphs attaining the b... 详细信息

关键词： maximum genus 3-edge connected loopless graph lower bound

maximum genus of the Generalized Permutation Graph

在线全文

学校读者我要写书评

暂无评论

Northeastern Mathematical Journal 2008年第3期24卷 189-195页

作者：马登举任韩 School of Science Nantong University Nantong Jiangsu 226007 Department of Mathematics East China Normal University Shanghai 200062

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.

关键词： generalized permutation graph maximum genus upper embeddable

maximum genus and Girth of a Graph

在线全文

学校读者我要写书评

暂无评论

Journal of Mathematical Research and Exposition 2000年第2期20卷 187-193页

作者：黄元秋刘彦佩湖南师范大学数学系长沙410081 北方交通大学数学系

It is known (for example, see [4]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, we establish a best upper bound on the Betti deficiency of a graph bounded... 详细信息

关键词： maximum genus Betti deficiency independece number girth.

LOWER BOUNDS ON THE maximum genus OF LOOPLESS MULTIGRAPHS

在线全文

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2000年第4期15卷 359-368页

作者： LiDeming LiuYanpei Dept.ofMath. CapitalNormalUniv.Beijing100037 Dept.ofMath. NorthernJiaotongUniv.Beijing100044

The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous kn... 详细信息

关键词： maximum genus lower bound multigraph.

A TIGHT LOWER BOUND ON THE maximum genus OF A 3-CONNECTED LOOPLESS MULTIGRAPH

在线全文

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2000年第4期15卷 369-376页

作者： LiDeming LiuYanpei Dept.ofMath. CapitalNormalUniv.Beijing100037. Dept.ofMath. NorhternJiaotongUniv.Beijing100044.

It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper ***... 详细信息

关键词： maximum genus graph connectivity.

A NOTE ON THE maximum genus OF 3-EDGE-CONNECTED NONSIMPLE GRAPHS

在线全文

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2000年第3期15卷 247-251页

作者： Huang YuanqiuDept.of Math.,Hunan Normal Univ.,Changsha 41 0 0 81 . Email:hyqq @*** Dept. of Math. Human Normal Univ. Changsha

Let G be a 3 edge connected graph (possibly with multiple edges or loops), and let γ M(G) and β(G) be the maximum genus and the Betti number of G, respectively. Then γ M(G)≥β(G)/3 can be proved and this... 详细信息

关键词： maximum genus upper embeddable Betti defficiency.

A POLYNOMIAL ALGORITHM FOR FINDING THEMINIMUM FEEDBACK VERTEX SET OF A3-REGULAR SIMPLE GRAPH

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Scientia 1999年第4期19卷 375-381页

作者：李德明刘彦佩 Department of Mathematics Capital Normal University Beijing 100037 China Department of Mathematics Northern Jiaotong University Beijing 100044 China

A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vert... 详细信息

关键词： maximum genus nonseparating independent number feedback vertex set 3-regular graph adjacency matching