Temat: Erdös problem - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Erdős-Gallai-Type Results for Total Monochromatic Connection of Graphs
Autorzy:: Jiang, Hui
Li, Xueliang
Zhang, Yingying
Powiązania:: https://bibliotekanauki.pl/articles/31343240.pdf
Data publikacji:: 2019-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: total-colored graph
total monochromatic connection
Erdős- Gallai-type problem
Opis:: A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A total-coloring of a graph is a total monochromatically-connecting coloring (TMC-coloring, for short) if any two vertices of the graph are connected by a path whose edges and internal vertices have the same color. For a connected graph G, the total monochromatic connection number, denoted by tmc(G), is defined as the maximum number of colors used in a TMC-coloring of G. In this paper, we study two kinds of Erdős-Gallai-type problems for tmc(G) and completely solve them.
Źródło:: Discussiones Mathematicae Graph Theory; 2019, 39, 4; 775-785
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: More on the Rainbow Disconnection in Graphs
Autorzy:: Bai, Xuqing
Chang, Renying
Huang, Zhong
Li, Xueliang
Powiązania:: https://bibliotekanauki.pl/articles/32222544.pdf
Data publikacji:: 2022-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: edge-coloring
edge-connectivity
rainbow disconnection coloring (number)
Erdős-Gallai type problem
Nordhaus-Gaddum type bounds
complexity
NP-hard (complete)
Opis:: Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1185-1204
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "Erdös problem" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język