Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

The Max-Flow Min-Cut theorem for countable networks

We prove a strong version of the Max-Flow Min-Cut theorem for countable networks, namely that in every such network there exist a flow and a cut that are “orthogonal” to each other, in the sense that the flow saturates the cut and is zero on the reverse cut. If the network does not contain infinite trails then this flow can be chosen to be mundane, i.e. to be a sum of flows along finite paths. We show that in the presence of infinite trails there may be no orthogonal pair of a cut and a mundane flow. We finally show that for locally finite networks there is an orthogonal pair of a cut and a flow that satisfies Kirchhoff's first law also for ends.     

标准算子代数上完全保对合性的可加映射

刻画了无限维实或复Banach空间上的标准算子代数间完全保对合性的可加映射,证明了这样的映射是同构的常数倍或(复情形下)共轭同构的常数倍.     

The DFS-heuristic for orthogonal graph drawing

In this paper, we present a new heuristic for orthogonal graph drawings, which creates drawings by performing a depth-first search and placing the nodes in the order they are encountered. This DFS-heuristic works for graphs with arbitrarily high degrees, and particularly well for graphs with maximum degree 3. It yields drawings with at most one bend per edge, and a total number of m−n+1 bends for a graph with n nodes and m edges; this improves significantly on the best previous bound of m−2 bends.     

Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs

Robert E. Jamison characterized chordal graphs by the edge set of every k-cycle being the symmetric difference of k−2 triangles. Strongly chordal (and chordal bipartite) graphs can be similarly characterized in terms of the distribution of triangles (respectively, quadrilaterals). These results motivate a definition of ‘strongly chordal bipartite graphs’, forming a class intermediate between bipartite interval graphs and chordal bipartite graphs.     

On the Right-Definite and Left-Definite Spectral Theory of the Legendre Polynomials

In this paper, we further develop the left-definite and right-definite spectral theory associated with the self-adjoint differential operator A in L²(-1,1), generated from the classical second-order Legendre differential equation, having the sequence of Legendre polynomials as eigenfunctions. Specifically, we determine the first three left-definite spaces associated with the pair (L²(-1,1),A). As a consequence of these results, we determine the explicit domain of both the associated left-definite operator A₁, first observed by Everitt, and the self-adjoint operator A^1/2. In addition, we give a new characterization of the domain D(A) of A and, as a corollary, we present a new proof of the Everitt-Mari result which gives optimal global smoothness of functions in D(A).     

图的边覆盖染色中的分类问题(英文)

设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全 r分图的分类问题     

On isogeny graphs of supersingular elliptic curves over finite fields

We study the isogeny graphs of supersingular elliptic curves over finite fields, with an emphasis on the vertices corresponding to elliptic curves of j-invariant 0 and 1728.     

Optimal broadcast domination in polynomial time

Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power f(v)?0 to each vertex v of a given graph, such that every vertex of the graph is within distance f(v) from some vertex v having f(v)?1. The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in P, and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach.