| In 1987, the well-know mathematician Yousef Alavi and other famous mathematicians defined a new decomposition of graph-Ascending Subgraph Decomposition (ASD) which is on the condition of proper subgraph isomorphic, and in the same paper they proposed the following ASD conjecture (Alavi conjecture): every graph of positive size has an ASD. After the ASD conjecture is proposed, many mathematicians begin to consider it, but to this day only few graphs have been proved to have an ASD, and in order to verify this conjecture, a revised conjecture attracts more attention than the original one, all conclusions in this paper are concerned about the revised conjecture.In this paper, we mostly discuss several especial graphs, although this can not finally resolve the ASD conjecture, it can reduce many counterexamples that make the ASD conjecture incorrect. Furthermore we firstly introduce into matrix, and combining the matrix's character we discuss the operation of the graphs that have an ASD, that also affords a new way to ultimately prove the ASD conjecture.For bipartite graph, which can be look as a graph by deleting a subgraph H from the complete bipartite graph Kn1n2 , so here we prove when H satisfy some conditions, bipartitegraph Kn1n2 -H has an ASD; And we also prove when the vertex number of one vertex set of bipartite graph G = (V1,V2) satisfy some conditions, G has an ASD. Moreover, we prove that any circular graph has an ASD, and on the basis of this we prove that for regular graph, namely the graph which degree of every vertex is equal, the ASD conjecture is correct. Before this, Ma Kejie and other people proved that regular graph G has an ASD when theirdegree k <2/3(n + 1), where n is positive integer such that |E(G)| =(n+1 2) . Further, in thispaper, we discuss the operation for the graphs that have an ASD, and prove that the mixed product of circular graph has an ASD; Further more, in this paper we prove that the tensor product for two graphs which both have an ASD has an ASD.
|
PDF Full Text Request