Triangle-free graphs with no six-vertex induced path

The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication).     

A Hopf algebra for counting cycles

Cycles, also known as self-avoiding polygons, elementary circuits or simple cycles, are closed walks which are not allowed to visit any vertex more than once. We present an exact formula for enumerating such cycles of any length on any directed graph involving a sum over its induced subgraphs. This result stems from a Hopf algebra, which we construct explicitly, and which provides further means of counting cycles. Finally, we obtain a more general theorem asserting that any Lie idempotent can be used to enumerate cycles.     

Brambles and independent packings in chordal graphs

An independent packing of triangles is a set of pairwise disjoint triangles, no two of which are joined by an edge. A triangle bramble is a set of triangles, every pair of which intersect or are joined by an edge. More generally, I consider independent packings and brambles of any specified connected graphs, not just triangles. I give a min-max theorem for the maximum number of graphs in an independent packing of any family of connected graphs in a chordal graph, and a dual min-max theorem for the maximum number of graphs in a bramble in a chordal graph.     

Induced nilpotent orbits and birational geometry

In general, a nilpotent orbit closure in a complex simple Lie algebra g, does not have a crepant resolution. But, it always has a Q-factorial terminalization by the minimal model program. According to B. Fu, a nilpotent orbit closure has a crepant resolution only when it is a Richardson orbit, and the resolution is obtained as a Springer map for it. In this paper, we shall generalize this result to Q-factorial terminalizations when g is classical. Here, the induced orbits play an important role instead of Richardson orbits.     

The parameterized complexity of the induced matching problem

Given a graph G and an integer k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.     

Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs

Let G = (V, E) be a connected graph. For a vertex subset , G[S] is the subgraph of G induced by S. A cycle C (a path, respectively) is said to be an induced cycle (path, respectively) if G[V(C)] = C (G[V(P)] = P, respectively). The distance between a vertex x and a subgraph H of G is denoted by , where d(x, y) is the distance between x and y. A subgraph H of G is called 2-dominating if d(x, H) ≤ 2 for all . An induced path P of G is said to be maximal if there is no induced path P′ satisfying and . In this paper, we assume that G is a connected claw-free graph satisfying the following condition: for every maximal induced path P of length p ≥ 2 with end vertices u, v it holds:

Some relationships between induced mappings

We prove some relationships between f, Cn(f), HSn(f) and f², when f, Cn(f), HSn(f) or f² belong to the following mapping classes: monotone, OM, confluent, semi-confluent, weakly confluent, pseudo-confluent, quasi-monotone, weakly monotone or joining.     

Dirichlet空间中的正交函数

主要考虑了Dirichlet空间中的正交函数.主要结论表明单位圆盘中的一个解析自映射是Dirichlet空间中的正交函数,当且仅当其所对应的计数函数是本质径向的;当且仅当其所对应的诱导测度是径向的.作为主要结论的一个应用,给出了单位圆盘上的单叶解析函数和闭单位圆盘上的解析函数是Dirichlet空间中正交函数的完全刻画.     

On the upper semicontinuity of Choquet capacities

The Choquet capacity T of a random closed set X on a metric space E is regarded as or related to a non-additive measure, an upper probability, a belief function, and in particular a counterpart of the distribution functions of ordinary random vectors. While the upper semicontinuity of T on the space of all closed subsets of E (hit-or-miss topology) is highly desired, T is not necessarily u.s.c. if E is not compact, e.g. E=Rⁿ. For any locally compact separable metric space E, this controversial situation can be resolved in the probabilistic context by stereographically projecting X into the Alexandroff compactification E_∞ of E with the “north pole” added to the projection. This leads to a random compact set that is defined on the same probability space, takes values in a space homeomorphic to the space of X, and possesses an equivalent probability law. Particularly, the Choquet capacity of is u.s.c. on the space of all closed subsets of E_∞. Further, consequences of the upper semicontinuity of are explored, and a proof of the equivalence between the upper semicontinuity of T and continuity from above on F(E) is provided.