关于超欧拉图的一个注记

设G是无向无环的有限图 ,若G有一个生成子图是欧拉图 (Euler) ,则称G是超欧拉图 (Supereulerian) .本文不利用收缩方法 ,直接证明了 :当图G至多差一边有两棵边不相交的生成树时 ,G是超欧拉图或者G有割边 .     

Degree sums and spanning brooms of a graph

A broom is a tree obtained by identifying an endpoint of a path with the center of a star. Let G be a connected graph of order $n\ge 3$. Chen et al. [2] conjectured that if the degree sum is at least $n?2$ for any three pairwise nonadjacent vertices, then G contains a spanning broom. In this paper, we confirm the conjecture for $n>50$.     

Spanning trees and spanning closed walks with small degrees

Let G be a graph and let f be a positive integer-valued function on $V(G)$. In this paper, we show that if for all $S?V(G)$, $\omega (G?S)<{\sum }_{v\in S}(f(v)?2)+2+\omega (G[S])$, then G has a spanning tree T containing an arbitrary given matching such that for each vertex v, $d_T(v)\le f(v)$, where $\omega (G?S)$ denotes the number of components of $G?S$ and $\omega (G[S])$ denotes the number of components of the induced subgraph $G[S]$ with the vertex set S. This is an improvement of several results. Next, we prove that if for all $S?V(G)$, $\omega (G?S)\le {\sum }_{v\in S}(f(v)?1)+1$, then G admits a spanning closed walk passing through the edges of an arbitrary given matching meeting each vertex v at most $f(v)$ times. This result solves a long-standing conjecture due to Jackson and Wormald (1990).     

The connectivity of a graph and its complement

Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let be the complement of G.In this article we prove that either λ(G)=δ(G) or . In addition, we present the Nordhaus-Gaddum type result . A family of examples will show that this inequality is best possible.     

Subgraph induced by the set of degree 5 vertices in a contraction critically 5-connected graph

An edge of a 5-connected graph is said to be contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no contractible edge is said to be contraction critically 5-connected. Let G be a contraction critically 5-connected graph and let H be a component of the subgraph induced by the set of degree 5 vertices of G. Then it is known that |V(H)|≥4. We prove that if |V(H)|=4, then , where stands for the graph obtained from K₄ by deleting one edge. Moreover, we show that either |N_G(V(H))|=5 or |N_G(V(H))|=6 and around H there is one of two specified structures called a -configuration and a split -configuration.     

The isomorphism problem for classes of graphs closed under contraction

We consider the isomorphism problem for graphs in classes which, together with any graph, contain its connected induced subgraphs and graphs obtained by successive identifications of endpoints of edges. The main result is to establish sufficient conditions for the existence of a polynomial time algorithm testing graphs of such classes for isomorphism. It is shown that classes failing to satisfy these conditions are isomorphism-complete.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 147–177, 1988.     

The Banach algebra generated by a contraction

Let be a contraction on a Banach space and the Banach algebra generated by . Let be the unitary spectrum (i.e., the intersection of with the unit circle) of . We prove the following theorem of Katznelson-Tzafriri type: If is at most countable, then the Gelfand transform of vanishes on if and only if

     

The independence number condition for the existence of a spanning f‐tree

Let G be a graph and f be a mapping from V(G) to the positive integers. A subgraph T of G is called an f‐tree if T forms a tree and d_T(x)≤f(x) for any x∈V(T). We propose a conjecture on the existence of a spanning f‐tree, and give a partial solution to it. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 173–184, 2010     

Chromatic numbers of quadrangulations on closed surfaces

It has been shown that every quadrangulation on any nonspherical orientable closed surface with a sufficiently large representativity has chromatic number at most 3. In this paper, we show that a quadrangulation G on a nonorientable closed surface N_k has chromatic number at least 4 if G has a cycle of odd length which cuts open N_k into an orientable surface. Moreover, we characterize the quadrangulations on the torus and the Klein bottle with chromatic number exactly 3. By our characterization, we prove that every quadrangulation on the torus with representativity at least 9 has chromatic number at most 3, and that a quadrangulation on the Klein bottle with representativity at least 7 has chromatic number at most 3 if a cycle cutting open the Klein bottle into an annulus has even length. As an application of our theory, we prove that every nonorientable closed surface N_k admits an eulerian triangulation with chromatic number at least 5 which has arbitrarily large representativity. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 100–114, 2001     

Maltsev families of varieties closed under join or Maltsev product

Maltsev families of varieties which are closed under join or Maltsev product are investigated. New Maltsev conditions for congruence semi-distributivity are given.     

关于图的若干介值问题

对连通图G,以C_i(G),■(G)分别表G的有i条边的连通支撑子图之集与连通子图之集,以C~i(G),(?)(G)分别表G的顶点数为i的子树集与连通子图之集.本文讨论了这四类子图簇对若干基本参数及端点数的介值性,从而对已有的一些结果作了若干有意义的拓广.     

The energy and spanning trees of the Aztec diamonds

The Aztec diamond was extensively studied in both graph theory and statistical physics. Knuth obtained a formula of the number of spanning trees of the Aztec diamond with the constrained boundary condition, which solved a conjecture posed by Stanley in 1994. In this paper, We give the formulae of the energy and the number of spanning trees of the Aztec diamond with the toroidal boundary condition.