Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s11590-019-01442-9

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

DOI： 10.1007/978-3-030-60440-0_29

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/wg/wg2020.html#FujitaPS20

Publishing type：Research paper (scientific journal)  

DOI： 10.1017/S0963548319000014

researchmap

Publishing type：Research paper (scientific journal)  

researchmap

Other Link： https://dblp.uni-trier.de/db/journals/corr/corr1908.html#abs-1908-06664

Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.dam.2018.11.018

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.disc.2019.03.012

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer New York LLC  

Let G be a graph, and let w be a positive real-valued weight function on V(G). For every subset X of V(G), let (Formula presented.). A non-empty subset (Formula presented.) is a weighted safe set of (G, w) if, for every component C of the subgraph induced by S and every component D of (Formula presented.), we have (Formula presented.) whenever there is an edge between C and D. If the subgraph of G induced by a weighted safe set S is connected, then the set S is called a connected weighted safe set of (G, w). The weighted safe number(Formula presented.) and connected weighted safe number(Formula presented.) of (G, w) are the minimum weights w(S) among all weighted safe sets and all connected weighted safe sets of (G, w), respectively. It is easy to see that for any pair (G, w), (Formula presented.) by their definitions. In this paper, we discuss the possible equality when G is a path or a cycle. We also give an answer to a problem due to Tittmann et al. (Eur J Combin 32:954–974, 2011) concerning subgraph component polynomials for cycles and complete graphs.

DOI： 10.1007/s10878-018-0316-4

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：INT PRESS BOSTON, INC  

In 1966, T. Gallai asked whether every connected graph has a vertex that appears in all longest paths. Since then this question has attracted much attention and much work has been done on this topic. One important open question in this area is to ask whether any three longest paths contain a common vertex in a connected graph. It was conjectured that the answer to this question is positive. In this paper, we propose a new approach in view of distances among longest paths in a connected graph, and give a substantial progress towards the conjecture along the idea.

DOI： 10.4310/JOC.2019.v10.n2.a2

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Wiley-Liss Inc.  

For an edge-colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge-colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge-colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge-colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.

DOI： 10.1002/jgt.22163

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Academic Press  

Let G be a graph on n vertices with independence number α. We prove that if n is sufficiently large (n≥α2k+1 will do), then G always contains a k-connected subgraph on at least n∕α vertices. The value of n∕α is sharp, since G might be the disjoint union of α equally-sized cliques. For k≥3 and α=2,3, we shall prove that the same result holds for n≥4(k−1) and n≥[Formula presented] respectively, and that these lower bounds on n are sharp.

DOI： 10.1016/j.ejc.2018.01.004

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：WILEY  

Let G=(V,E) be a graph and let w:V>0 be a positive weight function on the vertices of G. For every subset X of V, let w(X):=Sigma vGw(v). A non-empty subset SV(G) is a weighted safe set if, for every component C of the subgraph induced by S and every component D of G\S, we have w(C)w(D) whenever there is an edge between C and D. If the subgraph G[S] induced by a weighted safe set S is connected, then the set S is called a weighted connected safe set. In this article, we show that the problem of computing the minimum weight of a safe set is NP-hard for trees, even if the underlying tree is restricted to be a star, but it is polynomially solvable for paths. We also give an O(nlog?n) time 2-approximation algorithm for finding a weighted connected safe set with minimum weight in a weighted tree. Then, as a generalization of the concept of a minimum safe set, we define the concept of a parameterized infinite family of proper central subgraphs on weighted trees, whose polar ends are the vertex set of the tree and the centroid points. We show that each of these central subgraphs includes a centroid point.

DOI： 10.1002/net.21794

Web of Science

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s10878-017-0205-2

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

For a connected graph G=(V(G),E(G)), a non-empty subset S of V(G) is a safe set if, for every component C of G[S] and every component D of G−S, we have |V(C)|≥|V(D)| whenever there exists an edge of G between C and D. If G[S] is connected, then S is called a connected safe set. The safe number s(G) of G is defined as s(G)≔min{|S|:S is a safe set of G}, and the connected safe number cs(G) of G is defined as cs(G)≔min{|S|:S is a connected safe set of G}. The integrity of a graph G is defined as I(G)≔min{|S|+τ(G−S):S⊆V(G)}, where τ(G−S) is the order of the largest component of G−S. In this paper, we discuss a relationship between the (connected) safe number and the integrity in a connected graph.

DOI： 10.1016/j.dam.2018.03.074

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

A kernel by properly colored paths of an arc-colored digraph D is a set S of vertices of D such that (i) no two vertices of S are connected by a properly colored directed path in D, and (ii) every vertex outside S can reach S by a properly colored directed path in D. In this paper, we conjecture that every arc-colored digraph with all cycles properly colored has such a kernel and verify the conjecture for digraphs with no intersecting cycles, semi-complete digraphs and bipartite tournaments, respectively. Moreover, weaker conditions for the latter two classes of digraphs are given.

DOI： 10.1016/j.disc.2018.02.014

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

It is easy to see that in a connected graph any 2 longest paths have a vertex in common. For k≥7, Skupień in 1966 obtained a connected graph in which some k longest paths have no common vertex, but every k−1 longest paths have a common vertex. It is not known whether every 3 longest paths in a connected graph have a common vertex and similarly for 4, 5, and 6 longest path. Fujita et al. in 2015 give an upper bound on distance among 3 longest paths in a connected graph. In this paper we give a similar upper bound on distance between 4 longest paths and also for k longest paths, in general.

DOI： 10.1016/j.disc.2017.09.029

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A graph G is said to be K-1,K-r-free if G does not contain an induced subgraph isomorphic to K-1,K-r. Let k, r, t be integers with k >= 2 and t >= 3. In this paper, we prove that if G is a K-1,K-r-free graph of order at least (k - 1)(t(r - 1)+1) + 1 with delta(G) >= t and r >= 2t 1, then G contains k vertex-disjoint copies of K-1,K- t. This result shows that the conjecture in Fujita (2008) is true for r >= 2t - 1 and t >= 3. Furthermore, we obtain a weaker version of Fujita's conjecture, that is, if G is a K-1,K-r-free graph of order at least (k - 1)(t(r - 1) + 1 (t - 1)(t - 2)) + 1 with delta(G) >= t and r >= 6, then G contains k vertex-disjoint copies of K-1,K-t. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2016.11.034

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

For an edge-colored graph G, the minimum color degree of G means the minimum number of colors on edges which are incident to each vertex of G. We prove that if G is an edge-colored graph with minimum color degree at least 5 then V (G) can be partitioned into two parts such that each part induces a subgraph with minimum color degree at least 2. We show this theorem by proving a much stronger form. Moreover, we point out an important relationship between our theorem and Bermond-Thomassen's conjecture in digraphs.

DOI： 10.1016/j.endm.2017.06.078

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：WILEY-BLACKWELL  

Given k >= 1, a k-proper partition of a graph G is a partition P of V (G) such that each part P of P induces a k-connected subgraph of G. We prove that if G is a graph of order n such that d(G) >= root n, then G has a 2-proper partition with at most n/delta(G) parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that if G is a graph of order n with minimum degree
delta(G) >= root c(k - 1)n,
where c = 2123/180, then G has a k-proper partition into at most cn/delta(G) parts. This improves a result of Ferrara et al. (Discrete Math 313 (2013), 760-764), and both the degree condition and the number of parts is best possible up to the constant c. (C) 2015 Wiley Periodicals, Inc.

DOI： 10.1002/jgt.21904

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS INC ELSEVIER SCIENCE  

A well-known conjecture of Thomassen says that every (a + b + 1)-connected graph with a >= b can be decomposed into two parts A and B such that A is a-connected and B is b-connected. The case b = 2 is settled by Thomassen himself, but the conjecture is still open for b >= 3.
Motivated by this, we prove that every k-connected graph G (with k >= 4) has a subgraph M such that either
1. M is 3-connected with at most 5 vertices (thus G-V(M) is (k - 5)-connected), or
2. M is an induced cycle such that G-V(C) is (k - 2)-connected.
This result improves previous known results by Egawa and Kawarabayashi, respectively. Our result is also related to results and questions of Mader concerning critically k-connected graphs. We partially answer the question of Mader in 1988. (C) 2015 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.jctb.2015.12.001

Web of Science

J-GLOBAL

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

Let G be a graph on n vertices with independence number α. What is the largest k-connected subgraph that G must contain? We prove that if n is sufficiently large (n≥α2k+1 will do), then G contains a k-connected subgraph on at least n/α vertices. This is sharp, since G might be the disjoint union of α equally-sized cliques. For k≥3 and α=2,3, we shall prove that the same result holds for n≥4(k−1) and n≥27(k−1)4 sharp.

DOI： 10.1016/j.endm.2016.09.019

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

A safe set of a graph G = (V,E) is a non-empty subset S of V such that for every component A of G[S] and every component B of G[V \\ S], we have |A| ≥ |B| whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

DOI： 10.1007/978-3-319-48749-6_18

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A non-empty subset S of the vertices of a connected graph G = (V(G), E(G)) is a safe set if, for every connected component C of G[S] and every connected component D of G - S , we have vertical bar C vertical bar >= vertical bar D vertical bar whenever there exists an edge of G between C and D. If G[S] is connected, then S is called a connected safe set. We discuss the minimum sizes of safe sets and connected safe sets in connected graphs. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2016.07.020

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier B.V.  

Let G=(V,E) be a graph, and w:V→Q&gt
0 be a positive weight function on the vertices of G. For every subset X of V, let w(X)=∑v∈Gw(v). A non-empty subset S⊂V(G) is a weighted safe set if, for every component C of the subgraph induced by S and every component D of G\\S, we have w(C)≥w(D) whenever there is an edge between C and D. In this paper we show that the problem of computing the minimum weight of a safe set is NP-hard for trees, even if the underlining tree is restricted to be a star, but it is polynomially solvable for paths. Then we define the concept of a parameterized infinite family of “proper central subgraphs” on trees, whose polar ends are the minimum-weight connected safe sets and the centroids. We show that each of these central subgraphs includes a centroid. We also give a linear-time algorithm to find all of these subgraphs on unweighted trees.

DOI： 10.1016/j.endm.2016.09.015

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A path pi = (v(1), v(2), ... , v(k+1)) in a graph G = (V, E) is a downhill path if for every i, 1 <= i <= k, deg(v(i)) >= deg(v(i+1)), where deg(v(i)) denotes the degree of vertex v(i) is an element of V. A downhill dominating set DDS is a set S subset of V having the property that every vertex v is an element of V lies on a downhill path originating from some vertex in S. The downhill domination number gamma(dn)(G) equals the minimum cardinality of a DDS of G. A DDS having minimum cardinality is called a gamma(dn)-set of G. In this note, we give an enumeration of all the distinct gamma(dn)-sets of G, and we show that there is a linear time algorithm to determine the downhill domination number of a graph. (c) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ipl.2015.02.003

Web of Science

J-GLOBAL

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER JAPAN KK  

A k-rainbow dominating function of a graph G is a function f from the vertices V(G) to such that, for all , either or . The k-rainbow domination number of a graph G is then defined to be the minimum weight of a k-rainbow dominating function. In this work, we prove sharp upper bounds on the k-rainbow domination number for all values of k. Furthermore, we also consider the problem with minimum degree restrictions on the graph.

DOI： 10.1007/s00373-013-1394-9

Web of Science

J-GLOBAL

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

In this paper we study a generalization of both proper edge-coloring and strong edge-coloring: k-intersection edge-coloring, introduced by Muthu, Narayanan and Subramanian [18]. In this coloring, the set S(v) of colors used by edges incident to a vertex v does not intersect S(u) on more than k colors when u and v are adjacent. We provide some sharp upper and lower bounds for x'(k-int) for several classes of graphs. For l-degenerate graphs we prove that x'(k-int)(G) <= (l + 1)Delta - l(k - 1) - 1. We improve this bound for subcubic graphs by showing that X'(2-int)(G) <= 6. We show that calculating X'(k-int) (K-n) for arbitrary values of k and n is related to some problems in combinatorial set theory and we provide bounds that are tight for infinitely many values of n. Furthermore, for complete bipartite graphs we prove that X'(k-int) (K-n,K-m) = [mn/k]. Finally, we show that computing X'(k-int) (G) is NP-complete for every k >= 1.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics22.html#journals/combinatorics/BorozanCCFNNV15

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let G and H be graphs with the same number of vertices. We introduce a graph puzzle (G, H) in which G is a board graph and the set of vertices of H is the set of pebbles. A configuration of H on G is defined as a bijection from the set of vertices of G to that of H. A move of pebbles is defined as exchanging two pebbles which are adjacent on both G and H. For a pair of configurations f and g, we say that g is equivalent to f if f can be transformed into g by a sequence of finite moves. If G is a 4 x 4 grid graph and H is a star, then the puzzle (G, H) corresponds to the well-known 15-puzzle. A puzzle (G, H) is called feasible if all the configurations of H on G are mutually equivalent. In this paper, we study the feasibility of the puzzle under various conditions. Among other results, for the case where one of the two graphs G and H is a cycle, a necessary and sufficient condition for the feasibility of the puzzle (G, H) is shown. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.03.009

Web of Science

J-GLOBAL

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

For r >= 2, a >= r- 1 and k >= 1, let c(r,, a, k) be the smallest integer c such that the vertex set of any non-trivial r-uniform k-edge-colored hypergraph 9-1 with = a can be covered by c monochromatic connected components. Here a(9-1) is the maximum cardinality of a subset A of vertices in 9-1 such that A does not contain any edges. An old conjecture of Ryser is equivalent to c(2, k) = a(r 1) and a recent result of Z. Kiraly states that c(r,, r-1, k) = [k/r] for any r >= 3. Here we make the first step to treat non-complete hypergraphs, showing that c(r,, r, r) = 2 for r >= 2 and c(r,, r, r+1) = 3 for r >= 3.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics21.html#journals/combinatorics/FujitaFGT14

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.aam.2013.12.001

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

For k >= 1, r >= 1 and n >= 1, let t*(k, r; n) be the minimum value satisfying that gamma(rk)(G) <= t*(k, r; n) center dot n for any connected graph G of order n with radius r; if no such graph exists, we set t*(k, r; n) = infinity. For k >= land r >= 1, let t*(k, r) = lim sup(n ->infinity) t*(k, r; n). In this paper, we investigate the behavior of the function t*(k, r) and determine some exact values of t*(k, r) when k or r is small. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.10.020

Web of Science

J-GLOBAL

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD  

It was proved by Mader that, for every integer!, every k-connected graph of sufficiently large order contains a vertex set X of order precisely l such that G - X is (k - 2)-connected. This is no longer true if we require X to be connected, even for l = 3.
Motivated by this fact, we are trying to find an "obstruction" for k-connected graphs without such a connected subgraph. It turns Out that the obstruction is an essentially 3-connected subgraph W such that G - W is still highly connected. More precisely, our main result says the following.
For k >= 7 and every k-connected graph G, either there exists a connected subgraph W of order 4 in G such that G - W is (k - 2)-connected, or else G contains an "essentially" 3-connected subgraph W, i.e., a subdivision of a 3-connected graph, such that G W is still highly connected-actually, (k - 6)-connected.
This result can be compared to Mader's result (Mader, 2002) [5] which says that every k-connected graph G of sufficiently large order (k >= 4) has a connected subgraph H of order exactly 4 such that G - H is (k - 3)-connected. (C) 2013 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.ejc.2013.06.014

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：WILEY-BLACKWELL  

Gallai-colorings of complete graphsedge colorings such that no triangle is colored with three distinct colorsoccur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai-colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. We show that such graphs F are very close to bipartite graphs, namely, they can be made bipartite by the removal of at most one edge. We also extend Gallai's property for two infinite families and show that it also holds when F is a path with at most six vertices.

DOI： 10.1002/jgt.21694

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：CAMBRIDGE UNIV PRESS  

Let H be a set of connected graphs. A graph G is said to be H-free if G does not contain any element of H as an induced subgraph. Let F-k(H) be the set of k-connected H-free graphs. When we study the relationship between forbidden subgraphs and a certain graph property, we often allow a finite exceptional set of graphs. But if the symmetric difference of F-k(H-1) and F-k(H-2) is finite and we allow a finite number of exceptions, no graph property can distinguish them. Motivated by this observation, we study when we obtain a finite symmetric difference. In this paper, our main aim is the following. If vertical bar H vertical bar <= 3 and the symmetric difference of F-1({H}) and F-1(H) is finite, then either H is an element of H or vertical bar H vertical bar = 3 and H = C-3. Furthermore, we prove that if the symmetric difference of F-k({H-1}) and F-k({H-2}) is finite, then H-1 = H-2.

DOI： 10.1017/S0963548313000254

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let c, m, n be integers with n >= c >= 3, and let G be a graph of order n with m edges. A classical theorem by Eras and Gallai states that if m > (c - 1)(n - 1)/2, then G contains a cycle of order at least c. In fact, the bound on m in this theorem is not sharp when both n and c are even. In this work we give the sharp value for this case. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ipl.2013.05.015

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：UNIV BELGRADE, FAC ELECTRICAL ENGINEERING  

The inverse degree r(G) of a finite graph G = (V, E) is defined as r(G) = Sigma(nu is an element of V) 1/d(nu), where d(nu) is the degree of vertex nu. In Discrete Math., 310 (2010), 940 946, MUKWEMBI posed the following conjecture: Let C be a connected chemical graph with diameter diam(G) and inverse degree r(G). Then diam(G) <= 12/5r(G) + O(1). In this paper, we settle the conjecture affirmatively.

DOI： 10.2298/AADM121129022C

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let n, k be integers with n >= k >= 2, and let G be a graph of order n and S be a subset of V(G). We define mu(S) := min{max{d(G)(x), d(G)(y)} { x, y is an element of S, x not equal y, xy is not an element of E(G)} if there exist two nonadjacent vertices in S; otherwise mu(S) := +infinity.
Fujita [S. Fujita, Degree conditions for the partition of a graph into cycles, edges and isolated vertices, Discrete Math. 309 (2009) 3534-3540] proved that if mu(V(G)) >= (n - k + 1)/2, then G contains k vertex-disjoint subgraphs H-1,..., H-k such that boolean OR(k)(i=1) V(H-i) = V(G) and each H-i is a cycle or K-2 or K-1 unless G is an exceptional graph. In this paper, we generalize this result as follows: if mu(S) >= (n - k + 1)/2, then G contains k vertex-disjoint subgraphs H-1,..., H-k such that S subset of boolean OR(k)(i=1) V(H-i) and each H-i is a cycle or K-2 or K-1 unless G is an exceptional graph. (C) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2012.10.010

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

A 2-rainbow dominating function f of a graph G is a function f:V(G)→21,2r such that, for each vertex vV(G) with f(v)=Combining long solidus overlay, uNG(v)f(u)=1,2r. The minimum of ∼vV(G)f(v) over all such functions is called the 2-rainbow domination number γr2(G). A Roman dominating function g of a graph G, is a function g:V(G)→0,1,2r such that, for each vertex vV(G) with g(v)=0, v is adjacent to a vertex u with g(u)=2. The minimum of ∼vV(G)g(v) over all such functions is called the Roman domination number γR(G). Regarding Combining long solidus overlay as 0, these two dominating functions have a common property that the same three integers are used and a vertex having 0 must be adjacent to a vertex having 2. Motivated by this similarity, we study the relationship between γR(G) and γr2(G). We also give some sharp upper bounds on these dominating functions. Moreover, one of our results tells us the following general property in connected graphs: any connected graph G of order n≥3 contains a bipartite subgraph H=(A,B) such that δ(H)≥1 and A-B≥n/5. The bound on A-B is best possible. © 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2012.10.017

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪ · · · ∪ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G) was introduced by Fujita and Nakamigawa in 2008. They conjectured that f(G) ≤ ⌊n 2 ⌋ + 1 if G is a 2-connected graph on n vertices. In this paper, we shall prove two partial results, in the cases when G is a subdivided K4, and a 2-connected series-parallel graph.

DOI： 10.7151/dmgt.1666

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

We consider a forbidden rainbow structure condition which implies that an edge colored complete graph has an almost spanning monochromatic subgraph with high connectivity. Namely, we classify the connected graphs G that satisfy the following statement: If n >> m >> k are integers, then any rainbow G-free coloring of the edges of K-n using m colors contains a monochromatic k-connected subgraph of order at least n - f(G, k, m), where f does not depend on n.

DOI： 10.1137/120896906

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

An edge-colored graph G is k-proper connected if every pair of vertices is connected by k internally pairwise vertex-disjoint proper colored paths. The k-proper connection number of a connected graph G, denoted by Pc-k(G), is the smallest number of colors that are needed to color the edges of G in order to make it k-proper connected. In this paper we prove several upper bounds for pc(k)(G). We state some conjectures for general and bipartite graphs, and we prove them for the case when k = 1. In particular, we prove a variety of conditions on G which imply pc(1) (G) = 2. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2011.09.003

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：WILEY-BLACKWELL  

Consider the graph consisting of a triangle with a pendant edge. We describe the structure of rainbow -free edge colorings of a complete graph and provide some corresponding GallaiRamsey results. In particular, we extend a result of Gallai to find a partition of the vertices of a rainbow -free colored complete graph with a limited number of colors between the parts. We also extend some GallaiRamsey results of Chung and Graham, Faudree et al. and Gyarfas et al. Copyright (c) 2011 Wiley Periodicals, Inc. J Graph Theory

DOI： 10.1002/jgt.20622

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

We show that two results on covering of edge colored graphs by monochromatic connected parts can be extended to partitioning. We prove that for any 2-edge-colored non-trivial r-uniform hypergraph H, the vertex set can be partitioned into at most alpha(H) - r + 2 monochromatic connected parts, where alpha(H) is the maximum size of a set of vertices that does not contain any edge. In particular, any 2-edge-colored graph G can be partitioned into alpha(G) monochromatic connected parts, where alpha(G) denotes the independence number of G. This extends Konig's theorem, a special case of Ryser's conjecture.
Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without 3-edge-colored triangles. We show that for any Gallai-coloring of a graph G, the vertex set of G can be partitioned into monochromatic connected parts, where the number of parts depends only on alpha(G). This extends its cover-version proved earlier by Simonyi and two of the authors.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics19.html#journals/combinatorics/FujitaFGT12

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD  

Let r, n and n(1), ... , n(r) be positive integers with n = n(1) + ... + n(r). Let X be a connected graph with n vertices. For 1 <= i <= r, let P-i be the i-th color class of n(i) distinct pebbles. A configuration of the set of pebbles P = P-1 boolean OR ... boolean OR P-r on X is defined as a bijection from the set of vertices of X to P. A move of pebbles is defined as exchanging two pebbles with distinct colors on the two endvertices of a common edge. For a pair of configurations f and g, we write f similar to g if f can be transformed into g by a sequence of finite moves. The relation similar to is an equivalence relation on the set of all the configurations of P on X. We study the number c(X, n(1), ... , n(r)) of the equivalence classes. A tuple (X, n(1), ... , n(r)) is called transitive if for any configuration f and for any vertex u, a pebble f (u) can be moved to any other vertex by a sequence of finite moves. We determine c(X, n(1), ... , n(r)) for an arbitrary transitive tuple (X, n(1), ... , n(r)). (C) 2011 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.ejc.2011.09.019

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A k-rainbow dominating function of a graph is a function f from the vertices V(G) to 2(vertical bar k vertical bar) such that, for all nu is an element of V (G), either f (nu) not equal phi or boolean OR(u is an element of N vertical bar nu vertical bar) f (u) = {1, ... ,k}. The k-rainbow domatic number d(rk)(G) is the maximum integer d such that there exists a set of k-rainbow dominating functions f(1,) f(2), ..., f(d) with Sigma(d)(i=1) vertical bar f(i)(nu)vertical bar <= k for all nu is an element of V (G). We study the k-rainbow domatic number by finding this number for some classes of graphs and improving upon some known general bounds. (C) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2012.01.010

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

Let F, G be families of graphs. The generalized Ramsey number r(F, G) denotes the smallest value of n for which every red-blue coloring of K-n yields a red F is an element of F or a blue G is an element of G. Let F(k) be a family of graphs with k vertex-disjoint cycles.
In this paper, we deal with the case where F = F(3), G = {K-t} for some fixed t with t >= 2, and prove that r(F(3), G) = 2t + 5.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics19.html#journals/combinatorics/Fujita12

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A graph G is said to be bicritical if the removal of any pair of vertices decreases the domination number of G. For a bicritical graph G with the domination number t, we say that G is t-bicritical. Let lambda(G) denote the edge-connectivity of G. In [2], Brigham et al. (2005) posed the following question: If G is a connected bicritical graph, is it true that lambda(G) >= 3?
In this paper, we give a negative answer toward this question; namely, we give a construction of infinitely many connected t-bicritical graphs with edge-connectivity 2 for every integer t >= 5. Furthermore, we give some sufficient conditions for a connected 5-bicritical graph to have lambda(G) >= 3. (c) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2011.03.012

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

An edge of a 6-connected graph is said to be removable (resp. contractible) if the removal (resp. contraction) of the edge results in a 6-connected graph. A 6-connected graph is said to be minimally contraction-critically 6-connected if it has neither removable edge nor contractible edge. Let x be a vertex of a minimally contraction-critically 6-connected graph G. In this paper, we show that there is one of some specified configurations around x and using this result we prove that x has a neighbor of degree 6. We also display a condition for x to have at least two neighbors of degree 6. (C) 2011 Published by Elsevier B.V.

DOI： 10.1016/j.disc.2011.06.012

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

An edge-colouring of a graph G is rainbow k-connected if, for any two vertices of G, there are k internally vertex-disjoint paths joining them, each of which is rainbow (i.e., all edges of each path have distinct colours). The minimum number of colours for which there exists a rainbow k-connected colouring for G is the rainbow k-connection number of G, and is denoted by rck(G). The function rck(G) was introduced by Chartrand et al. in 2008, and has since attracted considerable interest. In this note, we shall consider the function rck(G) for complete bipartite and multipartite graphs, highly connected graphs, and random graphs. © 2011 Elsevier B.V.

DOI： 10.1016/j.endm.2011.09.059

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

It was proved by Mader that, for every integer l, every k-connected graph of sufficiently large order contains a vertex set X of order precisely l such that G-X is (k-2)-connected. This is no longer true if we require X to be connected, even for l=3. Motivated by this fact, we are trying to find an "obstruction" for k-connected graphs without such a connected subgraph. It turns out that the obstruction is an essentially 3-connected subgraph W such that G-W is still highly connected. More precisely, our main result says the following.For k≥. 7 and every k-connected graph G, either there exists a connected subgraph W of order 4 in G such that G-W is (k-2)-connected, or else G contains an "essentially" 3-connected subgraph W, i.e., a subdivision of a 3-connected graph, such that G-W is still highly connected, actually, (k-6)-connected.This result can be compared to Mader's result which says that every k-connected graph G of sufficiently large order (k≥. 4) has a connected subgraph H of order exactly four such that G-H is (k-3)-connected. © 2011 Elsevier B.V.

DOI： 10.1016/j.endm.2011.09.058

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

Sumner [7] proved that every connected K (1,3)-free graph of even order has a perfect matching. He also considered graphs of higher connectivity and proved that if m >= 2, every m-connected K (1,m+1)-free graph of even order has a perfect matching. In [6], two of the present authors obtained a converse of sorts to Sumner's result by asking what single graph one can forbid to force the existence of a perfect matching in an m-connected graph of even order and proved that a star is the only possibility. In [2], Fujita et al. extended this work by considering pairs of forbidden subgraphs which force the existence of a perfect matching in a connected graph of even order. But they did not settle the same problem for graphs of higher connectivity. In this paper, we give an answer to this problem. Together with the result in [2], a complete characterization of the pairs is given.

DOI： 10.1007/s00493-011-2655-y

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

In an edge-colored graph, let d(c) (upsilon) be the number of colors on the edges incident to upsilon and let delta(c) (G) be the minimum d(c) (upsilon) over all vertices upsilon is an element of G. In this work, we consider sharp conditions on delta(c) (G) which imply the existence of properly edge-colored paths and cycles, meaning no two consecutive edges have the same color. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2011.06.005

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

We show that, in a k-connected graph G of order n with alpha(G) = alpha, between any pair of vertices, there exists a path P joining them with vertical bar P vertical bar >= min{n, (k-1)(n-k)/alpha + K}. This implies that, for any edge e is an element of E(G), there is a cycle containing e of length at least min{n, (k-1)(n-k)/alpha +k}. Moreover, we generalize our result as follows: for any choice S of s <= k vertices in G, there exists a tree T whose set of leaves is S with vertical bar T vertical bar >= min{n, (k-s+1)(n-k)/alpha +k}.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics18.html#journals/combinatorics/FujitaHM11

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a theta-graph to be a pair of vertices u, v with three internally disjoint paths joining u to v. Given an independence number alpha and a fixed integer k, the results contained in this paper provide sharp bounds on the order f(k, alpha) of a graph with independence number alpha(G) <= alpha which contains no k disjoint theta-graphs. Since every theta-graph contains an even cycle, these results provide k disjoint even cycles in graphs of order atleast f(k, alpha)+1. We also discuss the relation ship between this problem and a generalized ramsey problem involving sets of graphs.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics18.html#journals/combinatorics/FujitaM11a

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

For given graphs G and H and an integer k, the Gallai-Ramsey number is defined to be the minimum integer n such that, in any k coloring of the edges of K(n), there exists a subgraph isomorphic to either a rainbow coloring of G or a monochromatic coloring of H. In this work, we consider Gallai-Ramsey numbers for the case when G = K(3) and H is a cycle of a fixed length. (C) 2009 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2009.11.004

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

In [On the circumference of a graph and its complement, Discrete Math. 309 (2009), 5891-5893], Faudree et al. conjectured that when r >= 3, every r-edge-colored complete graph K, contains a monochromatic cycle of length at least n/(r - 1). We disprove this conjecture for small it and give a short proof of the following weaker but more generalized form: for r >= 1, every r-edge-colored complete graph K(n) contains a monochromatic cycle of length at least n/r. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2011.01.016

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

In this note, we improve upon some recent results concerning the existence of large monochromatic, highly connected subgraphs in a 2-coloring of a complete graph. In particular, we show that if n >= 6.5(k - 1), then in any 2-coloring of the edges of K(n), there exists a monochromatic k-connected subgraph of order at least n - 2(k - 1). Our result improves upon several recent results by a variety of authors.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics18.html#journals/combinatorics/FujitaM11

Language：English   Publishing type：Research paper (scientific journal)   Publisher：BIRKHAUSER VERLAG AG  

We prove that if G is k-connected (with k >= 2), then G contains either a cycle of length 4 or a connected subgraph of order 3 whose contraction results in a k-connected graph. This immediately implies that any k-connected graph has either a cycle of length 4 or a connected subgraph of order 3 whose deletion results in a (k-1)-connected graph.

DOI： 10.1007/s00026-011-0070-0

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER TOKYO  

We prove that if G is highly connected, then either G contains a non-separating connected subgraph of order three or else G contains a small obstruction for the above conclusion. More precisely, we prove that if G is k-connected (with k >= 2), then G contains either a connected subgraph of order three whose contraction results in a k-connected graph (i.e., keeps the connectivity) or a subdivision of K(4)(-) whose order is at most 6.

DOI： 10.1007/s00373-010-0930-0

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER TOKYO  

Let r and s be nonnegative integers, and let G be a graph of order at least 3r + 4s. In Bialostocki et al. (Discrete Math 308: 5886-5890, 2008), conjectured that if the minimum degree of G is at least 2r + 3s, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles, and they showed that the conjecture is true for r = 0, s = 2 and for s = 1. In this paper, we settle this conjecture completely by proving the following stronger statement; if the minimum degree sum of two nonadjacent vertices is at least 4r + 6s - 1, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles.

DOI： 10.1007/s00373-010-0901-5

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER JAPAN KK  

In this work, we collect Ramsey-type results concerning rainbow edge colorings of graphs.

DOI： 10.1007/s00373-010-0891-3

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SIAM PUBLICATIONS  

The balanced decomposition number f(G) of a graph G was introduced by Fujita and Nakamigawa [Discr. Appl. Math., 156 (2008), pp. 3339-3344]. A balanced coloring of a graph G is a coloring of some of the vertices of G with two colors, such that there is the same number of vertices in each color. Then, f(G) is the minimum integer s with the following property: For any balanced coloring of G, there is a partition V (G) = V-1 (boolean OR) over dot...(boolean OR) over dot V-r such that, for every i, Vi induces a connected subgraph, vertical bar V-i vertical bar <= s, and V-i contains the same number of colored vertices in each color. Fujita and Nakamigawa studied the function f(G) for many basic families of graphs, and demonstrated some applications. In this paper, we shall continue the study of the function f(G). We give a characterization for noncomplete graphs G of order n which are [n/2]-connected, in view of the balanced decomposition number. We shall prove that a necessary and sufficient condition for such [n/2]-connected graphs G is f(G) = 3. We shall also determine f(G) when G is a complete multipartite graph, and when G is a generalized circle minus-graph (i.e., a graph which is a subdivision of a multiple edge). Some applications will also be discussed. Further results about the balanced decomposition number also appear in two subsequent papers by Fujita and Liu.

DOI： 10.1137/090780894

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

We prove that every k-connected graph (k >= 5) has an even cycle C such that G - V(C) is still (k - 4)-connected. The connectivity bound is best possible.
In addition, we prove that every k-connected triangle-free graph (k >= 5) has an even cycle C such that G - V(C) is still (k - 3)-connected. The same conclusion also holds for any k-connected graph (k >= 5) that does not contain a K(4)(-), i.e., K(4) minus one edge.
The first theorem is an analogue of the well-known result (without the parity condition) by Thomassen [9]. It is also a counterpart of the conjecture made by Thomassen [10] which says that there exists a function f(k) such that every f(k)-connected non-bipartite graph has an odd cycle C such that G - V(C) is still k-connected.
The second theorem is an analogue of the results (without the parity condition) by Egawa [2] and Kawarabayashi [3], respectively.

DOI： 10.1007/s00493-010-2482-6

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

We generalize the well-known theorem of Corrádi and Hajnal which says that if a given graph G has at least 3k vertices and the minimum degree of G is at least 2k, then G contains k vertex-disjoint cycles. Our main result is the following
for any integer k, there is an absolute constant ck satisfying the following
let G be a graph with at least ck vertices such that the minimum degree of G is at least 2k. Then either (i) G contains k vertex-disjoint even cycles, or (ii) (2 k - 1) K1 + p K2 ⊆ G ⊆ K2 k - 1 + p K2 (p ≥ k ≥ 2), or k = 1 and each block in G is either a K2 or a odd cycle, especially, each endblock in G is a odd cycle. In fact, our proof implies the following
the "even cycles" in the conclusion (i) can be replaced by "theta graphs", where a theta graph is a graph that has two vertices x, y such that there are three disjoint paths between x and y. Let us observe that if there is a theta graph, then there is an even cycle in it. Furthermore, if the conclusion (ii) holds, clearly there are no k vertex-disjoint even cycles (and hence no k vertex-disjoint theta graphs). © 2009 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.endm.2009.07.019

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Let r, n and n1, ..., nr be positive integers with n = n1 + ⋯ + nr. Let X be a connected graph with n vertices. For 1 ≤ i ≤ r, let Pi be the ith color class of ni distinct pebbles. A configuration of the set of pebbles P = P1 ∪ ⋯ ∪ Pr on X is defined as a bijection from the set of vertices of X to P. A move of pebbles is defined as exchanging two pebbles with mutually distinct colors on the two endvertices of a common edge. For a pair of configurations f and g, we write f ∼ g if f can be transformed into g by a sequence of finite moves. The relation ∼ is an equivalence relation on the set of all the configurations of P on X. We study the number c (X, n1, ..., nr) of the equivalence classes. © 2009 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.endm.2009.07.031

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let k, n be integers with 2 <= k <= n, and let G be a graph of order n. We prove that if max{d(G)(x), d(G)(y)} >= (n - k + 1)/2 for any x, y is an element of V(G) with x not equal y and xy is not an element of E(G), then G has k vertex-disjoint subgraphs H(1) ..... H(k) such that V(H(1))boolean OR...boolean OR V(H(k)) = V(G) and H(i) is a cycle or K(1) or K(2) for each 1 <= i <= k, unless k = 2 and G = C(5), or k = 3 and G = K(1) boolean OR C(5). (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2007.12.056

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELECTRONIC JOURNAL OF COMBINATORICS  

An r-edge-coloring of a graph is an assignment of r colors to the edges of the graph. An exactly r-edge-coloring of a graph is an r-edge-coloring of the graph that uses all r colors. A matching of an edge-colored graph is called rainbow matching, if no two edges have the same color in the matching. In this paper, we prove that an exactly r-edge-colored complete graph of order n has a rainbow matching of size k(>= 2) if r >= max{(2k-3 2) + 2, (k-2 2) + (k-2)(n-k + 2) +2}, k >= 2, and n >= 2k + 1. The bound on r is best possible.

Web of Science

researchmap

Other Link： http://dblp.uni-trier.de/db/journals/combinatorics/combinatorics16.html#journals/combinatorics/FujitaKSS09

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k >= 4), there is an induced cycle C such that G - V(C) is (k - 3)-connected and G - E(C) is (k - 2)-connected. Both "(k - 3) -connected" and "(k - 2)-connected" are best possible in a sense. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2008.06.012

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let k be a positive integer. It is shown that if G is a graph of order 4k with minimum degree at least 2k, then G contains k vertex-disjoint copies of K-1.3, Unless G is isomorphic to K-2k,K-2k with k being odd. (C) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2007.11.013

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A balanced vertex-coloring of a graph G is a function c from V(G) to {-1, 0, 1} Such that Sigma{c(v) : v is an element of V(G)} = 0. A Subset U of V(G) is called a balanced set if U induces a connected subgraph and Sigma{c(v) : v is an element of U} = 0. A decomposition V(G) = V(l) boolean OR ... boolean OR V(r) is called a balanced decomposition if V(i) is a balanced set for l <= i <= r.
In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G) = V(l) boolean OR ... boolean OR V(r) with vertical bar V(i)vertical bar <= s for l <= i <= r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied. (C) 2008 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2008.01.006

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS INC ELSEVIER SCIENCE  

The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that G - v is still k-connected. In this paper, we consider a generalization of the above result [G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63-68]. We prove the following result:
Suppose G is a k-connected graph with minimum degree at least [3k/2] + 2. Then G has an edge e such that G - V(e) is still k-connected.
The bound on the minimum degree is essentially best possible. (c) 2007 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.jctb.2007.11.001

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：JOHN WILEY & SONS INC  

In [15], Thomassen proved that any triangle-free k-connected graph has a contractible edge. Starting with this result, there are several results concerning the existence of contractible elements in k-connected graphs which do not contain specified subgraphs. These results extend Thomassen's result, cf., [2,3,9-12]. In particular, Kawarabayashi [12] proved that any k-connected graph without K-4(-) subgraphs contains either a contractible edge or a contractible triangle.
In this article, we further extend these results, and prove the following result.
Let k be an integer with k >= 6. If G is a k-connected graph such that G does not contain D-1 = K-1 + (K-2 boolean OR P-3) as a subgraph and G does not contain D-2 = K-2 + (k - 2)K-1 as an induced subgraph, then G has either a contractible edge which is not contained in any triangle or a contractible triangle. (C) 2008 Wiley Periodicals, Inc.

DOI： 10.1002/jgt.20297

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A graph G is said to be claw-free if G does not contain an induced subgraph isomorphic to K-1,K-3. Let k be an integer with k >= 2. We prove that if G is a claw-free graph of order at least 7k - 6 and with minimum degree at least 3, then G contains k vertex-disjoint copies of K-1 + (K-1 boolean OR K-2). (c) 2007 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2006.07.043

Web of Science

researchmap

Language：English  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

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.

DOI： 10.1016/j.disc.2007.03.008

Web of Science

researchmap

Language：English   Publisher：広島大学  

Let $r,k$ be integers with $r\ge 3, k\ge 2$. We prove that if $G$ is a $K_{1,r}$-free graph of order at least $(k- 1)(2r-1)+1$ with $\delta(G)\ge 2$, then $G$ contains $k$ vertex-disjoint copies of $K_{1,2}$. This result is motivated by the problem of characterizing a forbidden subgraph $H$ which satisfies the statement ``every $H$-free graph of sufficiently large order with minimum degree at least $t$ contains $k$ vertex-disjoint copies of a star $K_{1,t}$." In this paper, we also give the answer to this problem.

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS INC ELSEVIER SCIENCE  

In this paper, we study the relationship between forbidden subgraphs and the existence of a matching. Let W be a set of connected graphs. each of which has three or more vertices. A graph G is said to be H-free if no graph in W is ail induced subgraph of G. We completely characterize the set H such that every connected H-free graph of sufficiently large even order has a perfect matching in the following cases.
(1) Every graph in R is triangle-free.
(2) H consists of two graphs (i.e. a pair of forbidden subgraphs).
A matching M in a graph of odd order is said to be a near-perfect matching if every vertex of G but one is incident with an edge of M. We also characterize H such that every H-free graph of sufficiently large odd order has a near-perfect matching in the above cases. (C) 2005 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.jctb.2005.08.002

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let n, h be integers with n >= 6 and h >= 7. We prove that if G is a graph of order n with sigma(2)(G)>= h, then G contains two disjoint cycles C-1 and C-2 such that vertical bar V(C-1)vertical bar + vertical bar V(C-2)vertical bar >= min{h, n}. (c) 2005 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2005.10.017

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Recent progresses on degree conditions and vertex-disjoint cycles in graphs will be reviewed. © 2005 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.endm.2005.06.067

Scopus

researchmap

DOI： 10.7151/dmgt.1280

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：CHARLES BABBAGE RES CTR  

Let 6(G) denote the minimum degree of a graph G. We prove that for t greater than or equal to 4 and k greater than or equal to 2, a graph G of order at least (t + 1)k + 2t(2) - 4t + 2 with delta(G) greater than or equal to k + t - 1 contains k pairwise vertex-disjoint K-1,K-t's.

Web of Science

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

researchmap