完全二分图的升分解

Ａｌａｖｉ等人定义了一种关于图的新分解，即“升分解”并且猜想，任何有正条边的简单图可升分解。Ｈｕｎｇ－ＬｉｎＦｕ曾证明恰有（ｎ＋１／２）条边的完全二分图可升分解。本文得到了一个中的结论，证明了具有任何条边的完全二分图都可升分解。     

关于图升分解为独立边集问题

Ａｌａｖｉ［１］给出了图的升分解概念，并猜想每一图都可升分解．本文证明了边数为（?）的图Ｇ当边色数Ｘ＇（Ｇ）≤（ｎ＋２）／２时可升分解为{G_i}, 1≤i≤n, G_i≈iK₂．     

关于图的升分解的Alavi猜想

Y.Alavi等人在1987年定义了图的一种新分解,即“升分解”(ascebding subgraph decomposition),并提出猜想:设自然数n≥2,G是由k个分离的星S_1,S_2,…,S_k构成的图,S_i含有a_i条边,n≤a_i≤2n-2,,则G可升分解为星的并。本文证明了当n=2k+i(i=0,1,2)时猜想成立。     

图Kn-H -4的升分解

Alavi等人给出了图的升分解的概念并猜测任何一个有正数条边的图都可以升分解.Faudree等1987年证明了当完全图Kn的子图H至多有n-l条边时,Kn-H可以升分解.马克杰等1997年证明了当H至多含有n条边时,Kn-H可以升分解.作者1999年证明了当H的边数小于时,Kn-H可以升分解.本文将证明当H的边数小于 -4时Kn-H有升分解.     

关于图的一种新分解

Alavi等人在[1]中定义了图的一种新分解,即升分解,并提出猜想:     

关于二部图Km1m2-Hm2的升分解

在文献[2]中作者定义了图的一种新分解-升分解(Ascending subgraph Decomposition简记为ASD)，并提出了一个猜想：任意有正数条边的图都可以升分解．本文主要证明了二部图Km1m2-Hm2(m1≥m2)可以升分解，其中Hm2是至多含m2条边的Km1m2的子图．     

关于图的一种新分解

一、概念和记号 最近,Yousef Alavi等人在文献[*]中给出了图的升分解概念:已知图G,存在自然数n,G的边数q满足( )≤q≤( )。如果G能分解为子图G_1,G_2,…,G_n的并,使得G_i与G_(i+1)的一个真子图同构(1≤i≤n=1),G_i不含孤立点,则称这个分解为图G的一个升分解。     

图K_nH_((5n/2)-4)的升分解

Ａｌａｖｉ等人给出了图的升分解的概念并猜测任何一个有正数条边的图都可以升分解．Ｆａｕｄｒｅｅ等１９８７年证明了当完全图Ｋｎ的子图Ｈ至多有ｎ—１条边时，Ｋｎ－Ｈ可以升分解．马克杰等１９９７年证明了当Ｈ至多含有ｎ条边时，Ｋｎ－Ｈ可以升分解．作者１９９９年证明了当Ｈ的边数小于３ｎ／２时，Ｋｎ－Ｈ可以升分解．本文将证明当Ｈ的边数小于（５ｎ／２）－４时Ｋｎ－Ｈ有升分解．     

关于Kn—H2n＋1的升分解

［１］中猜想：任意有正数条边的图都可以升分解．本文证明了Ｋｎ－Ｈ２ｎ＋１可以升分解,其中Ｈ２ｎ＋１表示至多有ｎ个顶点和２ｎ＋１条边的图,ｎ≥７．     

关于图Kn-H2n+i(i=1,2)的升分解

Yousef.Alavi等人在文献[1]中定义了一种新分解(Ascending Subgraph Decomposition),即"升分解",并且猜想:任意有正整数条边的图都可以升分解.本文证明了下面两个结论:1. Kn-H2n+1可以升分解,其中H2n+1为含有2n+1条边的Kn的子图;2. Kn-H2n+2可以升分解,其中H2n+2为含有2n+2条边的Kn的子图.     

On the Ascending Subgraph Decomposition Problem

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｐａｐｅｒ［１］,Ａｌａｖｉａｎｄｏｔｈｅｒｓｄｅｆｉｎｅｄｔｈｅｃｏｎｃｅｐｔｏｆａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ：Ｄｅｆｉｎｉｔｉｏｎ　ＬｅｔＧｂｅａｇｒａｐｈｏｆｐｏｓｉｔｉｖｅｓｉｚｅｑ,ａｎｄｌｅｔｎｂｅｔｈａｔｐｏｓｉｔｉｖｅｉｎｔｅｇｅｒｆｏｒｗｈｉｃｈｎ＋１２ｑ＜ｎ＋２２．ＴｈｅｎＧｉｓｓａｉｄｔｏｈａｖｅａｎａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＡＳＤ）ｉｆＧｃａｎｂｅｄｅｃｏｍｐｏｓｅｄ…     

关于图Kn-H2n+i(i=1,2)的升分解

Ｙｏｕｓｅｆ．Ａｌａｖｉ等人在文献［１］中定义了一种新分解（Ａｓｃｅｎｄｉｎｇ Ｓｕｂｇｒａｐｈ Ｄｅｃｏｍｐｏｓｉ－ ｔｉｏｎ），即“升分解”，并且猜想：任意有正整数条边的图都可以升分解．本文证明了下面两个结 论： １．Ｋ_n-H_2n+1可以升分解，其中Ｈ_2n+1为含有２ｎ＋１条边的Ｋ_n的子图； ２．Ｋ_n-H_2n+2可以升分解，其中Ｈ_2n+2为含有２ｎ＋     

k-Factors and Spanning Subgraph in Graphs

In this paper, we discussed k-factors and spanning subgraph, and propose a conjecture which will lead to a series of important conclusion.     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

Induced Decompositions of Graphs

We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.     

最大2-正则诱导子图的长度

设G是2-连通图，c(G)是图G的最长诱导圈的长度，c′(G)是图G的最长诱导2-正则子图的长度。本文我们用图的特征值给出了c(G)和c′(G)的几个上界。     

几族3-优图

一个图 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-优图 .