More on monochromatic-rainbow Ramsey type theorems

An edge colored graph is called a rainbow if no two of its edges have the same color. Let ? and $\mathcal{G}$ be two families of graphs. Denote by $RM({\mathcal{H}},\mathcal{G})$ the smallest integer R, if it exists, having the property that every coloring of the edges of K _R by an arbitrary number of colors implies that either there is a monochromatic subgraph of K _R that is isomorphic to a graph in ? or there is a rainbow subgraph of K _R that is isomorphic to a graph in $\mathcal{G}$ . ${\mathcal{T}}_{n}$ is the set of all trees on n vertices. ${\mathcal{T}}_{n}(k)$ denotes all trees on n vertices with diam(T _n (k))≤k. In this paper, we investigate $RM({\mathcal{T}}_{n},4K_{2})$ , $RM({\mathcal{T}}_{n},K_{1,4})$ and $RM({\mathcal{T}}_{n}(4),K_{3})$ .     

Nordhaus–Gaddum-Type Theorem for Rainbow Connection Number of Graphs

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted by rc(G), is the minimum number of colors that are needed to make G rainbow connected. In this paper we give a Nordhaus–Gaddum-type result for the rainbow connection number. We prove that if G and ${\overline{G}}$ are both connected, then ${4\leq rc(G)+rc(\overline{G})\leq n+2}$ . Examples are given to show that the upper bound is sharp for n ≥ 4, and the lower bound is sharp for n ≥ 8. Sharp lower bounds are also given for n = 4, 5, 6, 7, respectively.     

The Edge Rotation Graph

Let P be a set of n points on the plane in general position, n ≥  3. The edge rotation graph ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ , such as its connectivity and diameter. We show that if the vertices of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ are not triangulations of P, then it is connected and has diameter O(n ²). We also show that the chromatic number of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs.     

On Graphlike k-Dissimilarity Vectors

Let \({\mathcal{G} = (G, w)}\) be a positive-weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of edges of G to the set of positive real numbers. For any subgraph \({G^\prime}\) of G, we define \({w(G^\prime)}\) to be the sum of the weights of the edges of \({G^\prime}\) . For any i ₁, . . . , i _k vertices of G, let \({D_{\{i_1,..., i_k\}} (\mathcal{G})}\) be the minimum of the weights of the subgraphs of G connecting i ₁, . . . , i _k . The \({D_{\{i_1,..., i_k\}}(\mathcal{G})}\) are called k-weights of \({\mathcal{G}}\) . Given a family of positive real numbers parametrized by the k-subsets of {1, . . . , n}, \({{\{D_I\}_{I} \in { \{1,...,n\} \choose k}}}\) , we can wonder when there exist a weighted graph \({\mathcal{G}}\) (or a weighted tree) and an n-subset {1, . . . , n} of the set of its vertices such that \({D_I (\mathcal{G}) = D_I}\) for any \({I} \in { \{1,...,n\} \choose k}\) . In this paper we study this problem in the case k =  n?1.     

The t-Tone Chromatic Number of Random Graphs

A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from \({\binom{[k]}{2}}\) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ ₂(G) is the smallest k such that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for \({p\geq Cn^{-1/4} {\rm ln}^{9/4}n, \tau_2(G_{n, p}) = (2 + o(1))\chi(G_{n, p})}\) where \({\chi}\) represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that \({\tau_2(G_{n, p}) = \lceil{({\sqrt{8\Delta + 1} + 5})/{2}}}\) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.     

A new graceful labeling for pendant graphs

A graceful labeling of a graph G with q edges is an injective assignment of labels from {0, 1, . . . , q} to the vertices of G so that when each edge is assigned the absolute value of the difference of the vertex labels it connects, the resulting edge labels are distinct. A labeling of the first kind for coronas ${C_n \odot K_1}$ occurs when vertex labels 0 and q = 2n are assigned to adjacent vertices of the n-gon. A labeling of the second kind occurs when q = 2n is assigned to a pendant vertex. Previous research has shown that all coronas ${C_n \odot K_1}$ have a graceful labeling of the second kind. In this paper we show that all coronas ${C_n \odot K_1}$ with ${n \equiv 3, 4\, {\rm (mod\, 8)}}$ also have a graceful labeling of the first kind.     

Degree Sum Conditions for Hamiltonicity on k-Partite Graphs

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least \(\frac{p} {2}\) then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than \(\frac{p} {4}\) then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian.     

Smallest Set-Transversals of k-Partitions

We asymptotically solve an open problem raised independently by Sterboul (Colloq Math Soc J Bolyai 3:1387–1404, 1973), Arocha et al. (J Graph Theory 16:319–326, 1992) and Voloshin (Australas J Combin 11:25–45, 1995). For integers n ≥ k ≥ 2, let f(n, k) denote the minimum cardinality of a family ${\mathcal H}$ of k-element sets over an n-element underlying set X such that every partition ${X_1\cup\cdots\cup X_k=X}$ into k nonempty classes completely partitions some ${H\in\mathcal H}$ ;  that is, ${|H\cap X_i|=1}$ holds for all 1 ≤ i ≤ k. This very natural function—whose defining property for k = 2 just means that ${\mathcal H}$ is a connected graph—turns out to be related to several extensively studied areas in combinatorics and graph theory. We prove general estimates from which ${ f(n,k) = (1+o(1))\, \tfrac{2}{n}\,{n\choose k}}$ follows for every fixed k, and also for all k = o(n ^1/3), as n → ∞. Further, we disprove a conjecture of Arocha et al. (1992). The exact determination of f(n,k) for all n and k appears to be far beyond reach to our present knowledge, since e.g. the equality ${f(n,n-2)={n-2\choose 2}-{\rm ex}(n,\{C_3,C_4\})}$ holds, where the last term is the Turán number for graphs of girth 5.     

On Ramsey—Turán type theorems for hypergraphs

LetH ^r be anr-uniform hypergraph. Letg=g(n;H ^r ) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH ^r . Lete =f(n;H ^r ,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH ^r . We show that ifr>2 andH ^r is e.g. a complete graph then $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r )$$ while for someH ^r with \(\mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r ) \ne 0\) $$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = 0$$ . This is in strong contrast with the situation in caser=2. Some other theorems and many unsolved problems are stated.     

The Linear t-Colorings of Sierpiński-Like Graphs

A proper t-coloring of a graph G is a mapping ${\varphi: V(G) \rightarrow [1, t]}$ such that ${\varphi(u) \neq \varphi(v)}$ if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by ${\chi(G)}$ , is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by ${lc(G)}$ , is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S(n, k), ${S^+(n, k)}$ and ${S^{++}(n, k)}$ are studied. It is obtained that ${lc(S(n, k))= \chi (S(n, k)) = k}$ for any positive integers n and k, ${lc(S^+(n, k)) = \chi(S^+(n, k)) = k}$ and ${lc(S^{++}(n, k)) = \chi(S^{++}(n, k)) = k}$ for any positive integers ${n \geq 2}$ and ${k \geq 3}$ . Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely.     

C 4p -frame of complete multipartite multigraphs

For two graphs G and H their wreath product ${G \otimes H}$ has the vertex set ${V(G) \times V(H)}$ in which two vertices (g ₁, h ₁) and (g ₂, h ₂) are adjacent whenever ${g_{1}g_{2} \in E(G)}$ or g ₁ =  g ₂ and ${h_{1}h_{2} \in E(H)}$ . Clearly ${K_{m} \otimes I_{n}}$ , where I _n is an independent set on n vertices, is isomorphic to the complete m-partite graph in which each partite set has exactly n vertices. A subgraph of the complete multipartite graph ${K_m \otimes I_n}$ containing vertices of all but one partite set is called partial factor. An H-frame of ${K_m \otimes I_n}$ is a decomposition of ${K_m \otimes I_n}$ into partial factors such that each component of it is isomorphic to H. In this paper, we investigate C _2k -frames of ${(K_m \otimes I_n)(\lambda)}$ , and give some necessary or sufficient conditions for such a frame to exist. In particular, we give a complete solution for the existence of a C _4p -frame of ${(K_m \otimes I_n)(\lambda)}$ , where p is a prime, as follows: For an integer m ≥  3 and a prime p, there exists a C _4p -frame of ${(K_m \otimes I_n)(\lambda)}$ if and only if ${(m-1)n \equiv 0 ({\rm {mod}} {4p})}$ and at least one of m, n must be even, when λ is odd.     

Hypergraphs do not jump

The number α, 0≦α≦1, is a jump forr if for any positive ε and any integerm,m≧r, anyr-uniform hypergraph withn>n _o (ε,m) vertices and at least (α+ε) \(\left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)\) edges contains a subgraph withm vertices and at least (α+c) \(\left( {\begin{array}{*{20}c} m \\ r \\ \end{array} } \right)\) edges, wherec=c(α) does not depend on ε andm. It follows from a theorem of Erdös, Stone and Simonovits that forr=2 every α is a jump. Erdös asked whether the same is true forr≧3. He offered $ 1000 for answering this question. In this paper we give a negative answer by showing that \(1 - \frac{1}{{l^{r - 1} }}\) is not a jump ifr≧3,l>2r.     

On Some Ramsey Numbers for Quadrilaterals Versus Wheels

For given graphs G ₁ and G ₂, the Ramsey number R(G ₁, G ₂) is the least integer n such that every 2-coloring of the edges of K _n contains a subgraph isomorphic to G ₁ in the first color or a subgraph isomorphic to G ₂ in the second color. Surahmat et al. proved that the Ramsey number ${R(C_4, W_n) \leq n + \lceil (n-1)/3\rceil}$ . By using asymptotic methods one can obtain the following property: ${R(C_4, W_n) \leq n + \sqrt{n}+o(1)}$ . In this paper we show that in fact ${R(C_4, W_n) \leq n + \sqrt{n-2}+1}$ for n ≥ 11. Moreover, by modification of the Erd?s-Rényi graph we obtain an exact value ${R(C_4, W_{q^2+1}) = q^2 + q + 1}$ with q ≥ 4 being a prime power. In addition, we provide exact values for Ramsey numbers R(C ₄, W _n ) for 14 ≤ n ≤ 17.     

Graphs with Average Degree Smaller Than {\frac {30}{11}} Burn Slowly

In this paper, we consider the following firefighter problem on a finite graph G =  (V, E). Suppose that a fire breaks out at a given vertex ${v \in V}$ . In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbours of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate ${\rho(G)}$ of G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of G. Let ε >  0. We show that any graph G on n vertices with at most ${(\frac {15}{11} - \varepsilon)n}$ edges can be well protected, that is, ${\rho(G) > \frac {\varepsilon}{60} > 0}$ . Moreover, a construction of a random graph is proposed to show that the constant ${\frac {15}{11}}$ cannot be improved.     

Adjacency matrices of polarity graphs and of other C 4-free graphs of large size

In this paper we give a method for obtaining the adjacency matrix of a simple polarity graph G _q from a projective plane PG(2, q), where q is a prime power. Denote by ex(n; C ₄) the maximum number of edges of a graph on n vertices and free of squares C ₄. We use the constructed graphs G _q to obtain lower bounds on the extremal function ex(n; C ₄), for some n < q ² + q + 1. In particular, we construct a C ₄-free graph on ${n=q^2 -\sqrt{q}}$ vertices and ${\frac{1}{2} q(q^2-1)-\frac{1}{2}\sqrt{q} (q-1) }$ edges, for a square prime power q.     

Some relations on the ordering of trees by minimal energies between subclasses of trees

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. A tree is said to be non-starlike if it has at least two vertices with degree more than 2. A caterpillar is a tree in which a removal of all pendent vertices makes a path. Let $\mathcal{T}_{n,d}$ , $\mathbb{T}_{n,p}$ be the set of all trees of order n with diameter d, p pendent vertices respectively. In this paper, we investigate the relations on the ordering of trees and non-starlike trees by minimal energies between $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ . We first show that the first two trees (non-starlike trees, resp.) with minimal energies in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same for 3≤d≤n?2 (3≤d≤n?3, resp.). Then we obtain that the trees with third-minimal energy in $\mathcal{T}_{n,d}$ and $\mathbb{T}_{n,n-d+1}$ are the same when n≥11, 3≤d≤n?2 and d≠8; and the tree with third-minimal energy in $\mathcal{T}_{n,8}$ is the caterpillar with third-minimal energy in $\mathbb{T}_{n,n-7}$ for n≥11.     

Packing Triangles in K 4-Free Graphs

Paul Erd?s conjectured that every K ₄-free graph of order n and size ${k + \lfloor n^2/4\rfloor}$ contains at least k edge disjoint triangles. In this note, we prove that such a graph contains at least 32k/35 + o(n ²) edge disjoint triangles and prove his conjecture for k ≥  0.077n ².     

A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture

The article shrinks the Δ = 6 hole that exists in the family of planar graphs which satisfy the total coloring conjecture. Let G be a planar graph. If ${v_n^k}$ represents the number of vertices of degree n which lie on k distinct 3-cycles, for ${n, k \in \mathbb{N}}$ , then the conjecture is true for planar graphs which satisfy ${v_5^4 +2(v_5^{5^+} +v_6^4) +3v_6^5 +4v_6^{6^+} < 24}$ .     

Dominant dimensions,derived equivalences and tilting modules

We show that for every ? > 0 there exist δ > 0 and n₀ ∈ ? such that every 3-uniform hypergraph on n ≥ n₀ vertices with the property that every k-vertex subset, where k ≥ δn, induces at least \(\left( {\frac{1}{2} + \varepsilon } \right)\left( {\begin{array}{*{20}c} k \\ 3 \\ \end{array} } \right)\) edges, contains K₄^? as a subgraph, where K₄^? is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erd?s and Sós. The constant 1/4 is the best possible.     

An extremal problem in graph theory

It is proved that the maximum number of cut-vertices in a connected graph withn vertices andm edges is $$max\left\{ {q:m \leqq (_2^{n - q} ) + q} \right\}$$ All the extremal graphs are determined and the corresponding problem for cut-edges is also solved.