Search

For a graph G = (V, E) and a set S ⊆ V of at least two vertices, an S-tree is a such subgraph T of G that is a tree with S ⊆ V (T). Two S-trees T1 and T2 are said to be internally disjoint if E(T1) ∩ E(T2) = ∅ and V (T1) ∩ V (T2) = S, and edge-disjoint if E(T1) ∩ E(T2) = ∅. The generalized local connectivity κG(S) (generalized local edge-connectivity λG(S), respectively) is the maximum number of internally disjoint (edge-disjoint, respectively) S-trees in G. For an integer k with 2 ≤ k ≤ n, the generalized k-connectivity (generalized k-edge-connectivity, respectively) is defined as κk(G) = min{κG (S) | S ⊆ V (G), |S| = k} (λk(G) = min{λG(S) | S ⊆ V (G), |S| = k}, respectively).

In 2011, Caro et al. introduced the monochromatic connection of graphs. An edge-coloring of a connected graph $G$ is called a monochromatically connecting (MC-coloring, for short) if there is a monochromatic path joining any two vertices. The monochromatic connection number $\operatorname{mc}(G)$ of a graph $G$ is the maximum integer $k$ such that there is a $k$-edge-coloring, which is an MC-coloring of $G$. Clearly, a monochromatic spanning tree can monochromatically connect any two vertices. So for a graph $G$ of order $n$ and size $m$, $\operatorname{mc}(G) \geq m-n+2$. Caro et al. proved that both triangle-free graphs and graphs of diameter at least three meet the lower bound. ¶ In this paper, we consider the monochromatic connectivity of graphs containing triangles which meet the lower bound too. Also, in order to study the graphs of diameter two, we present the formula for the monochromatic connectivity of join graphs. This will be helpful to solve the problem for graphs of diameter two.

Bollobas and Gyarfas conjectured that for n > 4 (k − 1) every 2-edge-coloring of K n contains a monochromatic k-connected subgraph with at least n − 2k + 2 vertices. Liu, et al. proved that the conjecture holds when n ≥ 13k − 15. In this note, we characterize all the 2-edge-colorings of K n where each monochromatic k-connected subgraph has at most n−2k+2 vertices for n ≥ 13k − 15.

The lower bounds for the size of maximum rainbow matching in properly edge-colored graphs have been studied deeply during the last decades. An edge-coloring of a graph [Formula: see text] is called a strong edge-coloring if each path of length at most three is rainbow. Clearly, the strong edge-coloring is a natural generalization of the proper one. Recently, Babu et al. considered the problem in the strongly edge-colored graphs. In this paper, we introduce a semi-strong edge-coloring of graphs and consider the existence of large rainbow matchings in it.

Let [Formula: see text] be a family of graphs. The anti-Ramsey number [Formula: see text] for [Formula: see text] in the graph [Formula: see text] is the maximum number of colors in an edge coloring of [Formula: see text] that does not have any rainbow copy of any graph in [Formula: see text]. In this paper, we consider the anti-Ramsey number for matchings in regular bipartite graphs and determine its value under several conditions.

Let $G$ be a simple undirected graph. Denote by $\mbox{ mi}(G)$ (respectively, $\mbox{xi}(G)$) the number of maximal (respectively, maximum) independent sets in $G$. In this paper we determine the second largest value of $\mbox{mi}(G)$ for graphs with at most $k$ cycles. Extremal graphs achieving these values are also determined.