共查询到20条相似文献,搜索用时 31 毫秒
1.
The Turán number of a k-uniform hypergraph H,denoted by exk(n;H),is the maximum number of edges in any k-uniform hypergraph F on n vertices which does not contain H as a subgraph.Let Cl~((k)) denote the family of all k-uniform minimal cycles of length l;S(?1,…,?r) denote the family of hypergraphs consisting of unions of r vertex disjoint minimal cycles of length ?1,…?r,respectively,and Cl~((k))denote a k-uniform linear ... 相似文献
2.
In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mTn.p/(n2) edges, where Tn.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined. 相似文献
3.
黄振杰 《数学的实践与认识》2000,30(4)
一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 . 相似文献
4.
Therese Biedl 《Discrete and Computational Geometry》2006,35(1):131-141
A flipturn on a polygon consists of reversing the order of edges inside a pocket
of the polygon, without changing lengths or slopes. Any polygon with n edges must be
convexified after at most (n − 1)! flipturns. A recent paper showed that in fact it will be
convex after at most n(n−3)/2 flipturns.We give here lower bounds.We construct a polygon
such that if pockets are chosen in a bad way, at least (n − 2)2/4 flipturns are needed to
convexify the polygon. In another construction, (n −1)2/8 flipturns are needed, regardless
of the order in which pockets are chosen. All our bounds are adaptive to a pre-specified
number of distinct slopes of the edges. 相似文献
5.
6.
Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article. 相似文献
7.
令$K_{n}^{c}$表示$n$ 个顶点的边染色完全图.
令 $\Delta^{mon}
(K_{n}^{c})$表示$K^c_{n}$的顶点上关联的同种颜色的边的最大数目.
如果$K_{n}^{c}$中的一个圈(路)上相邻的边染不同颜色,则称它为正常染色的.
B. Bollob\'{a}s和P. Erd\"{o}s (1976) 提出了如下猜想:若 $\Delta^{{mon}}
(K_{n}^{c})<\lfloor \frac{n}{2} \rfloor$, 则$K_{n}^{c}$中含有一个正常染
色的Hamilton圈. 这个猜想至今还未被证明.我们研究了上述条件下的正常染色的路和圈. 相似文献
8.
双圈图按谱半径的排序 总被引:1,自引:0,他引:1
一个n阶简单连通图G被称为双圈图,如果它的边数是n+1.记B(n)是n阶双圈图的全体.本文确定了B(n)(n≥20)中谱半径的第六大至第十大值和对应的图. 相似文献
9.
《数学季刊》2016,(2):147-154
Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained. 相似文献
10.
11.
This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding Θ(n) random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 33–42, 2003 相似文献
12.
如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数.本文得到在m=1,2,3,n≥1和m=n≥4时的均匀邻强边色数. 相似文献
13.
Kree Cole-McLaughlin Herbert Edelsbrunner John Harer Vijay Natarajan Valerio Pascucci 《Discrete and Computational Geometry》2004,32(2):231-244
Given a Morse function f over a 2-manifold with or without boundary,
the Reeb graph is obtained by contracting the connected components
of the level sets to points.
We prove tight upper and lower bounds on the
number of loops in the Reeb graph
that depend on the genus, the number of boundary components,
and whether or not the 2-manifold is orientable.
We also give an algorithm that constructs the Reeb graph in time
O(n log n), where n is the number of edges in the
triangulation used to represent the 2-manifold and the Morse function. 相似文献
14.
Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article. 相似文献
15.
16.
Derevyanko N. M. Zhukovskii M. E. Rassias M. Skorkin A. Yu. 《Doklady Mathematics》2019,100(2):478-479
Doklady Mathematics - We have proven that the maximum size k of an induced subgraph of the binomial random graph $$G(n,p)$$ with a given number of edges $$e(k)$$ (under certain conditions on this... 相似文献
17.
本文对带宽等于最小度的图的边数极值问题进行了研究,主要结果如下:对任意给定的正整数n及r(r相似文献
18.
Let G be a (molecular) graph. The Hosoya index Z(G) of G is defined as the number of subsets of the edge set E(G) in which no two edges are adjacent in G, i.e., Z(G) is the total number of matchings of G. In this paper, we determine all the connected graphs G with n + 1 ≤ Z(G) ≤ 5n ? 17 for n ≥ 19. As a byproduct, the graphs of n vertices with Hosoya index from the second smallest value to the twenty first smallest value are obtained for n ≥ 19. 相似文献
19.
20.
令f(n)为恰有n个顶点,任意两个循环长度都不相等的图的最多边数.1975年,Erdos提出确定f(n)的问题(见[1]P274,Problem11).1986年,Y.Shi证明了对任意自然数n≥3,有f(n)≥n+8n-23+1/2[],且当3≤n≤17时,等号成立.进而猜想:对于任何自然数n≥3,上述等式都成立.本文对该猜想给出一个反例. 相似文献