共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
3.
4.
四类粘接图的niche数 总被引:2,自引:0,他引:2
唐廷载 《高校应用数学学报(A辑)》1998,13(4):479-484
粘接图G1(u)⊙G2(υ)是将图G1的顶点u与图G2的顶点υ重合而得到的一个图.本文证明Pm(u)⊙Kn(u是Pm的起点或终点,n≥2),Km⊙Kn(m,n≥2),Pm(u)⊙Cn(n≥3)和Km⊙Cn(m≥2,n≥3)这四类图都是niche图. 相似文献
5.
探求椭圆面积公式的另一种方法 总被引:4,自引:0,他引:4
关于椭圆面积公式的探求有多种方法 ,不少的刊物上曾刊登过相关的研究文章 ,本文给出另一种探求方法 .图 1如图 1所示 ,设椭圆方程为 x2a2 + y2b2 =1 (a>b>0 ) ,Ak(xk,yk) (k=1 ,2 ,3,...n)是椭圆上的n个点 ,A1 A2 ...An 是椭圆的内接n边形 ,当n→∞时 ,|AkAk+1 |max =ln → 0 ,则 x2 ka2 + y2 kb2 =1 ,由此得x2 k + abyk2 =a2 ,可见 ,点Bk xk,abyk (k =1 ,2 ,3...n)是圆x2 +y2 =a2 上的n个点 ,且这n个点在圆上的排列顺序与点Ak(k=1 ,2 ,3...n)在椭圆上的排列顺序相同 ,所以 ,B1 B2 ...Bn 是圆x2 +y2 =a2 的内接n边形 .连接OA1 ,OA2… 相似文献
6.
也谈椭圆外切n边形面积的最小值 总被引:1,自引:0,他引:1
文 [1]通过引理 1、引理 2虽然给出了椭圆外切n边形面积的最小值 ,但没有给出取到最小值时 ,外切n边形的几何性质及作图方法 .本文通过对圆外切n边形面积最小值的探讨 ,回答了上述问题 .引理 外切于圆的所有n边形中 ,正n边形的面积最小 ,且最小值为rntan πn(n≥ 3) .图 1 圆外切n边形证 如图 1,设n边形P1P2 …Pn 为半径为r的外切n边形 ,A1,A2 ,… ,An 为切点 ,则由圆的切线性质可知 ,n边形P1P2 …Pn 的面积为S =2S△A1OP1+ 2S△A2 OP2+… + 2S△AnOPn=r·tan∠A1OP1+r·tan∠A2 OP2 +… +r·tan∠AnOPn.因为n≥ 3,所以∠Ai… 相似文献
7.
子图识别问题(SRP)就是在一个图G中确定并寻找是否存在和另一个图H相同构的子图.本文将引入图的层分解概念,并以此为基础建立识别图的同构子图的算法.该算法的复杂性为O(n(△-1)^k-1),其中△是图G的度,即G中点的最大度,n,k分别是图G,H的阶. 相似文献
8.
本文给出了Frobenius群Z_(2n~2 2n 1)■Z_4的一类四度Frobenius图.沿用方、李和Praeger的方法,计算出了这一类图的直径和型(定理3.2). 相似文献
9.
P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径;f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径.这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3;若t为奇数,则C(t,n)≤(n-8)/(t 1) 3;若t为偶数,则C(t,n)≤(n-7)/(t 2) 3.特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」.最后,证明了:若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4.这些改进了某些已知结果. 相似文献
10.
令f(n)为恰有n个顶点,任意两个循环长度都不相等的图的最多边数.1975年,Erdos提出确定f(n)的问题(见[1]P274,Problem11).1986年.Y.Shi证明了对任意自然数.≥3,有f(n)≥n [(√8n-23 1/1)/2],且当3≤n≤17时.等号成立.进而猜想:对于任何自然数n≥3,上述等式都成立.本文对该猜想给出一个反例。 相似文献
11.
Guanghui Wang Guizhen Liu Jiguo Yu 《Journal of Applied Mathematics and Computing》2006,20(1-2):149-156
The circular list coloring is a circular version of list colorings of graphs. Let χinc,l denote the circular choosability(or the circular list chromatic number). In this paper, the circular choosability of outer planar graphs and odd wheel is discussed. 相似文献
12.
The circular choosability or circular list chromatic number of a graph is a list-version of the circular chromatic number, that was introduced by Mohar in 2002 and has been studied by several groups of authors since then. One of the nice properties that the circular chromatic number enjoys is that it is a rational number for all finite graphs G, and a fundamental question, posed by Zhu and reiterated by others, is whether the same holds for the circular choosability. In this paper we show that this is indeed the case. 相似文献
13.
Frédéric Havet Ross J. Kang Tobias Müller Jean‐Sébastien Sereni 《Journal of Graph Theory》2009,61(4):241-270
We study circular choosability, a notion recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch(G)=O(ch(G)+ln|V(G)|) for every graph G. We investigate a generalization of circular choosability, the circular f‐choosability, where f is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of τ ? sup{cch(G) : G is planar}, and we prove that 6≤τ≤8, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 241–270, 2009 相似文献
14.
LǖEnyue ZhangKemin 《高校应用数学学报(英文版)》1999,14(1):108-116
In this paper, the choosability of outerplanar graphs, 1-tree and strong 1-outerplanargraphs have been described completely. A precise upper bound of the list chromatic number of 1-outerplanar graphs is given, and that every 1-outerplanar graph with girth at least 4 is 3-choosable is proved. 相似文献
15.
Serguei Norine 《Journal of Graph Theory》2008,58(3):261-269
We answer two questions of Zhu on circular choosability of graphs. We show that the circular list chromatic number of an even cycle is equal to 2 and give an example of a graph for which the infimum in the definition of the circular list chromatic number is not attained. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:261‐269, 2008 相似文献
16.
A structural theorem for planar graphs with some applications 总被引:1,自引:0,他引:1
Huiyu ShengYingqian Wang 《Discrete Applied Mathematics》2011,159(11):1183-1187
In this note, we prove a structural theorem for planar graphs, namely that every planar graph has one of four possible configurations: (1) a vertex of degree 1, (2) intersecting triangles, (3) an edge xy with d(x)+d(y)≤9, (4) a 2-alternating cycle. Applying this theorem, new moderate results on edge choosability, total choosability, edge-partitions and linear arboricity of planar graphs are obtained. 相似文献
17.
We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically (3, 1)*-choosable (i.e. they are acyclically 3-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically (2, 5)*-choosable (i.e. they are acyclically 2-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability and acyclic improper choosability of planar graphs are equivalent notions. 相似文献
18.
循环着色是普通着色的推广.本文中,我们研究了一类平面图-“花图”的循环着色问题,证明了由2r 1个长为2n 1的圈构成的“辐路”长度为m的花图Fr,m,n的循环色数是2 1/(n-m/2),并证明了在这类图中去掉任何一个点或边后,循环色数都严格减少但普通色数不减少,即这类图是循环色临界的但不是普通色临界的.同时,我们还研究了循环着色与图Gkd中的链之间的关系,给出了两个等价的条件. 相似文献
19.
O.V. Borodin 《Discrete Mathematics》2013,313(4):517-539
After a brief historical account, a few simple structural theorems about plane graphs useful for coloring are stated, and two simple applications of discharging are given. Afterwards, the following types of proper colorings of plane graphs are discussed, both in their classical and choosability (list coloring) versions: simultaneous colorings of vertices, edges, and faces (in all possible combinations, including total coloring), edge-coloring, cyclic coloring (all vertices in any small face have different colors), 3-coloring, acyclic coloring (no 2-colored cycles), oriented coloring (homomorphism of directed graphs to small tournaments), a special case of circular coloring (the colors are points of a small cycle, and the colors of any two adjacent vertices must be nearly opposite on this cycle), 2-distance coloring (no 2-colored paths on three vertices), and star coloring (no 2-colored paths on four vertices). The only improper coloring discussed is injective coloring (any two vertices having a common neighbor should have distinct colors). 相似文献
20.
Let S(r) denote a circle of circumference r. The circular consecutive choosability chcc(G) of a graph G is the least real number t such that for any r≥χc(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then chcc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then chcc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that chcc(G) = 2 holds for all cycles and for K2, n with n≥2. On the other hand, we prove that chcc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011 相似文献