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,...

Maximum Edge-Colorings Of Graphs

Stanislav Jendrol’, Michaela Vrbjarová (2016)

Discussiones Mathematicae Graph Theory

Similarity:

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) χ r ' ( G ) is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 χ r ' ( G ) ≤ 3 for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i...