共查询到19条相似文献,搜索用时 125 毫秒
1.
结合 4-边形 2 -因子条件 ,确定了一类点的度在 modulo4下值为 0 ,1的上可嵌入图类 .从而综合已有的结果 ,较完整地刻划了这类图的上可嵌入性情况 相似文献
2.
3.
4.
拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作. 相似文献
5.
结合4-边形2-因子条件,确定了一类点的度在modulo4下值为0,1的上可嵌入图类,从而综合已有的结果,较完整地刻划了这类图的上可嵌入性情况。 相似文献
6.
设$\phi: G\rightarrow S$是图$G$在曲面$S$上的2 -胞腔嵌入. 若$G$的所有面都是依次相邻, 即嵌入图$G$的对偶图有哈密顿圈, 则将$\phi$称为一个面依次相邻的嵌入. 该文研究了在克莱茵瓶上有面依次相邻嵌入的图的最大亏格. 相似文献
7.
不依赖图的其它参数, 而主要依据图嵌入在定向曲面上的有关嵌入性质, 该文研究图的最大亏格. 相似文献
8.
关于图的余树的奇连通分支数的内插定理 总被引:4,自引:0,他引:4
本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式. 相似文献
9.
图G的顶点A-划分是指:G的顶点集划分{V1,V2,···,Vs},其中G[Vi](1≤i≤s)为多重完全图或多重完全二部图.文中结合图的顶点A-划分,顶点度及边连通性等条件确定了一些新的上可嵌入图类,从而将已有类似结果进行了推广,且完整地刻画了这类图的上可嵌入性情况. 相似文献
10.
11.
12.
We study degree spectra of structures with respect to the bi‐embeddability relation. The bi‐embeddability spectrum of a structure is the family of Turing degrees of its bi‐embeddable copies. To facilitate our study we introduce the notions of bi‐embeddable triviality and basis of a spectrum. Using bi‐embeddable triviality we show that several known families of degrees are bi‐embeddability spectra of structures. We then characterize the bi‐embeddability spectra of linear orderings and study bases of bi‐embeddability spectra of strongly locally finite graphs. 相似文献
13.
14.
Mekkia Kouider 《Discrete Mathematics》2006,306(7):617-623
In this paper we obtain some upper bounds for the b-chromatic number of K1,s-free graphs, graphs with given minimum clique partition and bipartite graphs. These bounds are given in terms of either the clique number or the chromatic number of a graph or the biclique number for a bipartite graph. We show that all the bounds are tight. 相似文献
15.
Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is calledΓ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) = IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result. 相似文献
16.
17.
K. V. Vorob’ev 《Journal of Applied and Industrial Mathematics》2014,8(1):136-142
Under study is the relationship between the eigenfunctions of the Johnson and Hamming graphs. An eigenfunction of a graph is an eigenvector of its adjacency matrix with some eigenvalue; moreover, an eigenfunction can be identically zero. We find a criterion for the embeddability of an eigenfunction of the Johnson graph J(n, w) with a given eigenvalue into a certain eigenfunction of the Hamming graph with a given eigenvalue. 相似文献
18.
19.