Temat: conflict-free vertex-connection - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Conflict-Free Vertex-Connections of Graphs
Autorzy:: Li, Xueliang
Zhang, Yingying
Zhu, Xiaoyu
Mao, Yaping
Zhao, Haixing
Jendrol’, Stanislav
Powiązania:: https://bibliotekanauki.pl/articles/31868621.pdf
Data publikacji:: 2020-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: vertex-coloring
conflict-free vertex-connection
2-connected graph
tree
Opis:: A path in a vertex-colored graph is called conflict-free if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be conflict-free vertex-connected if any two vertices of the graph are connected by a conflict-free path. This paper investigates the question: for a connected graph G, what is the smallest number of colors needed in a vertex-coloring of G in order to make G conflict-free vertex-connected. As a result, we get that the answer is easy for 2-connected graphs, and very difficult for connected graphs with more cut-vertices, including trees.
Źródło:: Discussiones Mathematicae Graph Theory; 2020, 40, 1; 51-65
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Conflict-Free Vertex Connection Number at Most 3 and Size of Graphs
Autorzy:: Doan, Trung Duy
Schiermeyer, Ingo
Powiązania:: https://bibliotekanauki.pl/articles/32083899.pdf
Data publikacji:: 2021-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: vertex-colouring
conflict-free vertex-connection number
size of graph
Opis:: A path in a vertex-coloured graph is called conflict-free if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be conflict-free vertex-connected if any two distinct vertices of the graph are connected by a conflict-free vertex-path. The conflict-free vertex-connection number, denoted by $vcfc(G)$, is the smallest number of colours needed in order to make $G$ conflict-free vertex-connected. Clearly, $vcfc(G) ≥ 2$ for every connected graph on $n ≥ 2$ vertices. Our main result of this paper is the following. Let $G$ be a connected graph of order $n$. If $|E(G)|≥\binom{n-6}{2}+7$, then $vcfc(G) ≤ 3$. We also show that $vcfc(G) ≤ k + 3 − t$ for every connected graph $G$ with $k$ cut-vertices and $t$ being the maximum number of cut-vertices belonging to a block of $G$.
Źródło:: Discussiones Mathematicae Graph Theory; 2021, 41, 2; 617-632
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja