論文

P. Katerinis obtained a sufficient condition for the existence of a 2‐factor in a bipartite graph, in the spirit of Hall's theorem. We show a sufficient condition for the existence of a k‐factor in a bipartite graph, as a generalization of Katerinis's theorem and Hall's theorem. Copyright © 1988 Wiley Periodicals, Inc., A Wiley Company

We prove that every 3-connected graph G of order at least nine has two adjacent edges xy and yz such that the graph obtained from G by contracting x, y, and z into a single vertex is also 3-connected. © 1994 by Academic Press, Inc.

Let F be a family of connected graphs. A graph G is said to be F-free if G is H-free for every graph H in F. We study the problem of characterizing the families of graphs F such that every large enough connected F-free graph of even order has a perfect matching. This problems was previously studied in Plummer and Saito (J Graph Theory 50(1):1-12, 2005), Fujita et al. (J Combin Theory Ser B 96(3):315-324, 2006) and Ota et al. (J Graph Theory, 67(3):250-259, 2011), where the authors were able to characterize such graph families F restricted to the cases {pipe}F{pipe} ≤ 1, {pipe}F{pipe} ≤ 2 and ≤ 3, respectively. In this paper, we complete the characterization of all the families that satisfy the above mentioned property. Additionally, we show the families that one gets when adding the condition {pipe}F{pipe} ≤ k for some k ≥ 4. © 2011 Springer.

A graph drawn on the plane is called 1-plane if each edge is crossed at most once by another edge. In this paper, we show that every 4-edge-connected 1-plane graph has a connected spanning plane subgraph. We also show that there exist infinitely many 4-connected 1-plane graphs that have no 2-connected spanning plane subgraphs. Moreover, we consider the condition of (Formula presented.) and (Formula presented.) such that every (Formula presented.) -connected 1-plane graph has an (Formula presented.) -connected spanning plane subgraph.

We introduce a construction called the cone over a graph. It is a natural generalisation of Mycielski's construction. We give a formula for the fractional chromatic numbers of all cones over graphs, which generalizes that given in [3] for Mycielski's construction. © 2001 John Wliey & Sons, Inc.

The graph grabbing game is a two-player game on a connected graph with a vertex-weight function. In the game, they alternately remove a non-cut vertex from the graph (i.e., the resulting graph remains connected) and get the weight assigned to the vertex. Each player's aim is to maximize his or her outcome, when all vertices have been taken. In this paper, we consider the graph grabbing game on totally-weighted graphs that are graphs with weight functions from a set of elements in the vertex set and the edge set to non-negative real numbers. In this version, when a player removes a non-cut vertex v, that player gets the weight of v plus the total weight assigned to the edges incident to v. In particular, we give some results of interest for the graph grabbing game on edge-weighted trees, i.e., every vertex has weight zero. Moreover, we consider the game on edge-weighed graphs in the altered rule that each player must keep the connectedness of graphs induced by edges.

A graph (Formula presented.) is called a (Formula presented.) -free graph if it does not contain (Formula presented.) as an induced subgraph. In 2014, Broersma, Patel, and Pyatkin showed that every 25-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3-tough is sufficient instead of 25-tough. In this paper, we show that every 2-tough (Formula presented.) -free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.

Gao, Huo, Liu, and Ma proved a result on the existence of paths connecting specified two vertices whose lengths differ by one or two. By using this result, they settled two famous conjectures due to Thomassen. In this paper, we improve their result, and obtain a generalization of a result of Bondy and Vince.

Let (Formula presented.) be a graph of order (Formula presented.). For an integer (Formula presented.), a partition (Formula presented.) of (Formula presented.) is called a (Formula presented.) -proper partition of (Formula presented.) if every (Formula presented.) induces a (Formula presented.) -connected subgraph of (Formula presented.). This concept was introduced by Ferrara et al., and Borozan et al. gave minimum degree conditions for the existence of a (Formula presented.) -proper partition. In particular, when (Formula presented.), they proved that if (Formula presented.), then (Formula presented.) has a 2-proper partition (Formula presented.) with (Formula presented.). Later, Chen et al. extended the result by giving a minimum degree sum condition for the existence of a 2-proper partition. In this paper, we introduce two new invariants of graphs (Formula presented.) and (Formula presented.), which are defined from degree sum of particular independent sets. Our result is that if (Formula presented.), then with some exceptions, (Formula presented.) has a 2-proper partition (Formula presented.) with (Formula presented.). We completely determine exceptional graphs. This result implies both of results by Borozan et al. and by Chen et al. Moreover, we obtain a minimum degree product condition for the existence of a 2-proper partition as a corollary of our result.

Let k≥2 be an integer. We say that a graph G is (K2∪kK1)-free if it does not contain K2∪kK1 as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2k-connected (K2∪kK1)-free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k-connected (K2∪kK1)-free graph with minimum degree at least [Formula presented] is hamiltonian or the Petersen graph.

Let k and n be positive integers. Let G be a graph of order n≤4k, and let n = ∑ki=1 ai be a partition of n into k positive integers ai with 1≤ai≤4. In Matsunaga (Preprint, 1995) one of the authors proved that if G is 2-connected and the minimum degree of G is at least k, then with certain types of exceptions being allowed, the vertex set of G can be decomposed into k disjoint subsets Al,...,Ak so that |Ai| = ai and "the subgraph induced by Ai is connected" for all i, 1≤i≤k. In the present paper we extend this result for connected graphs in general. The paper also features the existence of D3-paths with a prescribed endvertex in a graph. (A D3-path in a graph is a path of the graph whose removal leaves no component of order at least 3.) © 2000 Elsevier Science B.V. All rights reserved.

Let k be a positive integer. It is shown that if G is a graph of order 4 k with minimum degree at least 2 k, then G contains k vertex-disjoint copies of K1, 3, unless G is isomorphic to K2 k, 2 k with k being odd. © 2007 Elsevier B.V. All rights reserved.

We show that if G is a 3‐connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges. Copyright © 1989 Wiley Periodicals, Inc., A Wiley Company

Let cl(G) denote Ryjáček's closure of a claw-free graph G. In this article, we prove the following result. Let G be a 4-connected claw-free graph. Assume that G[NG(T)] is cyclically 3-connected if T is a maximal K3 in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267-276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262-272]. © 2011 Wiley Periodicals, Inc.

In [3], Faudree et al. considered the proposition “Every (X, Y)-free graph of sufficiently large order has a 2-factor,” and they determined those pairs (X, Y) which make this proposition true. Their result says that one of them is (X, Y) = (K1,4, P4). In this paper, we investigate the existence of 2-factors in r-connected (K1, k, P4)-free graphs. We prove that if r ≥ 1 and k ≥ 2, and if G is an r-connected (K1, k, P4)-free graph with minimum degree at least k − 1, then G has a 2-factor with at most max(k − r, 1) components unless (k − 1)K2 + (k − 2)K1 ⊆ G ⊆ (k − 1)K2 + Kk−2. The bound on the minimum degree is best possible. © 2008 International Academic Printing Co. Ltd. All rights reserved.

In this paper, we introduce the notion of a pyramidal tour with step-backs which is an extension of a pyramidal tour. By using this idea we shall show that for a class of distance matrices an optimal tour of traveling salesman problem can be computed in polynomial time. © 1998 Elsevier Science B.V. All rights reserved.

A graph is said to be K1,n‐free, if it contains no K1,n as an induced subgraph. We prove that for n ⩾ 3 and r ⩾ n −1, if G is a K1,n‐free graph with minimum degree at least (n2/4(n −1))r + (3n −6)/2 + (n −1)/4r, then G has an r‐factor (in the case where r is even, the condition r ⩾ n −1 can be dropped). Copyright © 1991 Wiley Periodicals, Inc., A Wiley Company

In this paper, we show that for any even integer t≥4, every 3-connected graph with no K 3,t-minor has a spanning tree whose maximum degree is at most t-1. This result is a common generalization of the result by Barnette (1966) [1] and the one by Chen, Egawa, Kawarabayashi, Mohar, and Ota (2011) [4]. © 2012 Elsevier Inc.

Barnette proved that every 3-connected planar graph has a 3-tree, where a 3-tree is a spanning tree whose maximum degree is at most three. In this paper, we consider an improvement of Barnette's result for the direction of K3, t-minor-free graphs. Note that any planar graph is K3, 3-minor-free. Actually, we show that for an even integer t ≥ 3, any 3-connected K3, t -minor-free graph has a (t - 1)-tree. © 2009 Elsevier B.V. All rights reserved.

It is shown that with one small exception, the 3‐connected graphs admitting longest cycles that contain less than four contractible edges of the parent graph are the members of three closely related infinite families. © 1993 John Wiley & Sons, Inc. Copyright © 1993 Wiley Periodicals, Inc., A Wiley Company