Search

Given a graph H $H$, the k $k$‐colored Gallai–Ramsey number grk(K3:H) $g{r}_{k}({K}_{3}:H)$ is defined to be the minimum integer n $n$ such that every k $k$‐coloring of the edges of the complete graph on n $n$ vertices contains either a rainbow triangle or a monochromatic copy of H. $H.$ Fox et al. conjectured the values of the Gallai–Ramsey numbers for complete graphs. Recently, this conjecture has been verified for the first open case, when H=K4 $H={K}_{4}$. In this paper we attack the next case, when H=K5 $H={K}_{5}$. Surprisingly it turns out, that the validity of the conjecture depends upon the (yet unknown) value of the Ramsey number R(5,5) $R(5,5)$. It is known that 43≤R(5,5)≤48 $43\le R(5,5)\le 48$ and conjectured that R(5,5)=43 $R(5,5)=43$. If 44≤R(5,5)≤48 $44\le R(5,5)\le 48$, then Fox et al.'s conjecture is true and we present a complete proof. If, however, R(5,5)=43 $R(5,5)=43$, then Fox et al.'s conjecture is false, meaning that exactly one of these conjectures is true while the other is false. For the case when R(5,5)=43 $R(5,5)=43$, we show lower and upper bounds for the Gallai–Ramsey number grk(K3:K5) $g{r}_{k}({K}_{3}:{K}_{5})$. [ABSTRACT FROM AUTHOR]

Given a graph G and a positive integer k, define the Gallai—Ramsey number to be the minimum number of vertices n such that any k-edge coloring of Kn contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this paper, we obtain exact values of the Gallai—Ramsey numbers for the union of two stars in many cases and bounds in other cases. This work represents the first class of disconnected graphs to be considered as the desired monochromatic subgraph. [ABSTRACT FROM AUTHOR]

Given a graph G and a positive integer k, define the Gallai-Ramsey number to be the minimum number of vertices n such that any k-edge coloring of K n contains either a rainbow (all different colored) triangle or a monochromatic copy of G. Much like graph Ramsey numbers, Gallai-Ramsey numbers have gained a reputation as being very difficult to compute in general. As yet, still only precious few sharp results are known. In this paper, we obtain bounds on the Gallai-Ramsey number for wheels and the exact value for the wheel on 5 vertices. [ABSTRACT FROM AUTHOR]

Let G be an edge-colored connected graph. A path P in G is called ℓ -rainbow if no two edges of the same color have fewer than ℓ edges between them on P. The graph G is called (k , ℓ) -rainbow connected if every pair of distinct vertices of G are connected by k pairwise internally vertex-disjoint ℓ -rainbow paths in G. For a k-connected graph G, the minimum number of colors needed to make G (k , ℓ) -rainbow connected is called the (k , ℓ) -rainbow connection number of G and denoted by r c k , ℓ (G) . In this paper, we prove that r c 1 , 2 (G) ≤ 5 for any 2-connected graph G and provide a counter example which overturns a conjecture posed by Chartrand et al. in 2016. Considering graph operations, we study the (1, 2)-rainbow connection numbers for the join, the Cartesian, strong and lexicographic products of graphs, giving the sharp upper bounds for nearly all graph products. In addition, we find some basic properties of the (k , ℓ) -rainbow connection number and determine the values of r c 1 , ℓ (G) where G is a cube or a permutation graph of a nontrivial traceable graph. [ABSTRACT FROM AUTHOR]

Given a graph G and a positive integer k, define the Gallai-Ramsey number to be the minimum number of vertices n such that any k-edge coloring of K n contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this paper, we consider two classes of unicyclic graphs, the star with an extra edge and the path with a triangle at one end. We provide the 2-color Ramsey numbers for these two classes of graphs and use these to obtain general upper and lower bounds on the Gallai-Ramsey numbers. [ABSTRACT FROM AUTHOR]

Given two disjoint sets of k vertices each in a graph G, it was recently asked whether δ (G) ≥ n / 2 and κ (G) ≥ 2 k would be a sufficient assumption to guarantee the existence of a Hamiltonian cycle of G which alternates visiting vertices of the two selected sets. We answer this question in the affirmative when the graph is large and we also provide a generalization to more sets. [ABSTRACT FROM AUTHOR]

Given graphs G and H and a positive integer k, the Gallai–Ramsey number, denoted by g r k (G : H) is defined to be the minimum integer n such that every coloring of K n using at most k colors will contain either a rainbow copy of G or a monochromatic copy of H. We consider this question in the cases where G ∈ { P 4 , P 5 } . In the case where G = P 4 , we completely solve the Gallai–Ramsey question by reducing to the 2-color Ramsey numbers. In the case where G = P 5 , we conjecture that the problem reduces to the 3-color Ramsey numbers and provide several results in support of this conjecture. [ABSTRACT FROM AUTHOR]

Given a graph H, the k‐colored Gallai‐Ramsey number grk(K3⁢ :H) is defined to be the minimum integer n such that every k‐coloring (using all k colors) of the complete graph on n vertices contains either a rainbow triangle or a monochromatic copy of H. Recently, Fox et al [J. Combin. Theory Ser. B, 111 (2015), pp. 75–125] conjectured the value of the Gallai‐Ramsey numbers for complete graphs. We verify this conjecture for the first open case, where H=K4. [ABSTRACT FROM AUTHOR]

A recent variation of the classical geodetic problem, the strong geodetic problem, is defined as follows. If G is a graph, then sg (G) is the cardinality of a smallest vertex subset S, such that one can assign a fixed geodesic to each pair { x , y } ⊆ S so that these | S | 2 geodesics cover all the vertices of G. In this paper, we first give some bounds for strong geodetic number in terms of diameter, connectivity, respectively. Next, we show that 2 ≤ sg (G) ≤ n for a connected graph G of order n, and graphs with sg (G) = 2 , n - 1 , n are characterized, respectively. In the end, we investigate the Nordhaus–Gaddum-type problem and extremal problems for strong geodetic number. [ABSTRACT FROM AUTHOR]

An path that is edge-colored is called proper if no two consecutive edges receive the same color. A general graph that is edge-colored is called properly connected if, for every pair of vertices in the graph, there exists a properly colored path from one to the other. Given two vertices u and v in a properly connected graph G, the proper distance is the length of the shortest properly colored path from u to v. By considering a specific class of colorings that are properly connected for Cartesian products of complete and cyclic graphs, we present results on the proper distance between all pairs of vertices in the graph. [ABSTRACT FROM AUTHOR]

In 2000, Enomoto and Ota conjectured that if a graph G satisfies σ2(G)≥|G|+k-1, then for any set of k vertices v1,…,vk and for any positive integers n1,…,nk with ∑ni=|G|, there exists a partition of V(G) into k paths P1,…,Pk such that vi is an end of Pi and |Pi|=ni for all i. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices. [ABSTRACT FROM AUTHOR]

Gallai-Ramsey numbers often consider edge-colorings of complete graphs in which there are no rainbow triangles. Within such colored complete graphs, the goal is to look for specified monochromatic subgraphs. We consider an “off diagonal” case of this concept by looking for either a monochromatic K3 in one of some set of colors or a monochromatic C4 in one of some other set of colors. [ABSTRACT FROM AUTHOR]

In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph. [ABSTRACT FROM AUTHOR]

Let k be a positive integer and let F and H1,H2,…,Hk be simple graphs. The proper-Ramsey number prk(F;H1,H2,…,Hk) is the minimum integer n such that any k-coloring of the edges of Kn contains either a properly colored copy of F or a copy of Hi in color i, for some i. We consider the case where F=C4 is fixed, and establish the exact value of the proper-Ramsey number when {Hi}i=1k is a family containing only cliques, and nearly sharp bounds for the proper-Ramsey number when {Hi}i=1k is a family containing only cycles or only stars. We also give a general bound for the proper-Ramsey number that is nearly tight when {Hi}i=1k is a family of maximal split graphs. [ABSTRACT FROM AUTHOR]

If g is a Frobenius Lie algebra, then for certain F∈g∗ the natural map g⟶g∗ given by x⟼F[x,-] is an isomorphism. The inverse image of F under this isomorphism is called a principal element. We show that if g is a Frobenius seaweed subalgebra of An-1=sl(n), then the spectrum of the adjoint of a principal element consists of an unbroken set of integers whose multiplicities have a symmetric distribution. Our proof methods are constructive and combinatorial in nature. [ABSTRACT FROM AUTHOR]

A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with 2≤k≤n. For S⊆V(G) and |S|≥2, an S-tree is a tree containing the vertices of S in G. A set {T1,T2,…,Tℓ} of S-trees is called internally disjoint if E(Ti)∩E(Tj)=∅ and V(Ti)∩V(Tj)=S for 1≤i≠j≤ℓ. For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by κ(S). The k-connectivityκk(G) of G is defined by κk(G)=min{κ(S)∣S is a k-subset of V(G)}. For a connected graph G of order n and for two integers k and ℓ with 2≤k≤n and 1≤ℓ≤κk(G), the (k,ℓ)-proper indexpxk,ℓ(G) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist ℓ internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and ℓ with k≥3 and ℓ≤κk(Kn,n), there exists a positive integer N1=N1(k,ℓ) such that pxk,ℓ(Kn)=2 for every integer n≥N1, and there exists also a positive integer N2=N2(k,ℓ) such that pxk,ℓ(Km,n)=2 for every integer n≥N2 and m=O(nr)(r≥1). In addition, we show that for every p≥clogannk (c≥5), pxk,ℓ(Gn,p)≤2 holds almost surely, where Gn,p is the Erdős-Rényi random graph model. [ABSTRACT FROM AUTHOR]

A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A total-colored graph is total-rainbow connected if any two vertices of the graph are connected by a path whose edges and internal vertices have distinct colors. For a connected graph G, the total-rainbow connection number of G, denoted by trc( G), is the minimum number of colors required in a total-coloring of G to make G total-rainbow connected. In this paper, we first characterize the graphs having large total-rainbow connection numbers. Based on this, we obtain a Nordhaus-Gaddum-type upper bound for the total-rainbow connection number. We prove that if G and $$\overline{G}$$ are connected complementary graphs on n vertices, then $$trc(G)+trc(\overline{G})\le 2n$$ when $$n\ge 6$$ and $$trc(G)+trc(\overline{G})\le 2n+1$$ when $$n=5$$ . Examples are given to show that the upper bounds are sharp for $$n\ge 5$$ . This completely solves a conjecture in Ma (Res Math 70(1-2):173-182, 2016). [ABSTRACT FROM AUTHOR]

Analogous to the𝔰𝔩(n) case, we address the computation of the index of seaweed subalgebras of𝔰𝔭(2n) by introducing graphical representations called symplectic meanders. Formulas for the algebra’s index may be computed by counting the connected components of its associated meander. In certain cases, formulas for the index can be given in terms of elementary functions. [ABSTRACT FROM PUBLISHER]

We consider the connected graphs G that satisfy the following property: If $$n \gg m \gg k$$ are integers, then any coloring of the edges of $$K_{n}$$ , using m colors, containing no properly colored copy of G, contains a monochromatic k-connected subgraph of order at least $$n - f(G, k, m)$$ where f does not depend on n. If we let $$\mathscr {G}$$ denote the set of graphs satisfying this statement, we exhibit some infinite families of graphs in $$\mathscr {G}$$ as well as conjecture that the cycles in $$\mathscr {G}$$ are precisely those whose lengths are divisible by 3. Our main result is that $$C_{6} \in \mathscr {G}$$ . [ABSTRACT FROM AUTHOR]

We prove a sharp connectivity and degree sum condition for the existence of a subdivision of a multigraph in which some of the vertices are specified and the distance between each pair of vertices in the subdivision is prescribed (within one). Our proof makes use of the powerful Regularity Lemma in an easy way that highlights the extreme versatility of the lemma. [ABSTRACT FROM AUTHOR]

An edge-colored directed graph is called properly connected if, between every pair of vertices, there is a properly colored directed path. We study some conditions on directed graphs which guarantee the existence of a coloring that is properly connected. We also study conditions on a colored directed graph which guarantee that the coloring is properly connected. [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]

With sufficient minimum degree sum, Enomoto and Ota conjectured that for any selected set of vertices, there exists a spanning collection of disjoint paths, each starting at one of the selected vertices and each having a prescribed length. Using the Regularity Lemma, we prove that this claim holds without the spanning assumption if the vertex set of the host graph is sufficiently large. [ABSTRACT FROM AUTHOR]

Given a graph G and a positive integer k, define the Gallai-Ramsey number to be the minimum number of vertices n such that any k-edge coloring of [ABSTRACT FROM AUTHOR]

A classical result of Hajnal and Szemerédi, when translated to a complementary form, states that with sufficient minimum degree, a graph will contain disjoint large cliques. We conjecture a generalization of this result from cliques to cycles with many chords and prove this conjecture in several cases. [ABSTRACT FROM AUTHOR]

Math. Sci. Soc. (2021) 44:3991-4002 https://doi.org/10.1007/s408... The Funding information section was missing from this article and should have read 'The first author was supported by Zhejiang Provincial Natural Science Foundation of China Grant LQ21A010005'. The original article can be found online at https://doi.org/10.1007/s40840-021-01119-6. Funding The first author was supported by Zhejiang Provincial Natural Science Foundation of China Grant LQ21A010005. [Extracted from the article]

For a collection of graphs $${\fancyscript{G}}$$ , the distance graph of $${\fancyscript{G}}$$ is defined to be the graph containing a vertex for each graph in $${\fancyscript{G}}$$ , and an edge if the two corresponding graphs differ by exactly one edge. In 1998, Chartrand, Kubicki and Schultz conjectured that every bipartite graph is the distance graph for some collection of graphs. In this paper, we provide methods to combine known distance graphs to generate new larger ones. As observed by Gorše Pihler and Žerovnik in 2008, an important subcase of this conjecture seems to be whether dense graphs can be distance graphs, particularly the complete bipartite graphs. Along these lines, we extend the class of known distance graphs to include K. We further introduce equivalent formulations of this conjecture and discuss related problems. [ABSTRACT FROM AUTHOR]

Gallai-colorings of complete graphs-edge colorings such that no triangle is colored with three distinct colors-occur 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. [ABSTRACT FROM AUTHOR]

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 Kn 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. [ABSTRACT FROM AUTHOR]

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 Gallai-Ramsey 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 Gallai-Ramsey results of Chung and Graham, Faudree et al. and Gyárfás et al. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory [ABSTRACT FROM AUTHOR]

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrarymultigraph of order k, sizem, n0(H) isolated vertices and n1(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165-182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H and δ(G) ≥ n+m-k+n1(H)+2n0(H)/2 , then G contains a spanning H-subdivision with the same ground set as H. As a corollary to this result, the authors were able to obtain Dirac's famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3with δ(G) ≥ n/2 , then G is hamiltonian. Bondy (J.Comb.Theory Ser.B11:80-84, 1971) extended Dirac's theorem by showing that if G satisfied the condition δ(G) ≥ n/2 then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165-182, 2007) in a similar manner. An H-subdivisionHin G is 1-extendible if there exists an H-subdivision H* with the same ground set as H and ∣H*∣ = ∣H∣ + 1. If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that δ(G) ≥ n+m-k+n1(H)+2n0(H)/2 , then G is pan-H-linked. This result is sharp. [ABSTRACT FROM AUTHOR]

In this work, we collect Ramsey-type results concerning rainbow edge colorings of graphs. [ABSTRACT FROM AUTHOR]