Temat: edge dominating set - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Edge Dominating Sets and Vertex Covers
Autorzy:: Dutton, Ronald
Klostermeyer, William F.
Powiązania:: https://bibliotekanauki.pl/articles/30146532.pdf
Data publikacji:: 2013-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: edge dominating set
matching
total dominating set
vertex cover
Opis:: Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2013, 33, 2; 437-456
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Dominating Vertex Covers: The Vertex-Edge Domination Problem
Autorzy:: Klostermeyer, William F.
Messinger, Margaret-Ellen
Yeo, Anders
Powiązania:: https://bibliotekanauki.pl/articles/32083812.pdf
Data publikacji:: 2021-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: cubic graph
dominating set
vertex cover
vertex-edge dominating set
Opis:: The vertex-edge domination number of a graph, γ_ve(G), is defined to be the cardinality of a smallest set D such that there exists a vertex cover C of G such that each vertex in C is dominated by a vertex in D. This is motivated by the problem of determining how many guards are needed in a graph so that a searchlight can be shone down each edge by a guard either incident to that edge or at most distance one from a vertex incident to the edge. Our main result is that for any cubic graph G with n vertices, γ_ve(G) ≤ 9n/26. We also show that it is NP-hard to decide if γ_ve(G) = γ(G) for bipartite graph G.
Źródło:: Discussiones Mathematicae Graph Theory; 2021, 41, 1; 123-132
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: M2-edge colorings of dense graphs
Autorzy:: Ivanco, J.
Powiązania:: https://bibliotekanauki.pl/articles/254913.pdf
Data publikacji:: 2016
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: edge coloring
dominating set
dense graphs
Opis:: An edge coloring φ of a graph G is called an Mi-edge coloring if [formula] every vertex v of G, where φ (v) is the set of colors of edges incident with v. Let K1(G) denote the maximum number of colors used in an Mi-edge coloring of G. In this paper we establish some bounds of K.2(G), present some graphs achieving the bounds and determine exact values of K.2(G) for dense graphs.
Źródło:: Opuscula Mathematica; 2016, 36, 5; 603-612
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: On M_f-Edge Colorings of Graphs
Autorzy:: Ivančo, Jaroslav
Onderko, Alfréd
Powiązania:: https://bibliotekanauki.pl/articles/32222570.pdf
Data publikacji:: 2022-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: edge coloring
anti-Ramsey number
dominating set
Opis:: An edge coloring φ of a graph G is called an M_f-edge coloring if |φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let K_f (G) denote the maximum number of colors used in an M_f-edge coloring of G. In this paper we establish some bounds on K_f(G), present some graphs achieving the bounds and determine exact values of K_f(G) for some special classes of graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1075-1088
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: Spanning trees with many or few colors in edge-colored graphs
Autorzy:: Broersma, Hajo
Li, Xueliang
Powiązania:: https://bibliotekanauki.pl/articles/971955.pdf
Data publikacji:: 1997
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: edge-coloring
spanning tree
matroid (intersection)
complexity
NP-complete
NP-hard
polynomial algorithm
(minimum) dominating set
Opis:: Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
Źródło:: Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja