共查询到20条相似文献,搜索用时 93 毫秒
1.
设G为2-连通平面图,若存在G的面f0,其中f0的边界构成的圈上无弦且V(f0)中的点的度至少为3,使得在G中去掉f0边界上的所有边后得到的图为除V(f0)中的点外度不小于3的树T,则称G为伪-Halin图;若V(f0)中的点全为3度点,则称G为Halin-图.本文研究了这类图的完备色数,并证明了对△(G)≥ 6的伪-Halin图 G有 XC(C)=△(G)+1.其中△(G)和XC(G)分别表示G的最大度和完备色数. 相似文献
2.
图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}.χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数.对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图.本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度. 相似文献
3.
4.
高度图的独立集复形 总被引:3,自引:0,他引:3
给定图G,称以G的所有独立集为单形的抽象复形I(G)为G的独立集复形.如果两个图G和H的独立集复形I(G)和I(H)的各阶同调群都是同构的,则称两个图是独立同调的.J(G)表示Gc的连通分支数,J3K2(G)表示Gc中同构于(3H2)c的连通分支数.本文研究了最小次δ(G)至少为其阶数|V(G)|减5的图G的独立集复形的结构,对满足δ(G)≥|V(C)|5,δ(H)≥|V(H)|-5的两个图G和H,(I)证明了,G和H独立同调的充要条件为J(G)=J(H),J3K2(G)=J3K2(H),且I(G)和I(H)的Euler示性数相同.(Ⅱ)给出了一个在图上计算I(G)的一维Betti数的方法,得到了一个I(G)是无圈复形的充要条件 相似文献
5.
最大度不大于5的Halin-图的点强全染色 总被引:5,自引:0,他引:5
图G(V,E)的一正常k-全染色f称为G(V,E)的一k-点强全染色当且仅当任意(
A)v∈V(G),N[v]中的元素染不同色,其中N[v]={u|uv∈V(G)}U{v},并且XusT(G)=min{k|存在G的k-点强全染色}称为G(V,E)的点强全色数.本文得到了△(G)≤5的Halin-图G(V.E)的XusT(G),并提出如下猜想设G(V,E)为每一连通分支的阶数不小于6的图,则XusT(G)≤△(G)+2,其中△(G)表示图G的最大度. 相似文献
6.
3-γ-临界图G中关于i(G)=γ(G)的一个充分条件 总被引:1,自引:0,他引:1
如果图G满足γ(G)=k且对图G中任两个相邻的点x,y有γ(G+xy)=k-1,则称图G为k-γ-临界图,如果图G满足γ(G)=k且对图G中任何距离为d的两点x,y有γ(G+xy)=k-1,则称图G为k-(γ,d)-临界图。Sumner和Blitch猜想在3-γ-临界图中有γ(G)=i(G).Oellermann和Swart猜想3-(γ,2)-临界图中有γ(G)=i(G),这篇文章中我们提出3-γ-临界图中使γ(G)=i(G)的一个充分条件。 相似文献
7.
如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了:若G是一个最大度△(G)≠5,6的平面图,则lc(G)≤2△(G). 相似文献
8.
9.
半正规n-极大子群对有限群结构的影响 总被引:1,自引:0,他引:1
设△↓n(G)为有限群G的n次极大子群的全体。1.若△↓4(G)中的子群均在G中半正规,则下述结论之一成立:(1)G是可解群;(2)G/φ(G)=A5,(3)G/φ(G)=PSL(2,13);(4)G/φ(G)=PSL(2,p),满足p=4p1 1=6p2-1,这里p1≥43,p2≥29;(5)G/φ(G)=PSL(2,p),满足p=6p1 1=4p2-1,这里p1≥7,p2≥11.2。2.设3不属于π(G),若△↓(G)中的子群均在G中半正规,则G是可解群,或G/φ(G)=Sz(2^3). 相似文献
10.
根据图的邻点可区别VE-全染色的定义和性质,用概率方法研究了图的邻点可区别VE-全染色,并给出了图的邻点可区别VE-全色数的一个上界.如果δ≥7且△≥25,则有xatue(G)≤7△,其中δ是图G的最小度,△是图G的最大度. 相似文献
11.
Arthur M. Farley Andrzej Proskurowski Mirosława Skowrońska Maciej M. Sysło 《Graphs and Combinatorics》1999,15(4):393-404
An amalgam is obtained from two Halin graphs having skirting cycles of the same length. We are interested in hamiltonicity
of amalgams constructed from two identical Halin graphs without any shift along the skirting cycle. We establish hamiltonicity
of amalagams constructed from cubic Halin graphs. We give a sufficient condition for hamiltonicity of non-cubic amalgams and
characterize infinite classes of non-Hamiltonian amalgams. We also characterize hamiltonicity of amalgams constructed by shifting
the component Halin graphs by one and of general amalgams of higher degree.
Received: June 23, 1997 相似文献
12.
The Q-index of a graph G is the largest eigenvalue q(G) of its signless Laplacian matrix Q(G). In this paper, we prove that the wheel graph W_n = K_1 ∨C_(n-1)is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n. 相似文献
13.
A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively. 相似文献
14.
In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparating cycles. In particular, some known results such as P.F. Stadler's work on Halin graphs [Minimum cycle bases of Halin graphs, J. Graph Theory 43 (2003) 150-155] and Leydold and Stadler's results on outer-planar graphs [Minimum cycle bases of outerplanar graphs, Electronic J. Combin. 5(16) (1998) 14] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpolation theorem for the number of one-sided cycles contained in MCB of an embedded graph. 相似文献
15.
16.
张磊 《数学的实践与认识》2021,(1):302-307
设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件. 相似文献
17.
18.
A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others. 相似文献
19.
1. IntroductionSince WOodall gave out the concept of biIldi11g Ilu1lJber in 1973[l] ! the bil1ding nunlber fOrsome specia1 classes have beeIl studied by Kane and WaIlg Jianfang[']. Mirolawa Skowronskahave studied the binding number of Halin-graph[']. ZI1ang Zhongfu, Liu Li1lzhong andZhang Jianxun have extended the bil1di11g nuInber to the edges and studied tlle edge-bindingnumber of path, cycle, coInplete grapl1. I1l this paper, we study the edge-binding number ofouter plane graph, Ha… 相似文献
20.
[a,b]-对等图的范-型条件 总被引:1,自引:0,他引:1
既是[a,b]-覆盖又是[a,b]-消去的图称为[a,b]-对等图.设1≤aan+1a+b,则G为[a,b]-对等图.给出了一个图是[a,b]-对等图的关于范-型条件及邻域并的若干充分条件,并指出定理中的条件在一定意义上是最好可能的. 相似文献