共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
消去图、覆盖图和均匀图的若干结果 总被引:2,自引:0,他引:2
设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献
3.
1991年刘振宏和李明楚在南京大学召开的首届哈密顿图研讨会的综述文章中说"要给出一个一般图具有哈密顿圈的充分条件是一件非常不容易的事"。因哈密顿图是含哈密顿圈的图类,如此哈密顿图主要有六个方向:哈密顿圈、哈密顿连通、泛圈图、点泛圈图、泛连通图、最短路径泛圈图。本文中,我们就给出一般图的这些领域新进展的小综述。 相似文献
4.
5.
孙荣国 《高校应用数学学报(A辑)》1994,(3):335-337
本文给出了书本图B2m的m种不同的相继标号和B4m+1的m种不同的相继标号。因而,书本图Bm是相继图的充分条件为:m>1且m≠(3mod4)。这一条件也是书本图Bm是协调图的充要条件。 相似文献
6.
8.
9.
双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值. 确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果:任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图. 利用这两个结果,从已知紧图可构造出无穷多个紧图族. 相似文献
10.
本文所讨论的图均为无向、有限简单图。文中没有指明的记号、术语见[3]。图G的欧拉生成子图是一条经过G的所有顶点的闭迹,以下简称S-闭迹。 相似文献
11.
温一慧 《数学的实践与认识》2008,38(15)
通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果. 相似文献
12.
Ayman Badawi 《代数通讯》2015,43(1):43-50
Let A be a commutative ring with nonzero identity, 1 ≤ n < ∞ be an integer, and R = A × A × … ×A (n times). The total dot product graph of R is the (undirected) graph TD(R) with vertices R* = R?{(0, 0,…, 0)}, and two distinct vertices x and y are adjacent if and only if x·y = 0 ∈ A (where x·y denote the normal dot product of x and y). Let Z(R) denote the set of all zero-divisors of R. Then the zero-divisor dot product graph of R is the induced subgraph ZD(R) of TD(R) with vertices Z(R)* = Z(R)?{(0, 0,…, 0)}. It follows that each edge (path) of the classical zero-divisor graph Γ(R) is an edge (path) of ZD(R). We observe that if n = 1, then TD(R) is a disconnected graph and ZD(R) is identical to the well-known zero-divisor graph of R in the sense of Beck–Anderson–Livingston, and hence it is connected. In this paper, we study both graphs TD(R) and ZD(R). For a commutative ring A and n ≥ 3, we show that TD(R) (ZD(R)) is connected with diameter two (at most three) and with girth three. Among other things, for n ≥ 2, we show that ZD(R) is identical to the zero-divisor graph of R if and only if either n = 2 and A is an integral domain or R is ring-isomorphic to ?2 × ?2 × ?2. 相似文献
13.
A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P4, 2K2, and C4 as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G1 and G2, then G is perfectly orderable whenever G1 and G2 are both P4‐free and 2K2‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: if G1 and G2 are two edge‐disjoint graphs that are P4‐free and 2K2‐free, then the union of G1 and G2 is perfectly orderable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000 相似文献
14.
证明了对于正整数k,n,si,ti(si,ti≥2,i=1,2,…,n),图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d(d≥2),k≠0(roodd)及n,si,ti(si,ti≥2,i=1,2,…,n),图n/U/i=1,Ksi,ti是(k,d)-算术图,前一结论推广了文[6]的相应结果。 相似文献
15.
《Journal of Graph Theory》2018,87(3):317-332
We describe the missing class of the hierarchy of mixed unit interval graphs. This class is generated by the intersection graphs of families of unit intervals that are allowed to be closed, open, and left‐closed‐right‐open. (By symmetry, considering closed, open, and right‐closed‐left‐open unit intervals generates the same class.) We show that this class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic‐time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also show that the algorithm from Shuchat et al. [8] directly extends to provide a quadratic‐time algorithm to recognize the class of mixed unit interval graphs. 相似文献
16.
We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n2 log5 n) time and O(n2) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs. 相似文献
18.
李学文 《数学的实践与认识》2005,35(8):233-238
群G关于S的有向Cayley图X=Cay(G,S)称为pk阶有向循环图,若G是pk阶循环群.利用有限群论和图论的较深刻的结果,对p2阶弧传递(有向)循环图的正规性条件进行了讨论,证明了任一p2阶弧传递(有向)循环图是正规的当且仅当(|Aut(G,S)|,p)=1. 相似文献
19.
研究了含有多个圈的图的邻接矩阵的秩.将k(k≥2)条点不交的路,首和尾分别粘合得到的图称为Θ-图.用Γ(k-1)表示含有Θ-图作为导出子图的(k-1)-圈图的集合,而用C(η,k)表示含有n个顶点和k个边不交的圈的图的集合.确定了Γ(k-1)中秩等于5和6的图以及C(n,k)中秩等于4,5和6的图. 相似文献
20.
指出了《若干并图的优美标号》一文中的一些不当之处证明了对任意的正整数m和大于1的自然数p,q非连通图(P_2∨(K_m)~(1/2)∪K_(p,q)是优美图. 相似文献