Temat: edge-subdivision - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
Autorzy:: Dettlaff, M.
Raczek, J.
Yero, I. G.
Powiązania:: https://bibliotekanauki.pl/articles/255785.pdf
Data publikacji:: 2016
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: domination
paired domination
independent domination
edge subdivision
edge multisubdivision
corona graph
Opis:: Given a graph G = (V, E), the subdivision of an edge e = uv ∈ E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions which must be done in one edge such that the domination number increases. Moreover, the concepts of paired domination and independent domination subdivision (respectively multisubdivision) numbers are denned similarly. In this paper we study the domination, paired domination and independent domination (subdivision and multisubdivision) numbers of the generalized corona graphs.
Źródło:: Opuscula Mathematica; 2016, 36, 5; 575-588
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: Color-bounded hypergraphs, V: host graphs and subdivisions
Autorzy:: Bujtás, Csilla
Tuza, Zsolt
Voloshin, Vitaly
Powiązania:: https://bibliotekanauki.pl/articles/743863.pdf
Data publikacji:: 2011
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: mixed hypergraph
color-bounded hypergraph
vertex coloring
arboreal hypergraph
hypertree
feasible set
host graph
edge subdivision
Opis:: A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = {E₁,...,Eₘ}, together with integers $s_i$ and $t_i$ satisfying $1 ≤ s_i ≤ t_i ≤ |E_i|$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_i$ satisfies $s_i ≤ |φ(E_i)| ≤ t_i$. The hypergraph ℋ is colorable if it admits at least one proper coloring.
We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each $E_i$ induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀.
The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.
Źródło:: Discussiones Mathematicae Graph Theory; 2011, 31, 2; 223-238
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "edge-subdivision" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język