系列平行图的围长和圆可选性

本文讨论了系列平行图的圆可选性．令x_(c,l)表示圆可选性(或圆列表着色数)．本文证明了围长至少是4n 1的系列平行图的圆可选性至多为2 1/n．     

Factors and vertex-deleted subgraphs

A relationship is considered between an f-factor of a graph and that of its vertex-deleted subgraphs. Katerinis [Some results on the existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16 (1983) 271-277] proved that for even integer k, if G-x has a k-factor for each x∈V(G), then G has a k-factor. Enomoto and Tokuda [Complete-factors and f-factors, Discrete Math. 220 (2000) 239-242] generalized Katerinis’ result to f-factors, and proved that if G-x has an f-factor for each x∈V(G), then G has an f-factor for an integer-valued function f defined on V(G) with even. In this paper, we consider a similar problem to that of Enomoto and Tokuda, where for several vertices x we do not have to know whether G-x has an f-factor. Let G be a graph, X be a set of vertices, and let f be an integer-valued function defined on V(G) with even, |V(G)-X|?2. We prove that if and if G-x has an f-factor for each x∈V(G)-X, then G has an f-factor. Moreover, if G excludes an isolated vertex, then we can replace the condition with . Furthermore the condition will be when |X|=1.     

Bodies with similar projections

Aleksandrov's projection theorem characterizes centrally symmetric convex bodies by the measures of their orthogonal projections on lower dimensional subspaces. A general result proved here concerning the mixed volumes of projections of a collection of convex bodies has the following corollary. If is a convex body in whose projections on -dimensional subspaces have the same -dimensional volume as the projections of a centrally symmetric convex body , then the Quermassintegrals satisfy , for , with equality, for any , if and only if is a translate of . The case where is centrally symmetric gives Aleksandrov's projection theorem.

     

Note on a min‐max conjecture of Woodall

In 1978 Woodall [ 6 ] conjectured the following: in a planar digraph the size of a shortest cycle is equal to the maximum cardinality of a collection of disjoint tranversals of cycles. We prove that this conjecture is true when the digraph is series‐parallel. In fact, we prove a stronger weighted version that gives the latter result as a corollary. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 36–41, 2001     

The equivariant family index theorem in odd dimensions

In this paper, we prove a local odd dimensional equivariant family index theorem which generalizes Freed's odd dimensional index formula. Then we extend this theorem to the noncommutative geometry framework. As a corollary, we get the odd family Lichnerowicz vanishing theorem and the odd family Atiyah-Hirzebruch vanishing theorem.     

Star coloring planar graphs from small lists

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010     

围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径

图的谱半径和Laplacian谱半径分别是图的邻接矩阵和Laplacian矩阵的最大特征值.本文中,我们分别刻画了围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径达到最大时的极图.     

Biregular Cages of Odd Girth

Biregular ‐cages are graphs of girth g that contain vertices of degrees r and m and are of the smallest order among all such graphs. We show that for every and every odd , there exists an integer m₀ such that for every even , the biregular ‐cage is of order equal to a natural lower bound analogous to the well‐known Moore bound. In addition, when r is odd, the restriction on the parity of m can be removed, and there exists an integer m₀ such that a biregular ‐cage of order equal to this lower bound exists for all . This is in stark contrast to the result classifying all cages of degree k and girth g whose order is equal to the Moore bound.