Search

For two graphs $G,H$ and a positive integer $k$, the \emph{Gallai-Ramsey number} $\operatorname{gr}_k(G,H)$ is defined as the minimum number of vertices $n$ such that any $k$-edge-coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $H$. If $G$ and $H$ are both complete graphs, then we call it Gallai-Ramsey function. Fox and Sudakov proved $\operatorname{gr}_k(K_s,K_t)\leq s^{4kt}$. Alon et al. showed that $\operatorname{gr}_k(K_s,K_t)\leq (2s^3+4s^2)^{kt}$. In this paper, we prove that $\operatorname{gr}_k(K_s,K_t)\leq 2^{kt}s^{3kt}$ for $t\geq 47$. We also give better upper bounds for $\operatorname{gr}_k(G,H)$ when $G,H$ are some special graphs. In this paper, we derive some lower bounds for Gallai-Ramsey functions and numbers by Lov\'{a}sz Local Lemma., Comment: 17 pages

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph $G$ of order at least $2$ and $S\subseteq V(G)$, the \emph{Steiner distance} $d_G(S)$ among the vertices of $S$ is the minimum size among all connected subgraphs whose vertex sets contain $S$. Let $n,k$ be two integers with $2\leq k\leq n$. Then the \emph{Steiner $k$-eccentricity $e_k(v)$} of a vertex $v$ of $G$ is defined by $e_k(v)=\max \{d(S)\,|\,S\subseteq V(G), \ |S|=k, \ and \ v\in S \}$. Furthermore, the \emph{Steiner $k$-diameter} of $G$ is $sdiam_k(G)=\max \{e_k(v)\,|\, v\in V(G)\}$. In 2011, Chartrand, Okamoto and Zhang showed that $k-1\leq sdiam_k(G)\leq n-1$. In this paper, graphs with $sdiam_4(G)=3,4,n-1$ are characterized, respectively., Comment: 18 pages, 2 figures. arXiv admin note: text overlap with arXiv:1509.02801

For any graph $G$ of order $n$, the spanning tree packing number \emph{$STP(G)$}, is the maximum number of edge-disjoint spanning trees contained in $G$. In this paper, we obtain some sharp lower bounds for the spanning tree numbers of Cartesian product graphs and Lexicographic product graphs., Comment: 11 pages

The problem of determining the smallest number of edges, $h(n;\bar{\kappa}\geq r)$, which guarantees that any graph with $n$ vertices and $h(n;\bar{\kappa}\geq r)$ edges will contain a pair of vertices joined by $r$ internally disjoint paths was posed by Erd\"{o}s and Gallai. Bollob\'{a}s considered the problem of determining the largest number of edges $f(n;\bar{\kappa}\leq \ell)$ for graphs with $n$ vertices and local connectivity at most $\ell$. One can see that $f(n;\bar{\kappa}\leq \ell)= h(n;\bar{\kappa}\geq \ell+1)-1$. These two problems had received a wide attention of many researchers in the last few decades. In the above problems, only pairs of vertices connected by internally disjoint paths are considered. In this paper, we study the number of internally disjoint Steiner trees connecting sets of vertices with cardinality at least 3., Comment: 12 pages

A path in an edge (vertex)-colored graph $G$, where adjacent edges (vertices) may have the same color, is called a rainbow path if no pair of edges (internal vertices) of the path are colored the same. The rainbow (vertex) connection number $rc(G)$ ($rvc(G)$) of $G$ is the minimum integer $i$ for which there exists an $i$-edge (vertex)-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. Denote by $\mathcal{G}_d(n)$ ($\mathcal{G'}_d(n)$) the set of all graphs of order $n$ with rainbow (vertex) connection number $d$, and define $e_d(n)=\min\{e(G)\,|\, G\in \mathcal{G}_d(n)\}$ ($e_d'(n)=\min\{e(G)\,|\, G\in \mathcal{G'}_d(n)\}$), where $e(G)$ denotes the number of edges in $G$. In this paper, we investigate the bounds of $e_2(n)$ and get the exact asymptotic value. i.e., $\displaystyle \lim_{n\rightarrow \infty}\frac{e_2(n)}{n\log_2 n}=1$. Meanwhile, we obtain $e'_d(n)=n-1$ for $d\geq 2$, and the equality holds if and only if $G$ is such a graph such that deleting all leaves of $G$ results in a tree of order $d$., Comment: 8 pages