tailieunhanh - Báo cáo toán học: "Two Characterizations of Hypercubes"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Two Characterizations of Hypercubes. | Two Characterizations of Hypercubes Juhani Nieminen Matti Peltola and Pasi Ruotsalainen Department of Mathematics University of Oulu University of Oulu Faculty of Technology Mathematics Division . Box 4500 90014 Oulun yliopisto Finland Submitted Jun 11 2008 Accepted Apr 20 2011 Published Apr 29 2011 Mathematics Subject Classification 05C75 Abstract Two characterizations of hypercubes are given 1 A graph is a hypercube if and only if it is antipodal and bipartite 0 2 -graph. 2 A graph is an n-hypercube if and only if there are n pairs of prime convexes the graph is a prime convex intersection graph and each intersection of n prime convexes no one of which is from the same pair is a vertex. 1 Introduction Hypercubes constitute a very remarkable class of graphs especially for transmitting communication and therefore each characterization of hypercubes offers a new point of view to use and construct hypercubes. The class of 0 2 -graphs is a subclass of strongly regular graphs studied in the theory of combinatorial design. It was introduced in 6 and intensively studied in 3 and in 4 . We begin with some basic properties of antipodal graphs see also 7 . Then we prove that a graph is a hypercube if and only if it is an antipodal bipartite 0 2 -graph. This characterization gives another characterization of hypercubes by using prime convex intersection graphs. The graphs G V E considered here are finite connected and undirected without loops and multiple edges. The set V is the set of vertices and E the set THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P97 1 of edges in G. A shortest u v path is called a u v geodesic and d u v is its length. The interval u v is the set of all vertices locating on any u v geodesic. By N u we denote the set of neighbours of u N u v d u v 1 and by deg u the cardinality of N u . The diameter of a graph G is denoted by diam G max d u v u v G V . A graph G