Displaying similar documents to “The 3-Rainbow Index of a Graph”

Graphs with 3-Rainbow Index n − 1 and n − 2

Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V (G),E(G)) be a nontrivial connected graph of order n with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ N, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree connecting S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of...

Graphs with 4-Rainbow Index 3 and n − 1

Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for every set S of k vertices of V (G) is called the k-rainbow index of G, denoted...

Spanning tree congestion of rook's graphs

Kyohei Kozawa, Yota Otachi (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

Packing Trees Into n-Chromatic Graphs

András Gyárfás (2014)

Discussiones Mathematicae Graph Theory

Similarity:

We show that if a sequence of trees T1, T2, ..., Tn−1 can be packed into Kn then they can be also packed into any n-chromatic graph.

On graceful trees.

Hegde, Suresh Manjanath, Shetty, Sudhakar (2002)

Applied Mathematics E-Notes [electronic only]

Similarity:

Upper Bounds for the Strong Chromatic Index of Halin Graphs

Ziyu Hu, Ko-Wei Lih, Daphne Der-Fen Liu (2018)

Discussiones Mathematicae Graph Theory

Similarity:

The strong chromatic index of a graph G, denoted by χ′s(G), is the minimum number of vertex induced matchings needed to partition the edge set of G. Let T be a tree without vertices of degree 2 and have at least one vertex of degree greater than 2. We construct a Halin graph G by drawing T on the plane and then drawing a cycle C connecting all its leaves in such a way that C forms the boundary of the unbounded face. We call T the characteristic tree of G. Let G denote a Halin graph with...