Search

The $g$-extra connectivity is an important parameter to measure the ability of tolerance and reliability of interconnection networks. Given a connected graph $G=(V,E)$ and a non-negative integer $g$, a subset $S\subseteq V$ is called a $g$-extra cut of $G$ if $G-S$ is disconnected and every component of $G-S$ has at least $g+1$ vertices. The cardinality of the minimum $g$-extra cut is defined as the $g$-extra connectivity of $G$, denoted by $\kappa_g(G)$. In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph $G$ into a new graph $\mu(G)$, which is called the Mycielskian of $G$. This paper investigates the relationship of the g-extra connectivity of the Mycielskian $\mu(G)$ and the graph $G$, moreover, show that $\kappa_{2g+1}(\mu(G))=2\kappa_{g}(G)+1$ for $g\geq 1$ and $\kappa_{g}(G)\leq min\{g+1, \lfloor\frac{n}{2}\rfloor\}$.

Given a graph $G$ and a positive integer $k$, the \emph{Gallai-Ramsey number} is defined 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 obtain general upper and lower bounds on the Gallai-Ramsey numbers for books $B_{m} = K_{2} + \overline{K_{m}}$ and prove sharp results for $m \leq 5$., Comment: 24 pages, 4 figures

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

A path $P$ in an edge-colored graph $G$ is called \emph{a proper path} if no two adjacent edges of $P$ are colored the same, and $G$ is \emph{proper connected} if every two vertices of $G$ are connected by a proper path in $G$. The \emph{proper connection number} of a connected graph $G$, denoted by $pc(G)$, is the minimum number of colors that are needed to make $G$ proper connected. In this paper, we study the proper connection number on the lexicographical, strong, Cartesian, and direct product and present several upper bounds for these products of graphs., Comment: 16 pages, 2 figures. arXiv admin note: text overlap with arXiv:1505.01424. text overlap with arXiv:1504.02414 by other authors

The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a \emph{monochromatic path} if all the edges on the path are colored the same. An edge-coloring of $G$ is a \emph{monochromatic connection coloring} ($MC$-coloring, for short) if there is a monochromatic path joining any two vertices in $G$. The \emph{monochromatic connection number}, denoted by $mc(G)$, is defined to be the maximum number of colors used in an $MC$-coloring of a graph $G$. In this paper, we study the monochromatic connection number on the lexicographical, strong, Cartesian and direct product and present several upper and lower bounds for these products of graphs., Comment: 18 pages, 2 figures. arXiv admin note: text overlap with arXiv:1412.7798 by other authors