論文

A complete undirected graph of order n has (n-1)!/2 Hamilton cycles. We consider the diameter of a transition graph whose vertices correspond to those Hamilton cycles and any of two vertices are adjacent if and only if the corresponding Hamilton cycles can be transformed each other by exchanging two edges. Moreover, we consider several transition graphs related to it.

In this article, we study the existence of a 2-factor in a K 1, n-free graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K1, n-free graph of even order has a 1-factor. On the other hand, for every pair of integers m and n with m ≥ n ≥ 4, there exist infinitely many (n-2)-connected K1, n-free graphs of even order and minimum degree at least m which have no 1-factor. This implies that the connectivity condition of Sumner's result is sharp, and we cannot guarantee the existence of a 1-factor by imposing a large minimum degree. On the other hand, Ota and Tokuda [J Graph Theory 22 (1996), 59-64] proved that for n ≥ 3, every K1, n-free graph of minimum degree at least 2n-2 has a 2-factor, regardless of its connectivity. They also gave examples showing that their minimum degree condition is sharp. But all of them have bridges. These suggest that the effects of connectivity, edge-connectivity and minimum degree to the existence of a 2-factor in a K1, n-free graph are more complicated than those to the existence of a 1-factor. In this article, we clarify these effects by giving sharp minimum degree conditions for a K 1, n-free graph with a given connectivity or edge-connectivity to have a 2-factor. © 2010 Wiley Periodicals, Inc.

The toughness of a non-complete graph G is the minimum value of among all separating vertex sets S ⊂ V(G), where ω(G - S) ≥ 2 is the number of components of G - S. It is well-known that every 3-connected planar graph has toughness greater than 1/2. Related to this property, every 3-connected planar graph has many good substructures, such as a spanning tree with maximum degree three, a 2-walk, etc. Realizing that 3-connected planar graphs are essentially the same as 3-connected K3,3-minor-free graphs, we consider a generalization to a-connected Ka,t-minor-free graphs, where 3 ≤ a ≤t. We prove that there exists a positive constant h(a, t) such that every a-connected Ka,t-minor-free graph G has toughness at least h(a,t). For the case where a = 3 and t is odd, we obtain the best possible value for h(3, t). As a corollary it is proved that every such graph of order n contains a cycle of length Ω(logh(a,t) n).

Let δ(G) denote the minimum degree of a graph G. We prove that a graph G of order at least 4k + 6 with δ(G) ≥ k + 2 contains k pairwise vertex-disjoint K1,3's. The conditions on the minimum degree and on the order of the graph are best possible in a sense. © 1999 Elsevier Science B.V. All rights reserved.

Let n1, n2, . . ., nk be integers of at least two. Johansson gave a minimum degree condition for a graph of order exactly n1 + n2 + ⋯ + nk to contain k vertex-disjoint paths of order n1, n2, . . ., nk, respectively. In this paper, we extend Johansson's result to a corresponding packing problem as follows. Let G be a connected graph of order at least n1 + n2 + ⋯ + nk. Under this notation, we show that if the minimum degree sum of three independent vertices in G is at least (formula presented) then G contains k vertex-disjoint paths of order n1, n2, . . ., nk, respectively, or else n1 = n2 = ⋯ = nk = 3, or k = 2 and n1 = n2 = odd. The graphs in the exceptional cases are completely characterized. In particular, these graphs have more than n1 + n2 + ⋯ + nk vertices.

A circuit graph(G, C) is a 2-connected plane graph G with an outer cycle C such that from each inner vertex v, there are three disjoint paths to C. In this paper, we shall show that a circuit graph with n vertices has a 3-tree (i.e., a spanning tree with maximum degree at most 3) with at most frac(n - 7, 3) vertices of degree 3. Our estimation for the number of vertices of degree 3 is sharp. Using this result, we prove that a 3-connected graph with n vertices on a surface Fχ with Euler characteristic χ ≥ 0 has a 3-tree with at most frac(n, 3) + cχ vertices of degree 3, where cχ is a constant depending only on Fχ. © 2008 Elsevier B.V. All rights reserved.

A graph is called K1, n-free if it contains no K1, n as an induced subgraph. Let n(≥ 3), r be integers (if r is odd, r ≥ n - 1). We prove that every K1, n-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least (n + n-1/r) ⌈n/2(n - 1) r⌉ - n - 1/r (⌈n/2(n - 1) r⌉)2 + n - 3. This degree condition is sharp. © 1996 John Wiley & Sons, Inc.

A weighted graph is one in which every edge e is assigned a non-negative number, called the weight, of e. For a vertex v of a weighted graph, d w(v) is the sum of the weights of the edges incident with v. For a subgraph H of a weighted graph G, the weight of H is the sum of the weights of the edges belonging to H. In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. Let G be a k-connected weighted graph where 2 ≤ k. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/(k+1), if G satisfies the following conditions: (1) The weighted degree sum of any k independent vertices is at least m, (2) w(xz) = w(yz) for every vertex z ε N(x) ∩ N (y) with d(x,y) = 2, arid (4) In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight.

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t. every 3-connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that ∑x∈V(H) degG(x) ≤ 8t - 1. As a tool for proving this result, we consider decompositions of 3-connected planar graphs into connected subgraphs of order at least t and at most 2t - 1. © 1999 John Wiley & Sons, Inc.

We discuss the maximum size of uniform intersecting families with covering number at least τ. Among others, we construct a large k-uniform intersecting family with covering number k, which provides a counterexample to a conjecture of Lovász. The construction for odd k can be visualized on an annulus, while for even k on a Möbius band. © 1996 Academic Press, Inc.

We have determined all exponents of (n, k, L)-systems of k ≤ 12 except for essentially two cases, which are related to the Steiner systems S(11, 5, 4) and S(12, 6, 5). This requires several new constructions. Also some refinements of the previous methods are necessary to get suitable upper bounds. © 1996 Academic Press, Inc.

For a vertex v of an edge-colored graph, the color degree of v is the number of colors appeared in edges incident with v. An edge-colored graph is called properly colored if no two adjacent edges have the same color. In this paper, we prove that if the minimum color degree sum of two adjacent vertices of an edge-colored connected graph G is at least |G|, then G has a properly colored spanning tree. This is a generalization of the result proved by Cheng, Kano and Wang. We also show the sharpness of this lower bound of the color degree sum.