Thông tin chung

Văn phòng Khoa trân trọng thông báo tới các Thầy/Cô và các Anh/Chị thông tin về buổi Seminar Khoa học: – Chủ đề: Graceful Labeling Problems in Graphs – Properties and Algorithms – Người trình bày: GS Jay Bagga (Professor of Computer Science at Ball State University in Muncie, Indiana, USA) – Thời gian: 2h chiều 8/12, Thứ 5 – Địa điểm: P. 212, E3. Trân trọng kính mời các Thầy/Cô và các Anh/Chị quan tâm tới dự. Nội dung: A special type of graph labeling called graceful labeling has been extensively studied. Let G be a graph with n vertices and m edges. A labeling of the vertices with labels from the set {0, 1, 2, m} induces an edge labeling where the label of the edge joining two vertices with labels i and j is |i – j|. Such a labeling is called graceful if the edges are labeled 1, 2, 3,…, m in some order. A long standing open problem states that every tree has a graceful labeling. By exhaustive verification with computer algorithms, it has been shown that all trees of order up to 35 are graceful. Since the number of trees grows exponentially, such exhaustive methods are unlikely to solve this problem. Much of the research in graceful labelings has been focused on finding new families of graceful graphs. We embarked on a research program to enumerate graceful labelings of graphs which are known to be graceful. We have implemented algorithms that enumerate graceful labelings of cycles, and certain subclasses of trees. This has led to the discovery of new properties of such labelings.