Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 20

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  trees
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

On Closed Modular Colorings of Trees

100%
Phinezy B., Zhang P.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
411-428
EN
Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood of v. Then c is called a closed modular k-coloring if c′(u) 6= c′(v) in Zk for all pairs u, v of adjacent vertices that are not true twins. The minimum k for which G has a closed modular k-coloring is the closed modular chromatic number mc(G) of G. The closed modular chromatic number is investigated for trees and determined for several classes of trees. For each tree T in these classes, it is shown that mc(T) = 2 or mc(T) = 3. A closed modular k-coloring c of a tree T is called nowhere-zero if c(x) 6= 0 for each vertex x of T. It is shown that every tree of order 3 or more has a nowhere-zero closed modular 4-coloring.
2
Content available remote

Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees

100%
Chellali M., Rad N. J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
337-346
EN
A Roman dominating function (RDF) on a graph G = (V,E) is a function f : V −→ {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that R(G) strongly equals iR(G), denoted by R(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this paper we provide a constructive characterization of trees T with R(T) ≡ iR(T).
3
Content available remote

On Unique Minimum Dominating Sets in Some Cartesian Product Graphs

100%
Hedetniemi J. T.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
615-628
EN
Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.
4
Content available remote

Total Domination Multisubdivision Number of a Graph

100%
Avella-Alaminos D., Dettlaff M., Lemańska M., Zuazua R.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
315-327
EN
The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msdγt (G) of a graph G and we show that for any connected graph G of order at least two, msdγt (G) ≤ 3. We show that for trees the total domination multisubdi- vision number is equal to the known total domination subdivision number. We also determine the total domination multisubdivision number for some classes of graphs and characterize trees T with msdγt (T) = 1.
5
Content available remote

Bounds On The Disjunctive Total Domination Number Of A Tree

100%
Henning M. A., Naicker V.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
153-171
EN
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) $\gamma _t^d (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G) $\gamma _t^d (G) \le \gamma _t (G)$ . A leaf of G is a vertex of degree 1, while a support vertex of G is a vertex adjacent to a leaf. We show that if T is a tree of order n with ℓ leaves and s support vertices, then [...] 2(n−ℓ+3)/5≤γtd(T)≤(n+s−1)/2 $2(n - \ell + 3)/5 \le \gamma _t^d (T) \le (n + s - 1)/2$ and we characterize the families of trees which attain these bounds. For every tree T, we show have [...] γt(T)/γtd(T)<2 $\gamma _t (T)/\gamma _t^d (T) < 2$ and this bound is asymptotically tight.
6
Content available remote

Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

100%
Henning M. A., Marcon A. J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
71-93
EN
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G) ≤ γt2(G) ≤ γt(G). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Note about sequences of extrema \((A,2B)\)-edge coloured trees

100%
Bednarz U., Włoch I.
Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
|
2017
|
tom 71
|
nr 2
EN
In this paper we determine successive extremal trees with respect to the number of all \((A,2B)\)-edge colourings.
8
Content available remote

Harmonic functions and Hardy spaces on trees with boundaries

100%
Pytlik T.
Colloquium Mathematicum
|
1992
|
tom 63
|
nr 2
263-272
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On locating and differentiating-total domination in trees

100%
Chellali M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
383-392
EN
A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γₜ^L(G)$ and $γₜ^D(G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total dominating set of G, respectively. We show that for a nontrivial tree T of order n, with l leaves and s support vertices, $γₜ^L(T) ≥ max{2(n+l-s+1)/5,(n+2-s)/2}$, and for a tree of order n ≥ 3, $γₜ^D(T) ≥ 3(n+l-s+1)/7$, improving the lower bounds of Haynes, Henning and Howard. Moreover we characterize the trees satisfying $γₜ^L(T) = 2(n+l- s+1)/5$ or $γₜ^D(T) = 3(n+l-s+1)/7$.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Trees with equal restrained domination and total restrained domination numbers

100%
Raczek J.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
83-91
EN
For a graph G = (V,E), a set D ⊆ V(G) is a total restrained dominating set if it is a dominating set and both ⟨D⟩ and ⟨V(G)-D⟩ do not have isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. A set D ⊆ V(G) is a restrained dominating set if it is a dominating set and ⟨V(G)-D⟩ does not contain an isolated vertex. The cardinality of a minimum restrained dominating set in G is the restrained domination number. We characterize all trees for which total restrained and restrained domination numbers are equal.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Characterization of trees with equal 2-domination number and domination number plus two

100%
Chellali M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
687-697
EN
Let G = (V(G),E(G)) be a simple graph, and let k be a positive integer. A subset D of V(G) is a k-dominating set if every vertex of V(G) - D is dominated at least k times by D. The k-domination number γₖ(G) is the minimum cardinality of a k-dominating set of G. In [5] Volkmann showed that for every nontrivial tree T, γ₂(T) ≥ γ₁(T)+1 and characterized extremal trees attaining this bound. In this paper we characterize all trees T with γ₂(T) = γ₁(T)+2.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the dominator colorings in trees

100%
Merouane H., Chellali M.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
677-683
EN
In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates all vertices of at least one color class (possibly its own class). The dominator chromatic number $χ_d(G)$ is the minimum number of color classes in a dominator coloring of G. Gera showed that every nontrivial tree T satisfies $γ(T)+1 ≤ χ_d(T) ≤ γ(T)+2$. In this note we characterize nontrivial trees T attaining each bound.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graphs with equal domination and 2-distance domination numbers

100%
Raczek J.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
375-385
EN
Let G = (V,E) be a graph. The distance between two vertices u and v in a connected graph G is the length of the shortest (u-v) path in G. A set D ⊆ V(G) is a dominating set if every vertex of G is at distance at most 1 from an element of D. The domination number of G is the minimum cardinality of a dominating set of G. A set D ⊆ V(G) is a 2-distance dominating set if every vertex of G is at distance at most 2 from an element of D. The 2-distance domination number of G is the minimum cardinality of a 2-distance dominating set of G. We characterize all trees and all unicyclic graphs with equal domination and 2-distance domination numbers.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Arbitrarily vertex decomposable caterpillars with four or five leaves

100%
Cichacz S., Görlich A., Marczyk A., Przybyło J., Woźniak M.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
291-305
EN
A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ {1,...,k}, $V_i$ induces a connected subgraph of G on $a_i$ vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable caterpillars with four leaves. We also describe two families of arbitrarily vertex decomposable trees with maximum degree three or four.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Trees with equal 2-domination and 2-independence numbers

100%
Chellali M., Meddah N.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
263-270
EN
Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
16
Content available remote

Some Results on Maps That Factor through a Tree

88%
Züst R.
Analysis and Geometry in Metric Spaces
|
2015
|
tom 3
|
nr 1
EN
We give a necessary and sufficient condition for a map deffned on a simply-connected quasi-convex metric space to factor through a tree. In case the target is the Euclidean plane and the map is Hölder continuous with exponent bigger than 1/2, such maps can be characterized by the vanishing of some integrals over winding number functions. This in particular shows that if the target is the Heisenberg group equipped with the Carnot-Carathéodory metric and the Hölder exponent of the map is bigger than 2/3, the map factors through a tree.
17
Content available remote

Domination Game Critical Graphs

88%
Bujtás C., Klavžar S., Košmrlj G.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
781-796
EN
The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γg(G), named the game domination number. Here we study the γg-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize γg-critical graphs with γg = 2 and with γg = 3, moreover for each n we identify the (infinite) class of all γg-critical ones among the nth powers CnN of cycles. Along the way we determine γg(CnN) for all n and N. Results of a computer search for γg-critical trees are presented and several problems and research directions are also listed.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

About uniquely colorable mixed hypertrees

75%
Niculitsa A., Voloshin V.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
81-91
EN
A mixed hypergraph is a triple 𝓗 = (X,𝓒,𝓓) where X is the vertex set and each of 𝓒, 𝓓 is a family of subsets of X, the 𝓒-edges and 𝓓-edges, respectively. A k-coloring of 𝓗 is a mapping c: X → [k] such that each 𝓒-edge has two vertices with the same color and each 𝓓-edge has two vertices with distinct colors. 𝓗 = (X,𝓒,𝓓) is called a mixed hypertree if there exists a tree T = (X,𝓔) such that every 𝓓-edge and every 𝓒-edge induces a subtree of T. A mixed hypergraph 𝓗 is called uniquely colorable if it has precisely one coloring apart from permutations of colors. We give the characterization of uniquely colorable mixed hypertrees.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Global alliances and independence in trees

75%
Chellali M., Haynes T.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
19-27
EN
A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such an alliance. We determine relationships among these four parameters and the vertex independence number for trees.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Tree-like isometric subgraphs of hypercubes

63%
Brešar B., Imrich W., Klavžar S.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
227-240
EN
Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.