Random Minimum Length Spanning Trees in Regular Graphs

r -regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that . Received: Februray 9, 1998     

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).     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

一些图的生成树数

图 G 的生成树是它的连通子图(子树).本文精确地计算出了一些图的生成树的数目, 例如双心轮图、双柄扇图等等.     

Chordal 2‐Connected Graphs and Spanning Trees

We present a transformation on a chordal 2‐connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with , the threshold graph having n vertices and m edges that consists of an ‐clique and vertices of degree 2 is the only graph with the fewest spanning trees among all 2‐connected chordal graphs on n vertices and m edges.     

路或圈的笛卡尔乘积图的支撑树数

设G是路或圈的笛卡尔乘积图，t(G)表示G的支撑树数.该文借助于第二类Chebyshev多项式给出t(G)的公式，并考虑了t(G)的线性递归关系及渐近性态.     

Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs

For any graph G, let be the number of spanning trees of G, be the line graph of G, and for any nonnegative integer r, be the graph obtained from G by replacing each edge e by a path of length connecting the two ends of e. In this article, we obtain an expression for in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if G is of order and size in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on for such a graph G.     

几乎无爪图的叶子数较少的生成树

A spanning tree with no more than 3 leaves is called a spanning 3-ended tree.In this paper, we prove that if G is a k-connected(k ≥ 2) almost claw-free graph of order n and σ_(k+3)(G) ≥ n + k + 2, then G contains a spanning 3-ended tree, where σk(G) =min{∑_(v∈S)deg(v) : S is an independent set of G with |S| = k}.     

Multi-Faithful Spanning Trees of Infinite Graphs

For an end and a tree T of a graph G we denote respectively by m() and m _T () the maximum numbers of pairwise disjoint rays of G and T belonging to , and we define tm() := min{m _T(): T is a spanning tree of G}. In this paper we give partial answers — affirmative and negative ones — to the general problem of determining if, for a function f mapping every end of G to a cardinal f() such that tm() f() m(), there exists a spanning tree T of G such that m _T () = f() for every end of G.     

On the Minimum Number of Spanning Trees in k‐Edge‐Connected Graphs

We show that a k‐edge‐connected graph on n vertices has at least spanning trees. This bound is tight if k is even and the extremal graph is the n‐cycle with edge multiplicities . For k odd, however, there is a lower bound , where . Specifically, and . Not surprisingly, c₃ is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show that . However, we have no examples of 5‐edge‐connected graphs with fewer spanning trees than the n‐cycle with all edge multiplicities (except one) equal to 3, which is almost 6‐regular. We have no examples of 5‐regular 5‐edge‐connected graphs with fewer than spanning trees, which is more than the corresponding number for 6‐regular 6‐edge‐connected graphs. The analogous surprising phenomenon occurs for each higher odd edge connectivity and regularity.     

图的生成树, 基本圈与Betti亏数

G为图且T是G的一棵生成树. 记号ξ(G, T)表示G＼E(T)中边数为奇数的连通分支个数. 文献［2］称ξ(G)=min[DD(X]T[DD)]ξ(G, T)为图G的Betti亏数, 这里min取遍G的所有生成树T. 由文献［2］知, 确定一个图G的最大亏格主要确定这个图的Betii亏数ξ(G).该文研究与Betti亏数有关的图的特征结构, 得到了关于图的最大亏格的若干结果.     

Aztec Diamonds, Checkerboard Graphs, and Spanning Trees

This note derives the characteristic polynomial of a graph that represents nonjump moves in a generalized game of checkers. The number of spanning trees is also determined.     

图的连通因子

连通因子问题与Hamilton问题和信息网络有着密切的联系．1993年，首先由M.Kano就该问题在[6]中提出了许多问题和猜想，接下来他又在[16]中提出了一些猜想，本文就连通因子问题在过去十年的主要进展进行了回顾并提出了若干可进一步研究的问题和猜想．     

On Unavoidability of Trees with k Leaves

Graphs and Combinatorics - ?A digraph is said to be n-unavoidable if every tournament of order n contains it as a subgraph. Let f(n) be the smallest integer such that every oriented tree of...     

A Note on Cycle Lengths in Graphs

 We prove that for every c>0 there exists a constant K = K(c) such that every graph G with n vertices and minimum degree at least c n contains a cycle of length t for every even t in the interval [4,e c(G) − K] and every odd t in the interval [K,o c(G) − K], where e c(G) and o c(G) denote the length of the longest even cycle in G and the longest odd cycle in G respectively. We also give a rough estimate of the magnitude of K. Received: July 5, 2000 Final version received: April 17, 2002 2000 Mathematics Subject Classification. 05C38     

Pathwidth of Planar and Line Graphs

 We prove that for every 2-connected planar graph the pathwidth of its geometric dual is less than the pathwidth of its line graph. This implies that pathwidth(H)≤ pathwidth(H ^*)+1 for every planar triangulation H and leads us to a conjecture that pathwidth(G)≤pathwidth(G ^*)+1 for every 2-connected graph G. Received: May 8, 2001 Final version received: March 26, 2002 RID="*" ID="*" I acknowledge support by EC contract IST-1999-14186, Project ALCOM-FT (Algorithms and Complexity - Future Technologies) and support by the RFBR grant N01-01-00235. Acknowledgments. I am grateful to Petr Golovach, Roland Opfer and anonymous referee for their useful comments and suggestions.     

Connected [a,b]-factors in Graphs

In this paper, we prove the following result: Let G be a connected graph of order n, and minimum degree . Let a and b two integers such that 2a <= b. Suppose and . Then G has a connected [a,b]-factor. Received February 10, 1998/Revised July 31, 2000     

Graphs of Non-Crossing Perfect Matchings

 Let P _n be a set of n=2m points that are the vertices of a convex polygon, and let ℳ _m be the graph having as vertices all the perfect matchings in the point set P _n whose edges are straight line segments and do not cross, and edges joining two perfect matchings M ₁ and M ₂ if M ₂=M ₁−(a,b)−(c,d)+(a,d)+(b,c) for some points a,b,c,d of P _n . We prove the following results about ℳ _m : its diameter is m−1; it is bipartite for every m; the connectivity is equal to m−1; it has no Hamilton path for m odd, m>3; and finally it has a Hamilton cycle for every m even, m≥4. Received: October 10, 2000 Final version received: January 17, 2002 RID="*" ID="*" Partially supported by Proyecto DGES-MEC-PB98-0933 Acknowledgments. We are grateful to the referees for comments that helped to improve the presentation of the paper.     

生成树与图的结构

在网络研究中,人们需要将图分解为指定的结构,来研究网络的普适性、鲁棒又脆弱性,探索网络进化、动力学复杂性、节点多样性、时空演化复杂性等.生成树与图的结构得到研究,海林图,唯一圈图,具有特殊完美匹配树等图的结构得到刻画.