The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Graphs with rainbow connection number two”

A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected

Shiying Wang, Meiyu Wang, Lei Zhang (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For a subset S of edges in a connected graph G, S is a k-restricted edge cut if G − S is disconnected and every component of G − S has at least k vertices. The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξk(G) = min|[X, X̄]| : |X| = k, G[X] is connected, where X̄ = V (G). A graph G is super k-restricted edge connected if every minimum k-restricted edge cut of G isolates a component of order exactly k. Let...

Kaleidoscopic Colorings of Graphs

Gary Chartrand, Sean English, Ping Zhang (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For an r-regular graph G, let c : E(G) → [k] = 1, 2, . . . , k, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular...

Contractible edges in some k -connected graphs

Yingqiu Yang, Liang Sun (2012)

Czechoslovak Mathematical Journal

Similarity:

An edge e of a k -connected graph G is said to be k -contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k -connected. In 2002, Kawarabayashi proved that for any odd integer k ≥ 5 , if G is a k -connected graph and G contains no subgraph D = K 1 + ( K 2 ∪ K 1 , 2 ) , then G has a k -contractible edge. In this paper, by generalizing this result, we prove that...

The contractible subgraph of 5 -connected graphs

Chengfu Qin, Xiaofeng Guo, Weihua Yang (2013)

Czechoslovak Mathematical Journal

Similarity:

An edge e of a k -connected graph G is said to be k -removable if G - e is still k -connected. A subgraph H of a k -connected graph is said to be k -contractible if its contraction results still in a k -connected graph. A k -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k -connected. In this paper, we show that there is a contractible subgraph in a 5 -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex...

Dense Arbitrarily Partitionable Graphs

Rafał Kalinowski, Monika Pilśniak, Ingo Schiermeyer, Mariusz Woźniak (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 | | G | | > n - 4 2 + 12 edges is AP or belongs to few classes of exceptional graphs.

Radio antipodal colorings of graphs

Gary Chartrand, David Erwin, Ping Zhang (2002)

Mathematica Bohemica

Similarity:

A radio antipodal coloring of a connected graph G with diameter d is an assignment of positive integers to the vertices of G , with x ∈ V ( G ) assigned c ( x ) , such that d ( u , v ) + | c ( u ) - c ( v ) | ≥ d for every two distinct vertices u , v of G , where d ( u , v ) is the distance between u and v in G . The radio antipodal coloring number a c ( c ) of a radio antipodal coloring c of G is the maximum color assigned to a vertex of G . The radio antipodal chromatic number a c ( G ) of G is min { a c ( c ) } over all radio antipodal colorings c of G . Radio antipodal chromatic numbers...

Rainbow connection in graphs

Gary Chartrand, Garry L. Johns, Kathleen A. McKeon, Ping Zhang (2008)

Mathematica Bohemica

Similarity:

Let G be a nontrivial connected graph on which is defined a coloring c E ( G ) → { 1 , 2 , ... , k } , k ∈ ℕ , of the edges of G , where adjacent edges may be colored the same. A path P in G is a rainbow path if no two edges of P are colored the same. The graph G is rainbow-connected if G contains a rainbow u - v path for every two vertices u and v of G . The minimum k for which there exists such a k -edge coloring is the rainbow connection number r c ( G ) of G . If for every pair u , v of distinct vertices, G contains a rainbow u - v geodesic,...