Chinese Quarterly Journal of Mathematics ›› 1999, Vol. 14 ›› Issue (2): 52-58.

Previous Articles     Next Articles

On the Ascending Subgraph Decomposition Problem

  

  1. Department of Mathematics,Tangshan Teacherʾs College,Tangshan,063000
  • Received:1997-10-02 Online:1999-06-30 Published:2024-09-24

Abstract: Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that Kn-Rn-1 has a star ascending subgraph decomposition,here Kn is the complete graph with order n and Rn-1 is a subgraph of K n with size at most n-1. In paper [3],Ma Kejie and Chen Huaitang proved that Kn-Rn has an ascending subgraph decomposition when the size of R n is not greater than n. In this paper we will prove Kn-R has an ascending subgraph decomposition when the size of R is less than 3n/2. This paper will also give the concept of comet and prove that Kn-Rn-1 has a comet ascending subgraph decomposition.  

Key words:  , graph;comet;ascending subgraph decomposition;conjecture

CLC Number: