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

地 點：國立中山大學理學院理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.