主講人：蔡雷震　教授（香港中文大學資訊工程系）

地　點：國立中山大學理學院理4009-1室

議　程：

　　　87年3月19日（星期四）

　　　　　13:00-13:10 報到

　　　　　13:10-14:00 講題－On (X, 2X)-type generators for line graphs

　　　　　14:00-14:10 休息

　　　　　14:10-15:00 講題－How to compute the intersection of odd cycles quickly

　　　　　15:00-15:30 茶會

　　　87年3月20日（星期五）

　　　　　13:00-13:10 報到

　　　　　13:10-14:00 講題－Path decomposition of multigraphs

　　　　　14:00-14:10 休息

　　　　　14:10-15:00 講題－Spanning 2-trees

　　　　　15:00-15:30 茶會

報名方式：現場報名

連 絡 人：官大智　教授 (07)525-2000轉3812 guan@math.nsysu.edu.tw

主辦單位：國立中山大學應用數學系

協辦單位：國科會數學研究推動中心

時間：87年3月19日(星期四) 13:10-14:00

講題：On (X,2X)-type generators for line graphs

摘要：

For two fixed graphs X and Y, the (X,Y)-intersection graph of a graph G is a graph whose vertices are induced subgraphs of G isomorphic to Y and two of them are adjacent if their intersection in G contains an induced subgraph isomorphic to X.This generalizes the concept of line graphs since the line graph of G is precisely the (K1,K2)-intersection graph of G.Let 2X denote the disjoint union of two copies of X. In this talk,I will show that the family of all (X,2X)-intersection graphs equals the family of line graphs whenever X is a connected graph with no bipartite blocks. Furthermore, based on a property of vertex splitting of graphs, a necessary condition is obtained for (X,2X) to satisfy the equality between the above two families of graphs. Using a theorem from Ramsey theory, we can deduce that no X in such (X,2X) can be a nontrivial bipartite graph.

時間：87年3月19日(星期四) 14:10-15:00

講題：How to compute the intersection of odd cycles quickly

摘要：

Computing the intersection of odd cycles is easy; however, it is quite intriguing whether we can compute the intersection in linear time. In this talk, I will present a linear-time algorithm that finds all edges and vertices in the intersection of all odd cycles in a given graph. I will also show an application of the algorithm to a variant of the satisfiability problem of Boolean formulas.

時間：87年3月20日(星期五) 13:10-14:00

講題：Path Decomposition of Multigraphs

摘要：

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and u(x) respectively. Define f(x) to be the smallest even integer greater than or equal to u(x) if d(x) is even and the smallest odd integer greater than or equal to u(x) if d(x) is odd.

In this talk, I will show that every multigraph G admits a faithful path decomposition -- a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly f(x) paths in P. This result generalizes Lovasz's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture.

時間：87年3月20日(星期五) 14:10-15:00

講題：Spanning 2-Trees

摘要：

A k-tree is either a complete graph on k vertices or a graph T that contains a vertex v whose neighbourhood in T induces a complete graph on k vertices and whose removal results in a k-tree. Note that a 1-tree is exactly the same as a tree.

In this talk, I will discuss spanning 2-trees in a graph. It will be shown that spanning 2-trees have close connections with two special types of spanning trees: locally-connected spanning trees and tree 2-spanners. I will also give an approximation algorithm for finding a minimum-weight spanning 2-tree in a weighted complete graph, whose asymptotic performance ratio is at most 2 when edge weights satisfy the triangle inequality, and at most 1.655 when the graph is a complete Euclidean graph on a set of points in the plane.