YAMASHITA Tomoki

Department of ScienceProfessor/Senior Staff

Last Updated :2024/09/14

■Researcher basic information

Researcher number

10410458

Research Keyword

  • 組合せ論   ハミルトン路   グラフ理論   次数和条件   ハミルトン閉路   

Research Field

  • Natural sciences / Applied mathematics and statistics
  • Natural sciences / Basic mathematics

■Career

Career

  • 2022/04 - Today  Kindai UniversityFaculty of Science and Engineering教授
  • 2015/04 - 2022/03  Kindai UniversityFaculty of Science and Engineering准教授
  • 2011/04 - 2015/03  Kindai UniversityFaculty of Science and Engineering講師
  • 2008/04 - 2011/03  Kitasato University一般教育講師
  • 2005/04 - 2008/03  Asahi UniversitySchool of Dentistry講師
  • 2004/04 - 2005/03  Keio UniversityFaculty of Science and Technology特別研究助手

■Research activity information

Paper

  • Jun Fujisawa; Masao Tsugaki; Tomoki Yamashita; Takamasa Yashima
    Discrete Mathematics Elsevier BV 347 (1) 113692 - 113692 0012-365X 2024/01
  • Shuya Chiba; Masao Tsugaki; Tomoki Yamashita
    Discrete Mathematics Elsevier BV 346 (12) 113633 - 113633 0012-365X 2023/12
  • Masao Tsugaki; Tomoki Yamashita; Takamasa Yashima
    Graphs and Combinatorics Springer Science and Business Media LLC 39 (2) 0911-0119 2023/03 [Refereed]
  • Shuya Chiba; Katsuhiro Ota; Tomoki Yamashita
    Journal of Graph Theory Wiley 103 (2) 340 - 358 0364-9024 2023/01 [Refereed]
  • Shuya Chiba; Masao Tsugaki; Tomoki Yamashita
    Discrete Mathematics Elsevier BV 345 (6) 112808 - 112808 0012-365X 2022/06 [Refereed]
  • Shuya Chiba; Akira Saito; Masao Tsugaki; Tomoki Yamashita
    Graphs and Combinatorics Springer Science and Business Media LLC 37 (5) 1841 - 1858 0911-0119 2021/09 [Refereed]
  • Guantao Chen; Shuya Chiba, Ronal; J. Gould; Xiaofeng Gu; Akira Saito; Masao Tsugaki; Tomoki Yamashita
    Discrete Mathematics 343 (2) 111663 - 111663 2020/02 [Refereed]
  • Masao Tsugaki; Tomoki Yamashita
    Australasian Journal of Combinatorics 77 69 - 86 2020 [Refereed]
  • Tomoki Shuya Chiba; Michitaka Furuya; Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita
    Electronic Journal of Combinatorics ELECTRONIC JOURNAL OF COMBINATORICS 26 (4) 1077-8926 2019/12 [Refereed]
     
    In [Graphs Combin. 24 (2008) 469-483], the third author and the fifth author conjectured that if G is a k-connected graph such that sigma(k+1)(G) >= vertical bar V (G)vertical bar + kappa(G) + (k - 2) (alpha(G) - 1), then G contains a Hamilton cycle, where sigma(k+1)(G), kappa(G) and alpha(G) are the minimum degree sum of k+1 independent vertices, the connectivity and the independence number of G, respectively. In this paper, we settle this conjecture. The degree sum condition is best possible.
  • On 2-factors with a specified number of components in line graphs
    Shuya Chiba; Yoshimi Egawa; Jun Fujisawa; Akira Saito; Ingo Schiermeyer; Masao Tsugaki; Tomoki Yamashita
    Acta Mathematica Universitatis Comenianae 88 (3) 541 - 546 2019/09 [Refereed]
  • Atsuhiro Nakamoto; Yoshiaki Oda; Mamoru Watanabe; Tomoki Yamashita
    Discret. Math. 341 (4) 1109 - 1113 2018 [Refereed]
  • Shuya Chiba; Tomoki Yamashita
    SIAM Journal on Discrete Mathematics Society for Industrial and Applied Mathematics Publications 32 (1) 394 - 409 0895-4801 2018 [Refereed]
     
    In this paper, we give the following result: If D is a digraph of order n, and if d+D(u) + d−D(v) ≥ n for every two distinct vertices u and v with (u, v) ∈/ A(D), then D has a directed 2-factor with exactly k directed cycles of length at least 3, where n ≥ 12k+3. This result is equivalent to the following result: If G is a balanced bipartite graph of order 2n with partite sets X and Y , and if dG(x) + dG(y) ≥ n + 2 for every two vertices x ∈ X and y ∈ Y with xy ∈/ E(G), then for every perfect matching M, G has a 2-factor with exactly k cycles of length at least 6 containing every edge of M, where n ≥ 12k + 3. These results are generalizations of theorems concerning Hamilton cycles due to Woodall [Proc. Lond. Math. Soc., 24 (1972), pp. 739–755] and Las Vergnas [Problémes de couplages et problémes hamiltoniens en théorie des graphes, Ph.D. thesis, University of Paris, 1972], respectively.
  • Shuya Chiba; Tomoki Yamashita
    Graphs and Combinatorics Springer Tokyo 34 (1) 1 - 83 0911-0119 2018/01 [Refereed]
     
    In this paper, we survey results and conjectures on degree conditions for the existence of vertex-disjoint cycles and paths. In particular, we focus on the type of degree conditions, the type of cycles or paths, and relations between results or conjectures.
  • Shuya Chiba; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 340 (12) 2871 - 2877 0012-365X 2017/12 [Refereed]
     
    Let G be a balanced bipartite graph of order 2n >= 4, and let sigma(1,1)(G) be the minimum degree sum of two non-adjacent vertices in different partite sets of G. In 1963, Moon and Moser proved that if sigma(1,1)(G) >= n + 1, then G is hamiltonian. In this note, we show that if k is a positive integer, then the Moon Moser condition also implies the existence of a 2-factor with exactly k cycles for sufficiently large graphs. In order to prove this, we also give a sigma(1,1) condition for the existence of k vertex-disjoint alternating cycles with respect to a chosen perfect matching in G. (C) 2017 Elsevier B.V. All rights reserved.
  • Shuya Chiba; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 340 (4) 678 - 690 0012-365X 2017/04 [Refereed]
     
    Let k be a positive integer, and let G be a graph of order n >= 3k and S be a set of k vertices of G. In this paper, we prove that if sigma(2)(G) > n + k - 1 + Delta(G[S]), then G can be partitioned into k vertex-disjoint cycles C1, Ck i, Ck such that vertical bar V(C-i) boolean AND S] = 1 for 1 <= i <= k, and vertical bar V(C-i)vertical bar = 3 for 1 <= i <= k - Delta(G[5]) and vertical bar V(C-i)vertical bar <= 4 for k - Delta(G[S]) <= i <= k - 1, where sigma(2)(G) denotes the minimum degree sum of two non-adjacent vertices in G and Delta(G[S]) denotes the maximum degree of the subgraph of G induced by S. This is a common generalization of the results obtained by Dong (2010) and Chiba et al. (2010), respectively. In order to show the main theorem, we further give other related results concerning the degree conditions for the existence of k vertex-disjoint cycles in which each cycle contains a vertex in a specified vertex subset. (C) 2016 Elsevier B.V. All rights reserved.
  • Ryota Matsubara; Hajime Matsumura; Masao Tsugaki; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 340 (2) 87 - 95 0012-365X 2017/02 [Refereed]
     
    Let G be a graph, and let S be a subset of the vertex set of G. We denote the set of the end vertices of a path P by end(P). A path P is an S-path if vertical bar V(P)vertical bar >= 2 and V(P) boolean AND S = end(P). An S-path-system is a graph H such that H contains all vertices of S and every component of H is an S-path. In this paper, we give a sharp degree sum condition for a bipartite graph to have a spanning S-path-system. (C) 2016 Elsevier B.V. All rights reserved.
  • Enumeration of unlabeled graphs such that both the graph and its complement are 2-connected
    K.Kobata; S.Tazawa; T.Yamashita
    SUT J.~Math. 52 (1) 41 - 47 2016 [Refereed]
  • Yoshimi Egawa; Jun Fujisawa; Michael D. Plummer; Akira Saito; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 338 (12) 2260 - 2274 0012-365X 2015/12 [Refereed]
     
    Aldred and Plummer (1999) have proved that every m-connected K-1,K-m-k+2-free graph of even order contains a perfect matching which avoids k prescribed edges. They have also proved that the result is best possible in the range 1 <= k <= 1/2(m + 1). In this paper, we show that if 1/2(m + 2) <= k <= m - 1, their result is not best possible. We prove that if m >= 4 and 1/2(m + 2) <= k <= m - 1, every K-1,K-[2m-k+4/3]-free graph of even order contains a perfect matching which avoids k prescribed edges. While this is a best possible result in terms of the order of a forbidden star, if 2m - k + 4 equivalent to 0 (mod 3), we also prove that only finitely many sharpness examples exist. (C) 2015 Elsevier B.V. All rights reserved.
  • Mikio Kano; Kenta Ozeki; Kazuhiro Suzuki; Masao Tsugaki; Tomoki Yamashita
    ELECTRONIC JOURNAL OF COMBINATORICS ELECTRONIC JOURNAL OF COMBINATORICS 22 (1) 113  1077-8926 2015/01 [Refereed]
     
    A tree is called a k-tree if its maximum degree is at most k. We prove the following theorem. Let k >= 2 be an integer, and G he a connected bipartite graph with bipartition (A, B) such that |A| <= |B| <= (k - 1) |A| + 1. If sigma(k)(G) >= |B|, then G has a spanning k-tree, where sigma(k)(G) denotes the minimum degree sum of k independent vertices of G. Moreover, the condition on sigma(k) (G) is sharp. It was shown by Win (Abh. Math. Sem. Univ. Hamburg, 43, 263-267, 1975) that if a connected graph H satisfies sigma(k)(H) >= |H| - 1, then H has a spanning k-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.
  • Shuya Chiba; Masao Tsugaki; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 333 66 - 83 0012-365X 2014/10 [Refereed]
     
    We denote the order, the independence number, the connectivity and the minimum degree sum of independent four vertices of a graph G by n(G), alpha(G), K(G) and sigma(4)(G), respectively. The circumference of a graph G, denoted by c(G), is the length of a longest cycle in G. We call a cycle C of a graph G a D-k-cycle if the order of each component of G - V(C) is at most k - 1. Our goal is to accomplish the proof of the statement that if G is a 4-connected graph, then c(G) >= min{sigma(4)(G) - K(G) - alpha(G) + 1, n(G)}. In order to prove this, we consider three conditions for the construction of the outside of a longest cycle: (i) If G is a 3-connected graph and every longest cycle of G is a D-2-cycle, then c(G) >= min{sigma(4)(G) - K(G) - alpha(G) +1, n (G)} (ii) If G is a 3-connected graph and every longest cycle is a D-3-cycle and some longest cycle is not a D-2-cycle, then c(G) >= sigma(4)(G) - K(G) - 4. (iii) If G is a 4-connected graph and some longest cycle is not a D-3-cycle, then c(G) >= sigma(4)(G) - 8. For each condition, the lower bound of the circumference is sharp. (C) 2014 Elsevier B.V. All rights reserved.
  • Ryota Matsubara; Masao Tsugaki; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER JAPAN KK 30 (4) 957 - 962 0911-0119 2014/07 [Refereed]
     
    In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that for every independent set S in G of order k with . Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win's result (Abh Math Sem Univ Hamburg, 43:263-267, 1975) and Kano and Kishimoto's result (Graph Comb, 2013) as corollaries.
  • Haruhide Matsuda; Kenta Ozeki; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER JAPAN KK 30 (2) 429 - 437 0911-0119 2014/03 [Refereed]
     
    Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n - 2. These conditions are best possible. A related conjecture also is proposed.
  • Haruko Okamura; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER JAPAN KK 29 (4) 1077 - 1085 0911-0119 2013/07 [Refereed]
     
    We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d (G) (v) be the degree of a vertex v in a graph G. For G[X, Y] and we define . Amar et al. (Opusc. Math. 29:345-364, 2009) obtained sigma (1,1)(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| a parts per thousand yen |Y| and such that sigma (1,1)(S) a parts per thousand yen |X| + 1, then either there exists a cycle containing S or and there exists a cycle containing Y. This degree sum condition is sharp.
  • Mikio Kano; Tomoki Yamashita; Zheng Yan
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8296 95 - 100 0302-9743 2013 [Refereed]
     
    A tree is called a caterpillar if all its leaves are adjacent to the same its path, and the path is called a spine of the caterpillar. Broersma and Tuinstra proved that if a connected graph G satisfies σ2(G) ≥ |G| - k + 1 for an integer k ≥ 2, then G has a spanning tree having at most k leaves. In this paper we improve this result as follows. If a connected graph G satisfies σ2(G) ≥ |G| - k + 1 and |G| ≥ 3k - 10 for an integer k ≥ 2, then G has a spanning caterpillar having at most k leaves. Moreover, if |G| ≥ 3k - 7, then for any longest path, G has a spanning caterpillar having at most k leaves such that its spine is the longest path. These three lower bounds on σ2(G) and |G| are sharp. © 2013 Springer-Verlag.
  • Kenta Ozeki; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER JAPAN KK 28 (6) 859 - 868 0911-0119 2012/11 [Refereed]
     
    Let G be a graph. We denote p(G) and c(G) the order of a longest path and the order of a longest cycle of G, respectively. Let kappa(G) be the connectivity of G, and let sigma (3)(G) be the minimum degree sum of an independent set of three vertices in G. In this paper, we prove that if G is a 2-connected graph with p(G) - c(G) a parts per thousand yen 2, then either (i) c(G) a parts per thousand yen sigma (3)(G) - 3 or (ii) kappa(G) = 2 and p(G) a parts per thousand yen sigma (3)(G) - 1. This result implies several known results as corollaries and gives a new lower bound of the circumference.
  • Shuya Chiba; Jun Fujisawa; Masao Tsugaki; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 312 (11) 1857 - 1862 0012-365X 2012/06 [Refereed]
     
    Let G vertical bar X, Y vertical bar be a 2-connected bipartite graph with vertical bar X vertical bar >= vertical bar Y vertical bar. For S subset of V(G), we define delta(S; G) := min{d(G)(nu) : nu is an element of S}. We define sigma(1,1)(G) := min {d(G)(x) + d(G)(y) : x is an element of X, y is an element of Y. xy is not an element of E(G)} and sigma(2)(X) := min{d(G)(x) + d(G)(y) : x, y is an element of X, x not equal y}. We denote by c(G) the length of a longest cycle in G. Jackson [B. Jackson, Long cycles in bipartite graphs, J. Combin. Theory Ser. B 38 (1985) 118-131] proved that c(G) >= min{2 delta(X; G) + 2 delta(Y; G) - 2, 4 delta(X; G) - 4, 2 vertical bar Y vertical bar}. In this paper, we extend this result, and prove that c(G) >= min{2 sigma(1,1)(G) - 2, 2 sigma(2)(X) - 4, 2 vertical bar Y vertical bar}. (C) 2012 Elsevier B.V. All rights reserved.
  • Mikio Kano; Aung Kyaw; Haruhide Matsuda; Kenta Ozeki; Akira Saito; Tomoki Yamashita
    ARS COMBINATORIA CHARLES BABBAGE RES CTR 103 137 - 154 0381-7032 2012/01 [Refereed]
     
    For a graph H and an integer k >= 2, let sigma(k)(H) denote the minimum degree sum of k independent vertices of H. We prove that if a connected claw-free graph G satisfies sigma(k+1)(G) >= vertical bar G vertical bar - k, then G has a spanning tree with at most k leaves. We also show that the bound vertical bar G vertical bar - k is sharp and discuss the maximum degree of the required spanning trees.
  • Kenta Ozeki; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER JAPAN KK 27 (1) 1 - 26 0911-0119 2011/01 [Refereed]
     
    In this paper, we give a survey of spanning trees. We mainly deal with spanning trees having some particular properties concerning a hamiltonian properties, for example, spanning trees with bounded degree, with bounded number of leaves, or with bounded number of branch vertices. Moreover, we also study spanning trees with some other properties, motivated from optimization aspects or application for some problems.
  • Kenta Ozeki; Tomoki Yamashita
    ARS COMBINATORIA CHARLES BABBAGE RES CTR 98 173 - 182 0381-7032 2011/01 [Refereed]
     
    A cycle C in a graph G is said to be dominating if E(G - C) = empty set. Enomoto et al. showed that if G is a 2-connected triangle-free graph with alpha(G) <= 2 kappa(G) - 2, then every longest cycle is dominating. But it is unknown whether the condition on the independence number is sharp. In this paper, we show that if G is a 2-connected triangle-free graph with alpha(G) <= 2 kappa(G) - 1, then G has a longest cycle which is dominating. This condition is best possible.
  • Jun Fujisawa; Hajime Matsumura; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER TOKYO 26 (5) 695 - 720 0911-0119 2010/09 [Refereed]
     
    In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n >= 1, k >= 3, c >= 0 and G be an n-connected graph. Suppose that for every independent set S. V( G) of cardinality n( k - 1) + c + 2, there exists a vertex set X. S of cardinality k such that the degree sum of vertices in X is at least |V(G)| - c - 1. Then G has a spanning tree T with maximum degree at most k + [c/n] and Sigma(v is an element of V(T)) max{d(T) (v) - k, 0} <= c.
  • Kenta Ozeki; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER TOKYO 26 (4) 591 - 596 0911-0119 2010/07 [Refereed]
     
    Let G be a connected graph, let X subset of V (G) and let f be a mapping from X to {2, 3, ...}. Kaneko and Yoshimoto (Inf Process Lett 73: 163-165, 2000) conjectured that if vertical bar N(G) (S) - X vertical bar >= f (S) - 2 vertical bar S vertical bar + omega(G)(S) + 1 for any subset S subset of X, then there exists a spanning tree T such that d(T) (x) >= f (x) for all x is an element of X. In this paper, we show a result with a stronger assumption than this conjecture; if vertical bar N(G)(S) - X vertical bar >= f (S) - 2 vertical bar S vertical bar + alpha (S) + 1 for any subset S subset of X, then there exists a spanning tree T such that d(T) (x) >= f (x) for all x is an element of X.
  • A neighborhood and degree condition for panconnectivity
    Ryota Matsubara; T.Yamashita; Masao Tsugaki
    Austras. J.Combin. 47 3 - 10 2010/06 [Refereed]
  • Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 309 (23-24) 6503 - 6507 0012-365X 2009/12 [Refereed]
     
    For a graph G, p(G) and c(G) denote the orders of a longest path and a longest cycle of G. respectively. For a graph G, we denote by d(G)(x) and K(G) the degree of a vertex x in G and the connectivity of G, respectively. In this paper, we prove that if G is a 3-connected graph of order n such that Sigma(4)(i=1) d(G)(x(i)) >= n + k (G) + 3 for every independent set {x(1), x(2), x(3), x(4)}, then p(G) - c(G) <= 1. This is a stronger result than the problem of Lu et al. [M. Lu, H. Liu, F. Tian, Two sufficient conditions for dominating cycles, J. Graph Theory 49 (2005) 134-150], and this degree condition is sharp. (C) 2009 Elsevier B.V. All rights reserved.
  • Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita
    JOURNAL OF GRAPH THEORY JOHN WILEY & SONS INC 62 (3) 279 - 291 0364-9024 2009/11 [Refereed]
     
    For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. In this paper, we prove that if G is a 3-connected graph of order n such that the minimum degree sum of four independent vertices is at least n + 6, then p(G) - c(G) <= 2. By considering our result and the results in [J Graph Theory 20 (1995), 213-225; Amer Math Monthly 67 (1950), 55], we propose a conjecture which is a generalization of Bondy's conjecture. Furthermore, using our result, for a graph satisfying the above conditions, we obtain a new lower bound of the circumference and establish Thomassen's conjecture.(C) 2009 Wiley Periodicals, Inc. J Graph Theory 62: 279-291, 2009
  • Masao Tsugaki; Tomoki Yamashita
    ARS COMBINATORIA CHARLES BABBAGE RES CTR 91 113 - 121 0381-7032 2009/04 [Refereed]
     
    Let G be a graph and let sigma(k)(G) be the minimum degree sum of an independent set of k vertices. For S subset of V(G) with vertical bar S vertical bar >= k, let Delta(k)(S) denote the maximum value among the degree sums of the subset of k vertices in S. A cycle C of a graph G is said to be a dominating cycle if V(G \ C) is an independent set. In [2], Bondy showed that if G is a 2-connected graph with sigma(3) (G) >= vertical bar V(G)vertical bar + 2, then any longest cycle of G is a dominating cycle. In this paper, we improve it as follows: if G is a 2-connected graph with Delta(3)(S) >= vertical bar V(G)vertical bar + 2 for every independent set S of order kappa(G) + 1, then any longest cycle of G is a dominating cycle.
  • Kenta Ozeki; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 309 (6) 1584 - 1592 0012-365X 2009/04 [Refereed]
     
    Let G be an (in + 2)-graph on it vertices, and F be a linear forest in G with |E(F)| = in and cut (F) = s, where omega(1) (F) is the number of components of order one in F. We denote by sigma(3)(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several sigma(3) conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if sigma(3)(G) >= n + 2m + 2 + max{s - 3, 0}, then every longest cycle passing through F is dominating. Using this result, we prove that if sigma(3)(G) >= n + k(G) + 2m -1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and sigma(3)(G) >= n + k(G) + 2, then G is hamiltonian-connected. (C) 2008 Elsevier B.V. All rights reserved.
  • Ken-ichi Kawarabayashi; Kenta Ozeki; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 308 (24) 5899 - 5906 0012-365X 2008/12 [Refereed]
     
    For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van dell Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T Yamashita, Oil relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree Slims, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G) - c(G) at most I or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if sigma(4)(G) >= 1/3 (4n - 2), then p(G) - c(G) <= 1, and (ii) if sigma(4)(G) >= n + 3, then p(G) - c(G) <= 2.C) 2007 Elsevier B.V. All rights reserved.
  • Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 308 (24) 6584 - 6587 0012-365X 2008/12 [Refereed]
     
    Let G be a graph. For S subset of V(G), let Delta(k) (S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Delta(2) (S) >= d for every independent set S of order kappa(G) + 1, then G has a cycle of length at least min{d, |V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Delta(2)(S) >= |V(G)| for every independent set S of order kappa(X) + 1 in G|X|, then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles. (C) 2007 Elsevier B.V. All rights reserved.
  • Kenta Ozeki; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER TOKYO 24 (5) 469 - 483 0911-0119 2008/10 [Refereed]
     
    Let G be a graph and S. V(G). We denote by a(S) the maximum number of pairwise nonadjacent vertices in S. For x, y epsilon V(G), the local connectivity kappa(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define kappa(S) = min{kappa(x, y) : x, y epsilon S, x not equal y}. In this paper, we show that if kappa(S) >= 3 and Sigma(4)(i=1) dG(x(i)) >= | V(G)|+ kappa(S)+ alpha(S) - 1 for every independent set {x(1), x(2), x(3), x(4)} subset of S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian.
  • Jun Fujisawa; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 308 (12) 2382 - 2388 0012-365X 2008/06 [Refereed]
     
    Let G be a (k + m)-connected graph and F be a linear forest in G such that vertical bar E(F)vertical bar = m and F has at most k - 2 components of order 1, where k >= 2 and m >= 0. In this paper, we prove that if every independent set S of G with vertical bar S vertical bar = k + 1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min {d - m, vertical bar V(G)vertical bar} which contains all the vertices and edges of F. (C) 2007 Elsevier B.V. All rights reserved.
  • Jun Fujisawa; Tomoki Yamashita
    JOURNAL OF GRAPH THEORY JOHN WILEY & SONS INC 58 (2) 179 - 190 0364-9024 2008/06 [Refereed]
     
    In this article, we prove the following theorem. Let k >= 3 be an integer, G be a k-connected graph with minimum degree d and X be a set of k + 1 vertices on a cycle. Then G has a cycle of length at least min{2d, vertical bar V(G)vertical bar} passing through X This result gives the positive answer to the Question posed by Locke [8]. (C) 2008 Wiley Periodicals, Inc.
  • Jun Fujisawa; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 308 (9) 1612 - 1619 0012-365X 2008/05 [Refereed]
     
    Ore presented a degree condition involving every pair of nonadjacent vertices for a graph to be hamiltonian. Fan [New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221-227] showed that not all the pairs of nonadjacent vertices are required, but only the pairs of vertices at the distance two suffice. Bedrossian et al. [A generalization of Fan's condition for harniltonicity, pancyclicity, and hamiltonian connectedness, Discrete Math. 115 (1993) 39-50] improved Fan's result involving the pairs of vertices contained in an induced claw or an induced modified claw. On the other hand, Matthews and Sumner [Longest paths and cycles in K-1,K-3-free graphs, J. Graph Theory 9 (1985) 269-277] gave a minimum degree condition for a claw-free graph to be hamiltonian. In this paper, we give a new degree condition in an induced claw or an induced modified claw ensuring the hamiltonicity of graphs which extends both results of Bederossian et al. and Matthews and Sumner. (c) 2007 Elsevier B.V. All rights reserved.
  • Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 308 (9) 1620 - 1627 0012-365X 2008/05 [Refereed]
     
    For a graph G, let sigma(k) (G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n >= 3 with sigma(2) (G) >= n then G is hamiltonian. Let kappa(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with sigma(3) (G) >= n + kappa(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with 93 (G) >= n + 2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with sigma(4) (G) >= n + kappa(G) + 3, then G contains a longest cycle which is a dominating cycle. (c) 2007 Elsevier B.V. All rights reserved.
  • Yoshimi Egawa; Haruhide Matsuda; Tomoki Yamashita; Kiyoshi Yoshimoto
    GRAPHS AND COMBINATORICS SPRINGER TOKYO 24 (1) 13 - 18 0911-0119 2008/02 [Refereed]
     
    Let k >= 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least vertical bar G vertical bar + 1, then for each subset S of V(G) with vertical bar S vertical bar = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore's theorem which guarantees the existence of a Hamilton path connecting any two vertices.
  • A neighborhood and degree condition for pancyclicity and vertex pancyclicity
    R.Matsubara; M.Tsugaki; T.Yamashita
    Austras. J.Combin. 40 15 - 20 2008/01 [Refereed]
  • Shinya Fujita; Akira Saito; Tomoki Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 307 (23) 2934 - 2942 0012-365X 2007/11 [Refereed]
     
    A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157-183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least 1/3(n + 2) is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams' Theorem corresponds to the case of k = 1 of this result. (C) 2007 Elsevier B.V. All rights reserved.
  • Masao Tsugaki; Tomoki Yamashita
    GRAPHS AND COMBINATORICS SPRINGER TOKYO 23 (5) 585 - 598 0911-0119 2007/10 [Refereed]
     
    In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k >= 2 and m >= 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n -k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.
  • Tomoki Yamashita
    Discuss.Math. Graph Theory 27 (2) 323 - 332 2007/08 [Refereed]
  • Tomoki Yamashita
    JOURNAL OF GRAPH THEORY JOHN WILEY & SONS INC 54 (4) 277 - 283 0364-9024 2007/04 [Refereed]
     
    For a graph G, we denote by d(G)(x) and kappa(G) the degree of a vertex x in G and the connectivity of G, respectively. In this article, we show that if G is a 3-connected graph of order n such that d(G)(x) + d(G)(y) + d(G)(z) >= for every independent set {x, y, z}, then G contains a cycle of length least min{d - kappa(G), n}. (C) 2006 Wiley Periodicals, Inc.
  • Degree Sum Condition and Vertex-Disjoint Cycles in a graph
    S.Fujita; H.Matsumura; M.Tsugaki; T.Yamashita
    Austras. J.Combin. 35 237 - 255 2006/09 [Refereed]
  • Heavy cycles in hamiltonian weighted graphs
    J.Fujisawa; S.Fujita; T.Yamashita
    AKCE J.~Graphs.~Combin. 2 99 - 102 2004/04 [Refereed]
  • A Saito; T Yamashita
    DISCRETE MATHEMATICS ELSEVIER SCIENCE BV 278 (1-3) 219 - 226 0012-365X 2004/03 [Refereed]
     
    Let G be a graph and let f be a non-negative integer-valued function defined on V(G). Then a cycle C is called an f-dominating cycle if d(G)(v, C) less than or equal to f (v) holds for each v is an element of V(G), where d(G)(v,C) denotes the distance between v and C. A set S is called an f-stable set if d(G)(u, v) greater than or equal to f (u) + f (v) holds for each pair of distinct vertices u, v in S, and denote by alpha(f)(G) the order of a largest f-stable set in G. In this paper, we prove that if a k-connected graph G (k greater than or equal to 2) satisfies alpha(f+1)(G) less than or equal to k, then G has an f-dominating cycle, where f + 1 is the function defined by (f + 1)(v) = f (v) + 1. By taking an appropriate function as f, we can deduce a number of known results from this theorem. (C) 2003 Elsevier B.V. All rights reserved.
  • A Saito; T Yamashita
    ARS COMBINATORIA CHARLES BABBAGE RES CTR 69 3 - 8 0381-7032 2003/10 [Refereed]
     
    A cycle C in a graph G is said to be a dominating cycle if every vertex of G has a neighbor on C. Strengthening a result of Bondy and Fan [3] for tough graphs, we prove that a k-connected graph G (k greater than or equal to 2) of order p with t(G) > k/(k + 1) has a dominating cycle if Sigma(xis an element ofS) deg(G) x greater than or equal to p-2k-2 for each S subset of V(G) of order k + 1 in which every pair of vertices in S have distance at least four in G.

MISC

Books and other publications

  • Bondy, J. A. (John Adrian); Murty, U. S. R.; 山下, 登茂紀; 千葉, 周也 (Joint translation)丸善出版 2022/11 9784621307564 xiv, 637p
  • 初学者にやさしい統計学
    大橋 常道; 谷口 哲也; 山下登茂紀 (Joint work)コロナ社 2010/03

Lectures, oral presentations, etc.

  • 山下 登茂紀
    Japanese Conference on Combinatorics and its Applications 2024  2024/08
  • 山下登茂紀
    離散数学とその応用研究集会 2021  2021/08
  • 閉路の存在性に関する定理の関係について  [Not invited]
    山下登茂紀
    日本応用数理学会 2016年度年会  2016/09
  • 閉路や木が存在するための次数和条件  [Not invited]
    山下登茂紀
    平成27年度 RIMS 共同研究「デザイン、符号、グラフおよびその周辺」  2015/07
  • ハミルトン閉路が存在するための次数和条件  [Not invited]
    千葉 周也; 古谷 倫貴; 小関 健太; 津垣 正男; 山下 登茂紀
    離散数学とその応用研究集会  2014/08
  • Balanced partitions on permutations and their application to a geometric problem  [Not invited]
    中本 敦浩; 小田 芳彰; 山下 登茂紀; 渡辺 守
    日本数学会2013年度秋期総合分科会  2013/09
  • グラフの不変量と閉路の存在について  [Not invited]
    山下登茂紀
    日本応用数理学会2012年度年会  2012/08
  • Degree sum conditions concerning the connectivity and the independence number  [Not invited]
    S.Chiba; M.Tsugaki; T.Yamashita
    Cycles in Graphs  2012/06
  • Degree sum conditions concerning the order, the connectivity and the independence number for the circumference  [Not invited]
    S.Chiba; M.Tsugaki; T.Yamashita
    Workshop Cycles and Colourings 2011  2011/09

Affiliated academic society

  • THE MATHEMATICAL SOCIETY OF JAPAN   

Research Themes

Social Contribution Activities

  • 教員免許状更新講習
    Date (from-to) : 2018/08/05-2018/08/05
    Role : Lecturer
    Category : Others
  • 教員免許状更新講習
    Date (from-to) : 2017/08/05-2017/08/05
    Role : Lecturer
  • 教員免許状更新講習
    Date (from-to) : 2016/08/05-2016/08/05
    Role : Lecturer
  • 教員免許状更新講習
    Date (from-to) : 2015/08/07-2015/08/07
    Role : Lecturer
  • 教員免許状更新講習
    Date (from-to) : 2014/08/07-2014/08/07
    Role : Lecturer