首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 93 毫秒
1.
张欣  刘维婵 《运筹学学报》2017,21(4):135-152
如果图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-平面图.现主要介绍关于以上四类图在染色方面的结果.  相似文献   

2.
图G的点荫度a(G)是G的使得每个子集诱导一个森林的顶点划分中子集的最少个数.我们熟知对任何平面图G,a(G)≤3,且对任何直径最大是2的平面图有a(G)≤2.文献[European J.Combin.,2008,29(4):1064-1075]中给出下列猜想:任何没有3-圈的平面图都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.本文证明了任何2-边连通上可嵌入的3-正则图G(G≠K_4)都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.  相似文献   

3.
对于简单图G=(V,E),顶点子集F■V,如果由V\F导出的子图G′= (V\F,E′)是不含圈的,则称F是图G的一个反馈点集.点数最少的反馈点集称图的最小反馈点集,最小的点数称为反馈数.文章给出了交叉立方体网络的一个等价定义,用递归的方法构造出交叉立方体网络的诱导树,证明了诱导树的阶数Fibonacci数,进而得到叉立方体网络反馈数的上下界.  相似文献   

4.
折叠立方体网络的最小反馈点集   总被引:1,自引:0,他引:1  
对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1  相似文献   

5.
假设火在图G的某个顶点燃起,消防员每步最多可以防护k个顶点,然后火蔓延到所有未被防护的邻点.当火随机地在图G的一个顶点燃起时,消防员最多能防护的顶点数的平均比率称为图G的k-存活率,记为ρk(G).如果图G能画在平面上使得每两对交叉边至多有一个公共顶点,那么称G是NIC-平面图.本文证明了NIC-平面图G有ρ5(G)> 1/73.  相似文献   

6.
若能将图$G$画在一个平面上,使得任何两条边仅在顶点处相交,则称$G$是平面图.本文刻画了第二大特征值小于$\frac{\sqrt{5}-1}{2}$的所有无孤立点的平面图.  相似文献   

7.
一个平面图G被称为1-外平面图如果存在一个顶点u 使得G- u 是一个外平面图.本文证明了Melnikov 的边面染色猜想对所有1-外平面图成立.  相似文献   

8.
对简单有向图D=(V,E),顶点子集F∈V,如果由V\F导出的子图不含有向圈,则称F是D的反馈点集。点数最小的子集F称为最小反馈点集。最小的点数称为反馈数。本利用Kautz最小轨道的方法确定出了Kautz有向图K(d,k)反馈数的一个下界和上界。并且具体给出了当k≤3时的反馈数。  相似文献   

9.
设G是一个由n个顶点,m条边构成的简单连通图.如果图G所有顶点的度相同,则我们称图G是正则图,反之,称图G是不规则图.对于一个不规则图G,由其不变量定义的度偏差为s(G)=∑_(i=1)^(n)|d_(i)-2m/n|,其中d_(i)表示G的第i个顶点的度.本文给出极大外平面图的度偏差的极大值和极小值,并刻画其对应的极值图.  相似文献   

10.
关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.  相似文献   

11.
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 vertex set of a 3-regular simple graph is provided.  相似文献   

12.
1IntroductionLetG=(VE)beaconnectedsimplegraph.AsubsetFofvertexsetViscalIedafeedbackvertexsetofGifthegraPhGFisaf0rest.ThecardinaIity0faminimumfeedbackvertexset0fGisdenotedbyf(G).AvertexsubsetJofvertexsetViscaJledallonseparatingindependentsetofG,ifJisanilldependentsetofVandGJisconnected.Thema-xiammcardinalityofnollseparatingindependelltsetofGisden0tedbyz(G)andiscalledthenonseparatingindepelldentnumberofG,AgraphGiscalledacactusifGisc0nnectedandanytwocyclesofGaredisjoint.Avertexvofacon…  相似文献   

13.
A subset of the vertex set of a graph is a feedback vertex set of thegraph if the resulting graph is a forest after removed the vertexsubset from the graph. A polynomial algorithm for finding a minimumfeedback vertex set of a 3-regular simple graph is provided.  相似文献   

14.
A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in seriesparallel graphs and present a linear-time exact algorithm to solve it.  相似文献   

15.
对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.  相似文献   

16.
A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V (G) S is also adjacent to a vertex in V (G) S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.  相似文献   

17.
Let G be a finite group and let S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G×{0, 1} and edge set {(g, 0) (sg, 1) : g∈G, s ∈ S}. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if every minimum vertex cut creates two components, one of which is an isolated vertex. In this paper, super-connected and/or hyper-connected cubic Bi-Cayley graphs are characterized.  相似文献   

18.
A sufficient condition is given for a planar graph to be 4-colorable. This condition is in terms of the sums of the degrees of a subset of the vertex set of the graph.  相似文献   

19.
20.
<正>Total Restrained Bondage in Graphs Nader JAFARI RAD Roslan HASNI Joanna RACZEK Lutz VOLKMANN Abstract A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V(G)-S is also adjacent to a vertex in V(G)-S.The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G.In this paper we initiate the study of  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号