Search

Gyárfás and Sumner independently conjectured that for every tree T $T$, there exists a function f T : N → N ${f}_{T}:{\mathbb{N}}\to {\mathbb{N}}$ such that every T $T$‐free graph G $G$ satisfies χ( G ) ≤ f T(ω( G ) ) $\chi (G)\le {f}_{T}(\omega (G))$, where χ( G ) $\chi (G)$ and ω( G ) $\omega (G)$ are the chromatic number and the clique number of G $G$, respectively. This conjecture gives a solution of a Ramsey‐type problem on the chromatic number. For a graph G $G$, the induced SP‐cover number inspc( G ) $\text{inspc}(G)$ (resp. the induced SP‐partition number inspp( G ) $\text{inspp}(G)$) of G $G$ is the minimum cardinality of a family P ${\mathscr{P}}$ of induced subgraphs of G $G$ such that each element of P ${\mathscr{P}}$ is a star or a path and ⋃P ∈ P V( P ) = V( G ) ${\bigcup }_{P\in {\mathscr{P}}}V(P)=V(G)$ (resp. ⋃ ˙P ∈ P V( P ) = V( G ) ${\dot{\bigcup }}_{P\in {\mathscr{P}}}V(P)=V(G)$). Such two invariants are directly related concepts to the chromatic number. From the viewpoint of this fact, we focus on Ramsey‐type problems for two invariants inspc $\text{inspc}$ and inspp $\text{inspp}$, which are analogies of the Gyárfás‐Sumner conjecture, and settle them. As a corollary of our results, we also settle other Ramsey‐type problems for widely studied invariants. [ABSTRACT FROM AUTHOR]

Among some results, we prove the following two theorems. (i) Let G be a connected claw-free graph. We arbitrarily color every vertex of G red or blue so that the number of red vertices is even. Then G has vertex-disjoint paths whose end-vertices are exactly the same as the red vertices of G. (ii) Let G be a 3-edge connected claw-free cubic graph. We arbitrarily color every vertex of G red or blue so that the number of red vertices is even and the distance between any two red vertices is at least 3. Then G has a factor F such that deg F (x) = 1 for every red vertex x and deg F (y) = 2 for every blue vertex y. [ABSTRACT FROM AUTHOR]

Lately, Matsumoto and Nakamigawa introduced a game invariant concerning the edge-connectivity of graphs, called the game edge-connectivity (Matsumoto and Nakamigawa, 2021). To define the invariant, they introduced a combinatorial game where the first player deletes one edge and the second one contracts (or protects) one edge. In this paper, considering a natural variation of the game in which the second player also deletes an element instead of protecting one, we introduce an alternative game invariant, called the fair game edge-connectivity of graphs. By showing that the fair game edge-connectivity of every 2-edge-connected graph G is equal to 2 λ (G) − 1 except some graphs, where λ (G) denotes the edge-connectivity of G , we could completely determine the fair game edge-connectivity of all graphs. [ABSTRACT FROM AUTHOR]

In this paper, we prove that for positive integers a , b , c , r and s with a ≤ r / 2 ≤ b ≤ r , s / 2 − 1 ≤ c ≤ s / 2 and a s ≥ (b − 1) c , every bipartite graph G with bipartition (X , Y) such that deg G (x) = r for all x ∈ X and deg G (y) = s for all y ∈ Y has a factor F satisfying deg F (x) ∈ { a , b } for x ∈ X and deg F (y) ∈ { c , c + 1 } for y ∈ Y. [ABSTRACT FROM AUTHOR]

For a family H of graphs, a graph G is said to be H -free if G contains no member of H as an induced subgraph. We let G ̃ 3 (H) denote the family of connected H -free graphs having minimum degree at least 3. In this paper, we characterize the families H of connected graphs with | H | = 3 such that G ̃ 3 (H) is a finite family, except for the case where { K 3 , K 2 , 2 } ⊆ H. Our results give a fast algorithm determining the chromatic number of several classes of graphs with a forbidden subgraph condition imposed on. [ABSTRACT FROM AUTHOR]

In this paper, we give a characterization or a property for trees T such that a component of T − e is a specific path for each edge e of T , and as corollaries of them, we obtain upper bounds on some domination-type invariants. We demonstrate how our results can be used by taking a recent result, and give a sharp upper bound on the c -self domination number which was recently defined as a generalization of some well-studied invariants. [ABSTRACT FROM AUTHOR]

• Let Γ be (di)graph. A family P of sub(di)graphs of Γ is called a path cover (resp. a path partition) of Γ if ∪ p ϵ P V (P) = V (Γ) (resp. ∪ p ϵ P V (P) = V (Γ)) and every element of P is a path or a directed path. The minimum cardinality of a path cover (resp. a path partition) of Γ is denoted by pc(Γ) (resp. pp(Γ)). • The authors recently gave Ramsey-type results for the path cover/partition number of graphs. • We continue the research about them focusing on digraphs, and find a relationship between the path cover/partition number and forbidden structures in digraphs. • In this paper, we find forbidden structure conditions assuring us that pc(D) (or pp(D)) is bounded by a constant for every weakly connected digraph D. Recently, the authors [Electron. J. Combin. 29 (2022), Paper No. 4.8] gave Ramsey-type results for the path cover/partition number of graphs. In this paper, we continue the research about them focusing on digraphs, and find a relationship between the path cover/partition number and forbidden structures in digraphs. Let D be a weakly connected digraph. A family P of subdigraphs of D is called a path cover (resp. a path partition) of D if ⋃ P ∈ P V (P) = V (D) (resp. ⋃ ˙ P ∈ P V (P) = V (D)) and every element of P is a directed path. The minimum cardinality of a path cover (resp. a path partition) of D is denoted by pc (D) (resp. pp (D)). In this paper, we find forbidden structure conditions assuring us that pc (D) (or pp (D)) is bounded by a constant. [ABSTRACT FROM AUTHOR]

A subgraph of a graph is a homeomorphically irreducible tree (HIT) if it is a tree with no vertices of degree two. Furuya and Tsuchiya [Discrete Math. 313 (2013), pp. 2206–2212] proved that every connected P4‐free graph of order n≥5 has a HIT of order at least n−1, and Diemunsch et al [Discrete Appl. Math. 185 (2015), pp. 71–78] proved that every connected P5‐free graph of order n≥6 has a HIT of order at least n−2. In this paper, we continue the study of HITs in path‐free graphs and bring to a conclusion proving the following three results: (a) If a connected graph F satisfies the condition that every connected F‐free graph G has a HIT of order Ω(∣V(G)∣), then F is a path of order at most 7. (b) Every connected P6‐free graph of order n≥9 has a HIT of order at least (n+1)/2. (c) Every connected P7‐free graph of order n≥9 has a HIT of order at least (n+3)/3. Furthermore, we focus on a P6‐free graph having large minimum degree, and prove that for a connected P6‐free graph G of order n≥11, if δ(G)≥3, then G has a HIT of order greater than (δ(G)n/δ(G)+1)−1. [ABSTRACT FROM AUTHOR]

In this paper, we focus on a so-called Fan-type condition assuring us the existence of long paths in bipartite graphs. As a consequence of our main result, we completely determine the bipartite Ramsey numbers b (P s , B t 1 , t 2 ) , where B t 1 , t 2 is the graph obtained from a t 1 -star and a t 2 -star by joining their centers. [ABSTRACT FROM AUTHOR]

For two graphs A and B, a graph G is called { A , B } -free if G contains neither A nor B as an induced subgraph. Let P n denote the path of order n. For nonnegative integers k, ℓ and m, let N k , ℓ , m be the graph obtained from K 3 and three vertex-disjoint paths P k + 1 , P ℓ + 1 , P m + 1 by identifying each of the vertices of K 3 with one endvertex of one of the paths. Let Z k = N k , 0 , 0 and B k , ℓ = N k , ℓ , 0 . Bedrossian characterized all pairs { A , B } of connected graphs such that every 2-connected { A , B } -free graph is Hamiltonian. All pairs appearing in the characterization involve the claw ( K 1 , 3 ) and one of N 1 , 1 , 1 , P 6 and B 1 , 2 . In this paper, we characterize connected graphs that are (i) { K 1 , 3 , Z 2 } -free but not B 1 , 1 -free, (ii) { K 1 , 3 , B 1 , 1 } -free but not P 5 -free, or (iii) { K 1 , 3 , B 1 , 2 } -free but not P 6 -free. The third result is closely related to Bedrossian's characterization. Furthermore, we apply our characterizations to some forbidden pair problems. [ABSTRACT FROM AUTHOR]

Abstract A function f : V (G) → 2 [ k ] is an independent k -rainbow dominating function of a graph G if { x ∣ f (x) ≠ 0̸ } is an independent set of G and for every vertex x with f (x) = 0̸ , we have ⋃ y ∈ N G (x) f (y) = [ k ]. The independent k -rainbow domination number of G , denoted i r k (G) , is the minimum, over all independent k -rainbow dominating functions f , ∑ x ∈ V (G) | f (x) |. We provide sharp upper bounds on i r k (G) when G is a connected bipartite graph and when G is any graph. In both cases, we also classify those graphs that achieve the bounds. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we focus on a special chromatic invariant of graphs, so-called the locating chromatic number. We give a sharp upper bound of the locating chromatic number of trees by using the number of leaves. [ABSTRACT FROM AUTHOR]

Abstract Let G be a graph, and f : V (G) → N be a function. A subgraph H of G is an f -forest if H is a forest and d H (x) ≤ f (x) for all x ∈ V (H). In this paper, we give a degree-sum condition for the existence of a spanning f -forest of a graph. As a corollary of our result, for m ≤ k , we obtain degree-sum conditions for the existence of k -tree such that the degree of a specified vertex is at most m. [ABSTRACT FROM AUTHOR]

In this article, we are concerned with sufficient conditions for the existence of a {P2,P2k+1}‐factor. We prove that for k≥3, there exists εk>0 such that if a graph G satisfies ∑0≤j≤k−1c2j+1(G−X)≤εk|X| for all X⊆V(G), then G has a {P2,P2k+1}‐factor, where ci(G−X) is the number of components C of G−X with |V(C)|=i. On the other hand, we construct infinitely many graphs G having no {P2,P2k+1}‐factor such that ∑0≤j≤k−1c2j+1(G−X)≤32k+14172k−78|X| for all X⊆V(G). [ABSTRACT FROM AUTHOR]

The domination number of a graph G, denoted by γ(G), is the minimum cardinality of a dominating set of G. A vertex of a graph is called critical if its deletion decreases the domination number, and a graph is called critical if its all vertices are critical. A graph G is called weak bicritical if for every non-critical vertex x∈V(G), G-x is a critical graph with γ(G-x)=γ(G). Furuya (Australas. J. Comb. 62:184-196, 2015) proved that the diameter of a connected weak bicritical graph G is at most 2γ(G)-2. In this paper, we characterize the connected weak bicritical graphs G whose diameter is exactly 2γ(G)-2. This is a generalization of some known results concerning the diameter of graphs with a domination-criticality. [ABSTRACT FROM AUTHOR]

A spanning subgraph F of a graph G is called a { P 2 , C 2 i + 1 : i ≥ k } -factor if each component of F is isomorphic to either a path of order 2 or a cycle of order 2 i + 1 for some i ≥ k . In this paper, we obtain the following two results (here c i ( G − X ) is the number of components C of G − X with | V ( C ) | = i ): (i) If a graph G satisfies c 1 ( G − X ) + c 3 ( G − X ) ≤ 1 2 | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ 2 } -factor. (ii) For k ≥ 3 , if a graph G satisfies ∑ 0 ≤ j ≤ k − 1 c 2 j + 1 ( G − X ) ≤ 2 5 ( k 2 − 1 ) | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ k } -factor. [ABSTRACT FROM AUTHOR]

A fullerene graph is a 3-connected cubic plane graph whose all faces are bounded by 5- or 6-cycles. In this paper, we show that a matching M of a fullerene graph can be extended to a perfect matching if the following hold: (i) three faces around each vertex in $$\{x,y:xy\in M\}$$ are bounded by 6-cycles and (ii) the edges in M lie at distance at least 13 pairwise. [ABSTRACT FROM AUTHOR]

Let a and b be positive integers with a < b . In this paper, we obtain a neighborhood-union condition for the existence of a Hamiltonian [ a , b ] -factor showing the following result: For a Hamiltonian graph G of sufficiently large order n , if δ ( G ) ≥ a + 2 and | N G ( x ) ∪ N G ( y ) | ≥ a n a + b + 3 for any nonadjacent vertices x , y ∈ V ( G ) , then G has an [ a , b ] -factor avoiding a specified Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

A cycle C in a graph G is dominating if every edge of G is incident with at least one vertex of C. For a set $$\mathcal {H}$$ of connected graphs, a graph G is said to be $$\mathcal {H}$$ -free if G does not contain any member of $$\mathcal {H}$$ as an induced subgraph. When $$|\mathcal {H}| = 2, \mathcal {H}$$ is called a forbidden pair. In this paper, we investigate the characterization of the class of the forbidden pairs guaranteeing the existence of a dominating cycle and show the following two results: (i) Every 2-connected $$\{P_{5}, K_{4}^{-}\}$$ -free graph contains a longest cycle which is a dominating cycle. (ii) Every 2-connected $$\{P_{5}, W^{*}\}$$ -free graph contains a longest cycle which is a dominating cycle. Here $$P_{5}$$ is the path of order $$5, K_{4}^{-}$$ is the graph obtained from the complete graph of order 4 by removing one edge, and $$W^{*}$$ is the graph obtained from two triangles and an edge by identifying one vertex in each. [ABSTRACT FROM AUTHOR]

In Aldred and Plummer (Discrete Math 197/198 (1999) 29-40) proved that every m-connected [ABSTRACT FROM AUTHOR]

A cycle C in a graph G is called dominating if every edge of G is incident with a vertex of C . For a set H of connected graphs, a graph G is said to be H -free if G does not contain any member of H as an induced subgraph. When | H | = 2 , H is called a forbidden pair. In this paper, we investigate the set H of forbidden pairs H which satisfies that every 2-connected H -free graph has a dominating cycle. In particular, we show that H is a very small class and find some maximal forbidden pairs of H . [ABSTRACT FROM AUTHOR]

In this paper, we characterize connected $$\{K_{1,3},N(2,1,0)\}$$ -free but not $$N(1,1,1)$$ -free graphs. By combining our result and a theorem showed by Duffus et al. (every $$2$$ -connected $$\{K_{1,3},N(1,1,1)\}$$ -free graph is Hamiltonian), we give an alternative proof of Bedrossian's theorem (every $$2$$ -connected $$\{K_{1,3},N(2,1,0)\}$$ -free graph is Hamiltonian). [ABSTRACT FROM AUTHOR]

A semi-coloring is a fractional-type edge coloring of graphs. Daniely and Linial (J Graph Theory 69:426-440, ) conjectured that every graph has a semi-coloring. In this paper, we give an affirmative answer to this conjecture by considering a $$2$$ -factor in almost regular graphs. [ABSTRACT FROM AUTHOR]

For a graph G and a set H of connected graphs, G is said to be H -free if G does not contain any member of H as an induced subgraph. We let G 2 ( H ) denote the set of all 2-connected H -free graphs. Fujisawa et al. (2013) characterized sets H of connected graphs such that | H | ≤ 3 and G 2 ( H ) is finite. In this paper, we extend their result and characterize sets H of connected graphs such that | H | ≤ 4 and G 2 ( H ) is finite. [ABSTRACT FROM AUTHOR]

A k-rainbow dominating function of a graph G is a function f from the vertices V( G) to $${2^{\{1, 2, \dots, k\}}}$$ such that, for all $${v \in V(G)}$$ , either $${f(v) \neq \emptyset}$$ or $${\bigcup_{u \in N[v]} f(u) = \{1, 2, \dots, k\}}$$ . The k-rainbow domination number of a graph G is then defined to be the minimum weight $${w(f) = \sum_{v \in V(G)} |f(v)|}$$ 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. [ABSTRACT FROM AUTHOR]

A spanning tree with no vertices of degree two is called a homeomorphically irreducible spanning tree (or a HIST ) of a graph. In Furuya and Tsuchiya (2003), the sets of forbidden subgraphs that imply the existence of a HIST in a connected graph of sufficiently large order were characterized. In this paper, we focus on characterizing connected P 5 -free graphs which have a HIST. As applications of our main result, we also characterize forbidden pairs that imply the existence of a HIST. [ABSTRACT FROM AUTHOR]

For a graph G and a set $${\mathcal{F}}$$ of connected graphs, G is said be $${\mathcal{F}}$$ -free if G does not contain any member of $${\mathcal{F}}$$ as an induced subgraph. We let $${\mathcal{G} _{3}(\mathcal{F})}$$ denote the set of all 3-connected $${\mathcal{F}}$$ -free graphs. This paper is concerned with sets $${\mathcal{F}}$$ of connected graphs such that $${\mathcal{F}}$$ contains no star, $${|\mathcal{F}|=3}$$ and $${\mathcal{G}_{3}(\mathcal{F})}$$ is finite. Among other results, we show that for a connected graph T( ≠ K) which is not a star, $${\mathcal{G}_{3}(\{K_{4},K_{2,2},T\})}$$ is finite if and only if T is a path of order at most 6. [ABSTRACT FROM AUTHOR]

Abstract: For , and , let be the minimum value satisfying that for any connected graph of order with radius ; if no such graph exists, we set . For and , let . In this paper, we investigate the behavior of the function and determine some exact values of when or is small. [Copyright &y& Elsevier]

Abstract: The domination number of a graph is the minimum cardinality of any dominating set of . An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In general, every connected graph has diameter at most . It is known that the diameter of a connected dot-critical graph is at most . In this paper, we show that, if a dot-critical graph has diameter exactly , then is a path. Furthermore, we focus on dot-critical graphs with high connectivity. We prove that, for , the diameter of an -connected dot-critical graph is at most , and show that the bound is best possible. [Copyright &y& Elsevier]

Abstract: A spanning tree with no vertices of degree from 2 to of a graph is called a -spanning tree ( -ST) of the graph. In this paper, we consider sets of forbidden subgraphs that imply the existence of a -ST in a connected graph of sufficiently large order, and give the characterization of such sets. We also focus on connected graphs that contain no path of order as an induced subgraph, and characterize such graphs having a -ST. [Copyright &y& Elsevier]

In this paper, we prove that for a sufficiently large integer d and a connected graph G , if | V (G) | < (d + 2) (δ (G) + 1) 3 , then there exists a spanning tree T of G such that diam (T) ≤ d. [ABSTRACT FROM AUTHOR]

A paired dominating set of a graph G with no isolated vertex is a dominating set S of vertices such that the subgraph induced by S in G has a perfect matching. The paired domination number of G, denoted by γ( G), is the minimum cardinality of a paired dominating set of G. The paired domination subdivision number $${{\rm sd}_{\gamma _{\rm pr}}(G)}$$ is the minimum number of edges to be subdivided (each edge of G can be subdivided at most once) in order to increase the paired domination number. In this paper, we show that if G is a connected graph of order at least 4, then $${{\rm sd}_{\gamma _{\rm pr}}(G)\leq 2|V(G)|-5}$$. We also characterize trees T such that $${{\rm sd}_{\gamma _{\rm pr}}(T) \geq |V(T)| /2}$$. [ABSTRACT FROM AUTHOR]

Abstract: A -rainbow dominating function of a graph is a function such that, for each vertex with , . The minimum of over all such functions is called the -rainbow domination number . A Roman dominating function of a graph , is a function such that, for each vertex with , is adjacent to a vertex with . The minimum of over all such functions is called the Roman domination number . Regarding as , these two dominating functions have a common property that the same three integers are used and a vertex having must be adjacent to a vertex having . Motivated by this similarity, we study the relationship between and . 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 of order contains a bipartite subgraph such that and . The bound on is best possible. [Copyright &y& Elsevier]

A vertex of a graph is called critical if its deletion decreases the domination number, and an edge is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In this paper, we show that if G is a connected dot-critical graph with domination number k ≥ 3 and diameter d and if G has no critical vertices, then d ≤ 2 k−3. [ABSTRACT FROM AUTHOR]

Abstract: A -rainbow dominating function of a graph is a function from the vertices to such that, for all , either or . The -rainbow domatic number is the maximum integer such that there exists a set of -rainbow dominating functions with for all . We study the-rainbow domatic number by finding this number for some classes of graphs and improving upon some known general bounds. [Copyright &y& Elsevier]

In this paper, we characterize 2-connected { K 1 , 3 , N 3 , 1 , 1 } -free graphs without Hamiltonian cycle, where K 1 , 3 is the star of order 4 and N n 1 , n 2 , n 3 is the graph obtained from K 3 and three vertex-disjoint paths P n 1 + 1 , P n 2 + 1 , P n 3 + 1 by identifying each of vertices of K 3 with an endvertex of one of the paths. Such a characterization gives some refinements for known results, for example, a characterization of 2-connected { K 1 , 3 , N 3 , 1 , 1 , N 2 , 2 , 1 } -free graphs containing no Hamiltonian cycle given in Brousek et al. (1999) and the existence of a 2-factor in 2-connected { K 1 , 3 , N 3 , 1 , 1 } -free graphs given in Faudree et al. (2008). [ABSTRACT FROM AUTHOR]

In this note, we prove that every triangulation G on any closed surface has domination number at most [ABSTRACT FROM AUTHOR]

We let γ ( G ) and i ( G ) denote the domination number and the independent domination number of G , respectively. Recently, Rad and Volkmann conjectured that i ( G ) / γ ( G ) ≤ Δ ( G ) / 2 for every graph G , where Δ ( G ) is the maximum degree of G . In this note, we construct counterexamples of the conjecture for Δ ( G ) ≥ 6 and give a sharp upper bound of the ratio i ( G ) / γ ( G ) by using the maximum degree of G . [ABSTRACT FROM AUTHOR]

A major line of research is discovering Ramsey-type theorems, which are results of the following form: given a graph parameter ρ , every graph G with sufficiently large ρ (G) contains a particular induced subgraph H with large ρ (H). The classical Ramsey's theorem deals with the case when the graph parameter under consideration is the number of vertices. There is also a Ramsey-type theorem regarding connected graphs, namely, every sufficiently large connected graph contains a large induced connected graph that is a complete graph, a large star, or a path. Given a graph G , the matching number and the induced matching number of G are the maximum size of a matching and an induced matching, respectively, of G. In this paper, we formulate Ramsey-type theorems for the matching number and the induced matching number regarding connected graphs. Along the way, we obtain a Ramsey-type theorem for the independence number regarding connected graphs as well. [ABSTRACT FROM AUTHOR]

Let G be a graph without isolated vertices. A total dominating set of G is a subset S of V ( G ) such that every vertex of G is adjacent to a vertex in S . The minimum cardinality of a total dominating set of G is denoted by γ t ( G ) . A 2-rainbow dominating function of G is a function f : V ( G ) → 2 { 1 , 2 } such that for each v ∈ V ( G ) with f ( v ) = 0̸ , ⋃ u ∈ N G ( v ) f ( u ) = { 1 , 2 } . The minimum of ∑ v ∈ V ( G ) | f ( v ) | over all 2-rainbow dominating functions f of G is denoted by γ r 2 ( G ) . Chellali, Haynes and Hedetniemi conjectured that for every graph G without isolated vertices, γ t ( G ) ≤ γ r 2 ( G ) . In this note, we solve the conjecture. [ABSTRACT FROM AUTHOR]

Abstract: A graph is said to be bicritical if the removal of any pair of vertices decreases the domination number of . For a bicritical graph with the domination number , we say that is -bicritical. Let denote the edge-connectivity of . In , Brigham et al. (2005) posed the following question: If is a connected bicritical graph, is it true that In this paper, we give a negative answer toward this question; namely, we give a construction of infinitely many connected -bicritical graphs with edge-connectivity for every integer . Furthermore, we give some sufficient conditions for a connected -bicritical graph to have . [Copyright &y& Elsevier]

Given [ABSTRACT FROM AUTHOR]