Search

Let G be a connected graph and S ⊆ V (G) with | S | ≥ 2. A tree T in G is called an S -tree if S ⊆ V (T). Two S -trees T 1 and T 2 are internally disjoint if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S. For an integer k ≥ 2 , the generalized k -connectivity of a graph G , denoted by κ k (G) , is defined as κ k (G) = min { κ G (S) : S ⊆ V (G) and | S | = k } , where κ G (S) denotes the maximum number of pairwise internally disjoint S -trees in G. The generalized connectivity is a generalization of traditional connectivity. Let G n be the class of connected graphs of order n and let f (n , k , t) = min G ∈ G n { | E (G) | : κ k (G) = t }. In this paper, we prove f (n , k , t) ≥ ⌈ t (t + 2) 2 t + 2 n ⌉ for 4 ≤ k ≤ n and 1 ≤ t ≤ n − ⌈ k 2 ⌉. In particular, the lower bound is sharp when k = 4 and t = 2 (i.e., we explicitly provide a family of graphs fulfilling the bound in this case), improving the known results of Sun et al. (2021). [ABSTRACT FROM AUTHOR]

Given a connected graph G and S ⊆ V (G) with | S | ≥ 2 , an S -tree is a such subgraph T = (V ′ , E ′) of G that is a tree with S ⊆ V ′ . Two S -trees T and T ′ are edge-disjoint if E (T) ∩ E (T ′) = ∅. Let λ G (S) be the maximum size of a set of edge-disjoint S -trees in G. The λ k -connectivity of G is defined as λ k (G) = min { λ G (S) : S ⊆ V (G) , | S | = k }. In this paper, we first show some structural properties of edge-disjoint S -trees by Fan Lemma and König-ore Formula. Then, the λ 4 -connectivity of the Cartesian product of trees is determined. That is, let T n 1 , T n 2 , ... , T n k be trees, then λ 4 (T n 1 □ T n 1 ⋯ □ T n k ) = k if | V (T n i ) | ≥ 4 for each i ∈ { 1 , 2 , ... , k } , otherwise λ 4 (T n 1 □ T n 2 □ ⋯ □ T n k ) = k − 1. As corollaries, λ 4 -connectivity for some graph classes such as hypercubes and meshes can be obtained directly. [ABSTRACT FROM AUTHOR]

Let S be a set of at least two vertices in a graph G. A subtree T of G is an S -Steiner tree if S ⊆ V (T). Two S -Steiner trees T 1 and T 2 are internally disjoint (resp. edge-disjoint) if E (T 1) ∩ E (T 2) = 0̸ and V (T 1) ∩ V (T 2) = S (resp. E (T 1) ∩ E (T 2) = 0̸). Let κ G (S) (resp. λ G (S)) be the maximum number of internally disjoint (resp. edge-disjoint) S -Steiner trees in G , and let κ k (G) (resp. λ k (G)) be the minimum κ G (S) (resp. λ G (S)) for S ranges over all k -subsets of V (G). It is well-known that the connectivity of the line graph of a graph G is closely related to the edge-connectivity of G. Chartrand et al., Li et al., and Li et al. showed that κ k (L (G)) ≥ λ k (G) for k = 2 , 3 , 4 , respectively. In [Discrete Math. 341(2018), 1945–1951.], Li et al. also proposed the following conjecture: κ k (L (G)) ≥ λ k (G) for integer k ≥ 2 and a graph G with at least k vertices. In this paper, we show that κ k (L (G)) ≥ λ k (G) − m a d (G) 2 2 for general k , where m a d (G) is the maximum average degree of a graph G. We also show that κ k (L (G)) ≥ λ k (G) − r 2 2 for any integers k and r such that k ≤ r 2 . Finally, we show that the conjecture holds for k = 5 , and the conjecture holds for the wheel graph and the complete bipartite graph K 3 , n. [ABSTRACT FROM AUTHOR]

The k-forcing number of a graph G, denoted by F k (G) , was introduced by Amos et al. It is a generalization of the zero forcing number of a graph G, denoted by Z(G). Amos et al. proved that for a connected graph G of order n with maximum degree Δ ≥ 2 , Z (G) = F 1 (G) ≤ (Δ - 2) n + 2 Δ - 1 , and this inequality is sharp. Moreover, they posed a conjecture that Z (G) = F 1 (G) = (Δ - 2) n + 2 Δ - 1 if and only if G = C n , G = K Δ + 1 or G = K Δ , Δ . In this paper, we prove that this conjecture is true. Moreover, we point out a mistake in their paper and get a stronger result which shows that F n - 1 (G) = 1 if and only if G is connected and F k (G) = n - k if and only if G = K n for k ≤ n - 2 . [ABSTRACT FROM AUTHOR]

Let S be a set of at least two vertices in a graph G . A subtree T of G is a S -Steiner tree if S ⊆ V ( T ) . Two S -Steiner trees T 1 and T 2 are edge-disjoint (resp. internally vertex-disjoint ) if E ( T 1 ) ∩ E ( T 2 ) = ∅ (resp. E ( T 1 ) ∩ E ( T 2 ) = ∅ and V ( T 1 ) ∩ V ( T 2 ) = S ). Let λ G ( S ) (resp. κ G ( S ) ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) S -Steiner trees in G , and let λ k ( G ) (resp. κ k ( G ) ) be the minimum λ G ( S ) (resp. κ G ( S ) ) for S ranges over all k -subset of V ( G ) . Kriesell conjectured that if λ G ( { x , y } ) ≥ 2 k for any x , y ∈ S , then λ G ( S ) ≥ k . He proved that the conjecture holds for | S | = 3 , 4 . In this paper, we give a short proof of Kriesell’s Conjecture for | S | = 3 , 4 , and also show that λ k ( G ) ≥ 1 k − 1 k ℓ 2 (resp. κ k ( G ) ≥ 1 k − 1 k ℓ 2 ) if λ ( G ) ≥ ℓ (resp. κ ( G ) ≥ ℓ ) in G , where k = 3 , 4 . Moreover, we also study the relation between κ k ( L ( G ) ) and λ k ( G ) , where L ( G ) is the line graph of G . [ABSTRACT FROM AUTHOR]

A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. An edge-colored graph G is rainbow connected if every two distinct vertices are connected by a rainbow path. The rainbow connection number r c ( G ) of G is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we study bounds of rainbow connection number of some graph operations, such as the union of two graphs, adding edges, deleting edges, and adding vertices and edges. Moreover, we also study the following extremal problem. Let k and n be two integers such that 1 ≤ k ≤ ℓ < n . Find the smallest integer f ( n , k , ℓ ) such that for each graph G of order n and diameter k , there exists an edge set F ⊆ E ( G ¯ ) satisfying | F | ≤ f ( n , k , ℓ ) and r c ( G + F ) ≤ ℓ . [ABSTRACT FROM AUTHOR]

A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc( G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that $${\text{trc(G) = 3 if}}\left( {\begin{array}{*{20}{c}} {n - 1} \\ 2 \end{array}} \right) + 1 \leqslant \left| {{\text{E(G)}}} \right| \leqslant \left( {\begin{array}{*{20}{c}} n \\ 2 \end{array}} \right) - 1$$ , and $${\text{trc(G)}} \leqslant {\text{6 if }}\left| {{\text{E(G)}}} \right| \geqslant \left( {\begin{array}{*{20}{c}} {n - 2} \\ 2 \end{array}} \right) + 2$$ . Next, we investigate the total rainbow connection numbers of graphs G with | V( G)| = n, diam( G) ≥ 2, and clique number ω( G) = n − s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31(2): 313-320] is not completely correct, and we provide a complete result for this theorem. [ABSTRACT FROM AUTHOR]

The generalized k -connectivity κ k ( G ) of a graph G , which was introduced by Chartrand et al. (1984), is a generalization of the concept of vertex connectivity. For this generalization, the generalized 2-connectivity κ 2 ( G ) of a graph G is exactly the connectivity κ ( G ) of G . In this paper, let G be a connected graph of order n and let H be a 2-connected graph. For Cartesian product, we show that κ 3 ( G □ H ) ≥ κ 3 ( G ) + 1 if κ ( G ) = κ 3 ( G ) ; κ 3 ( G □ H ) ≥ κ 3 ( G ) + 2 if κ ( G ) > κ 3 ( G ). Moreover, above bounds are sharp. As an example, we show that κ 3 ( C n 1 □ C n 2 □ ⋯ C n k ︷ k ) = 2 k − 1 , where C n i is a cycle. For lexicographic product, we prove that κ 3 ( H ∘ G ) ≥ max { 3 δ ( G ) + 1 , ⌈ 3 n + 1 2 ⌉ } if δ ( G ) < 2 n − 1 3 , and κ 3 ( H ∘ G ) = 2 n if δ ( G ) ≥ 2 n − 1 3 . [ABSTRACT FROM AUTHOR]

The spanning-tree packing number of a graph G is the maximum number of edge-disjoint spanning trees contained in G . In this paper, we obtain a sharp lower bound for the spanning-tree packing number of lexicographic product graphs. [ABSTRACT FROM AUTHOR]

An edge-colored graph G, where adjacent edges may have the same color, is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. A graph G is d-rainbow connected if one can use d colors to make G rainbow connected. For integers n and d let t( n, d) denote the minimum size (number of edges) in d-rainbow connected graphs of order n. Schiermeyer got some exact values and upper bounds for t( n, d). However, he did not present a lower bound of t( n, d) for $${3 \leq d < \lceil\frac{n}{2}\rceil}$$ . In this paper, we improve his lower bound of t( n, 2), and get a lower bound of t( n, d) for $${3 \leq d < \lceil\frac{n}{2}\rceil}$$ . [ABSTRACT FROM AUTHOR]

Abstract: A path in an edge-colored graph , where adjacent edges may have the same color, is a rainbow path if no two edges of the path are colored the same. The rainbow connection number of is the minimum integer for which there exists a -edge-coloring of such that any two distinct vertices of are connected by a rainbow path. It is known that for a graph with diameter 2, deciding if is NP-Complete. In particular, computing is NP-hard. So, it is interesting to know the upper bound of for such a graph . In this paper, we show that if is a bridgeless graph with diameter 2, and that if is a connected graph with diameter 2 and has bridges, where . [Copyright &y& Elsevier]

Abstract: A path in an edge-colored graph , whose adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number of is the minimum integer for which there exists an -edge-coloring of such that every two distinct vertices of are connected by a rainbow path. The strong rainbow connection number of is the minimum integer for which there exists an -edge-coloring of such that every two distinct vertices and of are connected by a rainbow path of length . In this paper, we give upper and lower bounds of the (strong) rainbow connection numbers of Cayley graphs on Abelian groups. Moreover, we determine the (strong) rainbow connection numbers of some special cases. [Copyright &y& Elsevier]

Abstract: Let be a graph. Determining the minimum and/or maximum size ( ) of graphs with some given parameters is a classic extremal problem in graph theory. For a graph and , we denote the edge–degree of . In this paper, we obtain a lower bound for the minimum size of graphs with a given order , a given minimum degree and a given minimum edge–degree . Moreover, we characterize the extremal graphs for . As an application, we characterize some kinds of minimum restricted edge connected graphs. [Copyright &y& Elsevier]