Study On Graph Labelings And Hypergraph Decomposition

This thesis makes a study and discussion on the graph Labeling and hypergraph Decomposition.The first chapter introduces the basic concepts of general graphs, traditional hypergraphs and information hypergraphs, as well as the research development of graph labeling, cycle decomposition of traditional hypergraphs and information hypergraph.In the second chapter, we study gracefulness of digraphs n ? C|-_m obtained from any n copies of the directed cycle C|-_m which have just one common vertex. In 1994, Zhiting Du et al. proposed a conjecture that n . C|- _2k+1 is graceful graph for any even n and integer k. This chapter proves that n ? C|-_m is graceful for any even n and m = 11,13,15,17.In the third chapter, we study gracefulness of digraphs n - C|-_m obtained from any n copies of the directed cycle C|-_m which have just one common edge. We prove that the digraph n - C|-_m is graceful if 4 ≤ m ≤ 13 and n is any even. Moreover, we present a conjecture and a problem on the gracefulness of the digraph n - C|-_m .In the fourth chapter, we discuss (a,d)-antimagic labeling of generalized petersen graph. In 2000, Miller and Baca conjecture that P(n, k) is (5n+5/2, 2)-antimagic for odd n and 2 ≤ k≤n/2 - 1. We show that the conjecture is true for k = 2 and n = 3 (mod 4), n ≥ 7.In the fifth chapter, we mainly study cycle structure of traditional hypergraphs. We first give a partition of edges of complete 3_uniform hypergraph, based on which we define edge sequence according to the edge adjacency requirement and research some properties of all the edge sequences. Then, we obtain an edge decomposition and cycle decomposition of complete 3-uniform hypergraph. Furthermore, we get the following:(1) Hamilton cycle decomposition of complete 3-uniform hypergraph for prime n.(2) Half Hamilton cycle decomposition, namely, cycle decomposition of length n/2 for prime n = 2q, (qis prime.(3) Hamilton cycle decomposition of complete bipartite 3-uniform hypergraph.In the sixth chapter, we mainly study cycle structure and cycle decomposition of information hypergraphs. According to two different edge adjacency requirement, we define the edge sequences and study some properties and cycle model of all edge sequences. Finally, we respectively get edge decomposition and cycle decomposition of complete 3-uniform information hypergraph K³.