共查询到19条相似文献,搜索用时 62 毫秒
1.
证明了风车图K4n3(n∈自然数)及其它几类强协调图,并给出了统一的强协调值标号,最后证明了Kn-e(n≥6)是非强协调图. 相似文献
2.
4.
5.
这里考虑的一切图均为简单的,以V(G),E(G)分别表示图G的节点集和边集。设H是G的子图,x∈V(H),用d_H(x)表示H中与节点x相邻节点的个数。如果e=(x,y)∈E(H),x,y是e的端点,则让d_H(e)=d_H(x)+d_H(y)。设A、B是V(G)的两个节点不交的子集,用E(A:B)表示G中一端在A中另一端在B中边的个数。设M是G 相似文献
6.
7.
9.
关于图与圈之并图的圈唯一性 总被引:2,自引:0,他引:2
Farrell[1]引进图 G 的圈多项式 c(G;■).文[6]猜测:轮形图 W_8是圈唯一的.本文中我们证明上述猜测为真且讨论了某些图与圈之并图的圈唯一性. 相似文献
10.
图的圈基是图的一个重要结构,一个圈基的长度是该圈基中所有圈的长度之和,本讲座了简单图的圈基长度的最大值,得到了如下结果:设基圈数为k,顶点数为n的简单图的圈基长度最大值为C^*,i)若k≥4且n ≥k 2时,C^*-kn;Ⅱ)若k=2,3,则对任意n≥4,C^*=kn-1,Ⅲ)若n(n≥5)为奇数,则对k(k≥4)的所有可能值,C^*=kn。 相似文献
11.
Andrzej ?ak 《Discrete Mathematics》2009,309(20):6055-6064
We consider the following generalization of the concept of harmonious graphs. Given a graph G=(V,E) and a positive integer t≥|E|, a function is called a t-harmonious labeling of G if is injective for t≥|V| or surjective for t<|V|, and for all distinct edges vw,xy∈E(G). Then the smallest possible t such that G has a t-harmonious labeling is named the harmonious order of G. We determine the harmonious order of some non-harmonious graphs, such as complete graphs Kn (n≥5), complete bipartite graphs Km,n (m,n>1), even cycles Cn, some powers of paths , disjoint unions of triangles nK3 (n even). We also present some general results concerning harmonious order of the Cartesian product of two given graphs or harmonious order of the disjoint union of copies of a given graph. Furthermore, we establish an upper bound for harmonious order of trees. 相似文献
12.
For a graph G, let diff(G) = p(G) − c(G), where p(G) and c(G) denote the orders of a longest path and a longest cycle in G, respectively. Let G be a 3-connected graph of order n. In the paper, we give a best-possible lower bound to σ4(G) to assure diff(G) ≤ 1. The result settles a conjecture in J. Graph Theory 37 (2001), 137–156. 相似文献
13.
14.
We characterize edge-colored graphs in which every edge belongs to some properly colored cycle. We obtain our result by applying
a characterization of 1-extendable graphs.
Received: April, 2003 相似文献
15.
16.
Yongzhu Chen 《Discrete Mathematics》2009,309(8):2233-2163
Let G be a plane graph having no 5-cycles with a chord. If either Δ≥6, or Δ=5 and G contains no 4-cycles with a chord or no 6-cycles with a chord, then G is edge-(Δ+1)-choosable, where Δ denotes the maximum degree of G. 相似文献
17.
D.S. Franzblau 《Graphs and Combinatorics》2002,18(2):259-270
In this paper, a class of cubic planar graphs is given that have Hamiltonian cycles that can be constructed in linear time.
A member of this class is called a layered cubic planar graph, and consists of a sequence of cycles C
0
,C
1
,…,C
n
such that each pair of successive cycles, C
i
, C
i+1
, is joined by a matching. The cycles can be pictured as concentric circles, and the edges of the matchings as radial line
segments between successive circles. The subgraph bounded by two successive cycles forms a layer; each face in layer i is incident to a fixed number k
i+1
of edges in the matching in layer i+1. The problem that initially motivated this work is that of identifying classes of convex cubic polyhedra that can be easily
edge three-colored.
Received: September 21, 1998 Final version received: July 21, 1999 相似文献
18.
Ralph J. Faudree Evelyne Flandrin Michael S. Jacobson Jenő Lehel Richard H. Schelp 《Graphs and Combinatorics》2000,16(4):399-410
It will be shown that if G is a graph of order n which contains a triangle, a cycle of length n or n−1 and at least cn odd cycles of different lengths for some positive constant c, then there exists some positive constant k=k(c) such that G contains at least kn
1/6 even cycles of different lengths. Other results on the number of even cycle lengths which appear in graphs with many different
odd length cycles will be given.
Received: October 15, 1997 相似文献
19.
本文使用变分方法证明了三维标准切触球的标准勒让德扭结,至少存在一个弦连结适应于标准切触结构的任何选定切触形式,这部分证明了著名的阿诺德弦猜想。 相似文献