87319日（星期四）

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 茶會

87320日（星期五）

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 茶會

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.

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.

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.

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.