Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A Note on the Total Detection Numbers of Cycles

100%

Escuadro H. E., Fujie F., Musick C. E.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 2

237-247

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of a detectable labeling c of a graph G is the sum of the labels assigned to the edges in G. The total detection number td(G) of G is defined by td(G) = min{val(c)}, where the minimum is taken over all detectable labelings c of G. We investigate the problem of determining the total detection numbers of cycles.

On Monochromatic Subgraphs of Edge-Colored Complete Graphs

88%

Andrews E., Fujie F., Kolasinski K., Lumduanhom C., Yusko A.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 1

5-22

In a red-blue coloring of a nonempty graph, every edge is colored red or blue. If the resulting edge-colored graph contains a nonempty subgraph G without isolated vertices every edge of which is colored the same, then G is said to be monochromatic. For two nonempty graphs G and H without isolated vertices, the mono- chromatic Ramsey number mr(G,H) of G and H is the minimum integer n such that every red-blue coloring of Kn results in a monochromatic G or a monochromatic H. Thus, the standard Ramsey number of G and H is bounded below by mr(G,H). The monochromatic Ramsey numbers of graphs belonging to some common classes of graphs are studied. We also investigate another concept closely related to the standard Ram- sey numbers and monochromatic Ramsey numbers of graphs. For a fixed integer n ≥ 3, consider a nonempty subgraph G of order at most n con- taining no isolated vertices. Then G is a common monochromatic subgraph of Kn if every red-blue coloring of Kn results in a monochromatic copy of G. Furthermore, G is a maximal common monochromatic subgraph of Kn if G is a common monochromatic subgraph of Kn that is not a proper sub- graph of any common monochromatic subgraph of Kn. Let S(n) and S*(n) be the sets of common monochromatic subgraphs and maximal common monochromatic subgraphs of Kn, respectively. Thus, G ∈ S(n) if and only if R(G,G) = mr(G,G) ≤ n. We determine the sets S(n) and S*(n) for 3 ≤ n ≤ 8.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Fujie F.

1 Andrews E.

1 Escuadro H. E.

1 Kolasinski K.

1 Lumduanhom C.

1 Musick C. E.

1 Yusko A.

1 2015

1 2014

Wyniki wyszukiwania

A Note on the Total Detection Numbers of Cycles

On Monochromatic Subgraphs of Edge-Colored Complete Graphs