Properties Of Multimedian Graph

A connected graph is called a multimedian graph,if for any three vertices,,wvu of its vertex set,there are at least one vertex immediately lies on a shortest u,w-path,a shortest u,v-path and a shortest v,w-path.The median graph is an important structural feature of the graph,and the tree and hypercube graphs are common median graphs.As a natural generalization of the median graph,the multimedian graph is of great significance to the study of the structure and properties of graphs.This paper mainly studies the properties of multimedian graphs,focuses on the following aspects: the relation between multimedian graph and partial cube;every interval of a multimedian graph induces a multimedian graph;the multimedian graph under vertex-gluing and edge-gluing operation;using the forbidden subgraph of multimedian graph to study its property after deleting one edge.This thesis consists of five chapters.In the first chapter,we introduce the development history of graph theory and research status of median graph and multimedian graph.In the second chapter,we mainly study the relation between multimedian graph and partial cube.Firstly,we prove that median graph is partial cube.Next,we prove that the multimedian graph except median graph(strict multimedian graph)contains a2,3K as its subgraph.Finally,we prove that a strict multimedian graph is not a partial cube by using the fact that2,3K is not partial cube.In the third chapter,we give the proof that every interval of a multimedian graph induces a multimedian graph.In the fourth chapter,it is proved that a multimedian graph obtained from two mutimedian graphs by gluing a vertex or gluing an edge is still a multimedian graph.Thus,we provide a method for constructing multimedian graphs,and then we give and use the forbidden subgraphs of the multimedian graph to prove that a planar multimedian graph is not a multimedian graph after deleting a particular edge,and propose some problems and conjectures.The last chapter makes a brief summary and prospect of the research in this paper.We hope that it will play a role in the following research.