1-可嵌入曲面的图的边染色北大核心CSCD

一个图称为是1-可嵌入曲面的,当且仅当它可以画在一个曲面上,使得它的任何一条边最多交叉另外一条边.x′(G)和△(G)分别表示图G的边色数和最大度.给定图G是1-可嵌入到欧拉示性数x(∑)≥0的曲面∑上的图.如果△(G)≥8且不含4-圈或者△(G)≥7且围长g(G)≥4,则图G满足等式△(G)=x′(G),其中,g(G)表示图G中最短圈的长度.     

1-可嵌入曲面的图的边染色

一个图称为是1-可嵌入曲面的,当且仅当它可以画在一个曲面上,使得它的任何一条边最多交叉另外一条边.x′(G)和△(G)分别表示图G的边色数和最大度.给定图G是1-可嵌入到欧拉示性数x(∑)≥0的曲面∑上的图.如果△(G)≥8且不含4-圈或者△(G)≥7且围长g(G)≥4,则图G满足等式△(G)=x′(G),其中,g(G)表示图G中最短圈的长度.     

恰有k条非基本边的极小3连通图

设G是简单3连通图．G\e(删除边e)和G/e(收缩边e)都不是简单3连通图,则e称为G的基本边．对于3连通图中的非基本边．Tutte证明了：唯一没有非基本边的简单3连通图是轮．Oxley和Wu确定了至多有3条非基本边的所有极小3连通图以及恰有4条非基本的极小3连通图．Reid与Wu确定了至多有5条非基本边的极小3连通图．在本文中,我们在极小3连通图中定义了三种运算,然后通过轮利用这些运算的逆运算给出恰有k(k■2)条非基本边的极小3连通图的一种构造方法．     

关于图的定向4—边形嵌入

本文中考虑的图均是连通的．没有重边和环的图称为简单的．若Ｘ为一个图Ｇ的边子集,记号 Ｇ＼表示 Ｇ中去掉 Ｘ中的所有边后所得到的图．有关图的基本术语和记号均同［１］．Ｐｉｓａｎｋｉ在［２］中研究正则偶图的定向４－边形嵌入．所谓一个图Ｇ的定向４－边形嵌入是指Ｇ到某定向曲面Ｓ的一个２－胞腔嵌入使得Ｇ在Ｓ上的每个面的边界是Ｇ中一个长为４的圈（这里,Ｇ中的圈是Ｇ的一条点不交的闭迹）．若Ｇ为简单偶图,因Ｇ中不含长为１,２和３的圈,由Ｅｕｌｅｒ公式确定Ｇ有定向４－边形嵌入等价确定了Ｇ的最小亏格嵌入．关于这类问题…     

图的最大亏格的一个性质

本文所考虑的图均指有限元向图，没有解释的术语和记号同[1]．一个图称为简单图如果不含重边及环．曲面S这里指一个紧的，连通的，2－维闭流形（定向或不可定向），其亏格记为g（S）．连通图G在曲面S上的一个2－胞腔嵌入意指存在一个1－1连续映射h：G→S使得S＼h（G）的每个连通分支与圆盘拓扑同胚．连通图G的定向亏格γ（G）（或不可定向亏格γ（G））是指最小的整数k使得G在亏格为k的定向（或不可走向）曲面S上有2－胞腔嵌入；而图G的最大定向亏格，也常称之为最大亏格，记为γM（G）,是指最大的整数k使得G在亏格为k定向曲面S上有…     

图论与中学数学竞赛(二)

六平面图平面图一个图G,如果能够把它画在平面上,且除端点外任意两条边均不相交则称G可以嵌入平面,如果图G可以嵌入平面,则称G为可平面图可平面图在平面上的一个嵌入称为一个平面图,如图17—a所示的图G是一个可平面图。图17-b所示的图G是G的一个平面嵌入即平面图。     

边着色路到完全图的嵌入

一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”.     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

IC-平面图为第一类图的一个充分条件

图G的一个正常k-边染色是指一个映射Φ:E(G)→{1,2,…,k},使得任意两条相邻的边x,y∈E(G)满足Φ(x)≠Φ(y).使得G具有正常k-边染色的最小正整数k称为图G的边色数,记为χ'(G).著名Vizing定理证明每个简单图G的边色数χ'(G)要么等于最大度Δ(G)要么等于Δ(G)+1.这个定理将所有的图分成了两类:第一类图满足关系式χ'(G)=Δ(G),第二类图满足关系式χ'(G)=Δ(G)十1.本文主要讨论特殊1-平面图的正常边染色问题.1-平面图G是指G能够嵌入到平面上使得G的任意一条边最多被交叉一次.1-平面图G按照上述条件的一种画法称为G的一种1-平面嵌入.所以1-平面图中的每个交叉点w都是由两条边相交所得,从而每个交叉点w都对应着两条相交边,同时也对应着由这两条相交边的四个端点组成的集合ψ(w).如果1-平面图的一个1-平面嵌入中任意两个交叉点w和w'满足ψ(w)∩ψ(w')=Φ,那么称此1-平面图为IC-平面图.在本文中,通过观察分析Δ-临界图和不含相邻弦6-圈的IC-平面图的结构,应用权值转移方法证明了任何最大度为7且不含相邻弦6-圈的IC-平面图G是第一类图.     

上可嵌入性，边独立数与围长

结合边连通性,研究边独立数与上可嵌入性之间的关系,得到如下结果：设G为七一边连通图,围长为g,若α＇（G）≤（（k-1）^2＋2）[g/2]＋1-（-1）^g/2（（k-1）（k-2）＋1）-1,其中k=1,2,3,α＇（G）表示图G的边独立数,则G是上可嵌入的,且上界是最好的．这推广了相关结果．     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

图的边覆盖染色中的分类问题(英文)

设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全 r分图的分类问题     

Acyclic edge coloring of triangle-free 1-planar graphs

A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ a(G), is the least number of colors such that G has an acyclic edge coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that χ a(G) ≤Δ(G) + 22, if G is a triangle-free 1-planar graph.     

On Spectral Integral Variations of Graphs

Let G be a general graph. The spectrum S ( G ) of G is defined to be the spectrum of its Laplacian matrix. Let G + e be the graph obtained from G by adding an edge or a loop e . We study in this paper when the spectral variation between G and G + e is integral and obtain some equivalent conditions, through which a new Laplacian integral graph can be constructed from a known Laplacian integral graph by adding an edge.     

On Spectral Integral Variations of Graphs

Let G be a general graph. The spectrum S ( G ) of G is defined to be the spectrum of its Laplacian matrix. Let G + e be the graph obtained from G by adding an edge or a loop e . We study in this paper when the spectral variation between G and G + e is integral and obtain some equivalent conditions, through which a new Laplacian integral graph can be constructed from a known Laplacian integral graph by adding an edge.     

两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.     

The Gauss code problem off the plane

The classical Gauss code problem asks to characterize which cyclic sequences arise as the vertex sequence of the straight-ahead path of a 4-regular graph embedded in the plane This problem is generalized to certain 4 regular graphs in arbitrary surfacesA characterization is given for the existence of a 4-regular graph in a specified surface yielding the specified sequence This characterization is obtained using a generalization of Shank's left-right paths     

正则图的限制性边连通度

将连通图分离成阶至少为二的分支之并的边割称为限制性边割,最小限制性边割的阶称为限制性边连通度. 用λ′(G)表示限制性连通度,则λ′(G)≤ξ(G),其中ξ(G)表示最小边度. 如果上式等号成立,则称G是极大限制性边连通的. 本文证明了当k＞|G|/2时,k正则图G是极大限制性边连通的,其中k≥2, |G|≥4; k的下界在某种程度上是不可改进的.     

图的邻点可区别无圈边染色的一个界

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.应用概率的方法得到了图G的一个邻点可区别无圈边色数的上界,其中图G为无孤立边的图.