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: 17

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

Wyniki wyszukiwania

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

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Lower bound on the domination number of a tree

100%
Lemańska M.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
165-169
EN
>We prove that the domination number γ(T) of a tree T on n ≥ 3 vertices and with n₁ endvertices satisfies inequality γ(T) ≥ (n+2-n₁)/3 and we characterize the extremal graphs.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On non-z(mod k) dominating sets

80%
Caro Y., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
189-199
EN
For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 1, a subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x ∈ V(G), |N[x]∩D| ≢ z (mod k).For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with z < k and z ≠ 1, that a non-z(mod k) dominating set exist for all trees. Also, it will be shown that for k ≥ 4, z ≥ 1, 2 or 3 that any unicyclic graph contains a non-z(mod k) dominating set. We also give a few special cases of other families of graphs for which these dominating sets must exist.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

2-placement of (p,q)-trees

80%
Orchel B.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
23-36
EN
Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which are not 2-placeable.
4
Content available remote

The Turán Number of the Graph 2P5

80%
Bielak H., Kieliszek S.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
683-694
EN
We give the Turán number ex (n, 2P5) for all positive integers n, improving one of the results of Bushaw and Kettle [Turán numbers of multiple paths and equibipartite forests, Combininatorics, Probability and Computing, 20 (2011) 837-853]. In particular we prove that ex (n, 2P5) = 3n−5 for n ≥ 18.
5
Content available remote

Bounds on the Locating Roman Domination Number in Trees

80%
Jafari Rad N., Rahbani H.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
49-62
EN
A Roman dominating function (or just 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 f is the value f(V (G)) = ∑u∈V(G) f(u). An RDF f can be represented as f = (V0, V1, V2), where Vi = {v ∈ V : f(v) = i} for i = 0, 1, 2. An RDF f = (V0, V1, V2) is called a locating Roman dominating function (or just LRDF) if N(u) ∩ V2 ≠ N(v) ∩ V2 for any pair u, v of distinct vertices of V0. The locating Roman domination number [...] γRL(G) $\gamma _R^L (G)$ is the minimum weight of an LRDF of G. In this paper, we study the locating Roman domination number in trees. We obtain lower and upper bounds for the locating Roman domination number of a tree in terms of its order and the number of leaves and support vertices, and characterize trees achieving equality for the bounds.
6
Content available remote

Characterization Results for theL(2, 1, 1)-Labeling Problem on Trees

80%
Zhang X., Deng K.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
611-622
EN
An L(2, 1, 1)-labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all L(2, 1, 1)-labelings of G is called the L(2, 1, 1)-labeling number of G, denoted by λ2,1,1(G). It was shown by King, Ras and Zhou in [The L(h, 1, 1)-labelling problem for trees, European J. Combin. 31 (2010) 1295–1306] that every tree T has Δ2(T) − 1 ≤ λ2,1,1(T) ≤ Δ2(T), where Δ2(T) = maxuv∈E(T)(d(u) + d(v)). And they conjectured that almost all trees have the L(2, 1, 1)-labeling number attain the lower bound. This paper provides some sufficient conditions for λ2,1,1(T) = Δ2(T). Furthermore, we show that the sufficient conditions we provide are also necessary for trees with diameter at most 6.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A lower bound for the irredundance number of trees

80%
Poschen M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
209-215
EN
Let ir(G) and γ(G) be the irredundance number and domination number of a graph G, respectively. The number of vertices and leaves of a graph G are denoted by n(G) and n₁(G). If T is a tree, then Lemańska [4] presented in 2004 the sharp lower bound γ(T) ≥ (n(T) + 2 - n₁(T))/3. In this paper we prove ir(T) ≥ (n(T) + 2 - n₁(T))/3. for an arbitrary tree T. Since γ(T) ≥ ir(T) is always valid, this inequality is an extension and improvement of Lemańska's result.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Solution to the problem of Kubesa

80%
Meszka M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
375-378
EN
An infinite family of T-factorizations of complete graphs $K_{2n}$, where 2n = 56k and k is a positive integer, in which the set of vertices of T can be split into two subsets of the same cardinality such that degree sums of vertices in both subsets are not equal, is presented. The existence of such T-factorizations provides a negative answer to the problem posed by Kubesa.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Trees with equal total domination and total restrained domination numbers

80%
Chen X.-G., Shiu W., Chen H.-Y.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
59-66
EN
For a graph G = (V,E), a set S ⊆ V(G) is a total dominating set if it is dominating and both ⟨S⟩ has no isolated vertices. The cardinality of a minimum total dominating set in G is the total domination number. A set S ⊆ V(G) is a total restrained dominating set if it is total dominating and ⟨V(G)-S⟩ has no isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. We characterize all trees for which total domination and total restrained domination numbers are the same.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Spectral integral variation of trees

80%
Wang Y., Fan Y.-Z.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
49-58
EN
In this paper, we determine all trees with the property that adding a particular edge will result in exactly two Laplacian eigenvalues increasing respectively by 1 and the other Laplacian eigenvalues remaining fixed. We also investigate a situation in which the algebraic connectivity is one of the changed eigenvalues.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Algorithmic aspects of total-subdomination in graphs

80%
Harris L., Hattingh J., Henning M.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
5-18
EN
Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination number of a tree and also show that the associated decision problem is NP-complete for general graphs.
12
Content available remote

Maximal buttonings of trees

71%
Short I.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
415-420
EN
A buttoning of a tree that has vertices v1, v2, . . . , vn is a closed walk that starts at v1 and travels along the shortest path in the tree to v2, and then along the shortest path to v3, and so forth, finishing with the shortest path from vn to v1. Inspired by a problem about buttoning a shirt inefficiently, we determine the maximum length of buttonings of trees
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total edge irregularity strength of trees

71%
Ivančo J., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 3
449-456
EN
A total edge-irregular k-labelling ξ:V(G)∪ E(G) → {1,2,...,k} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that for every tree T of maximum degree Δ on p vertices tes(T) = max{⎡(p+1)/3⎤,⎡(Δ+1)/2⎤}.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Arboreal structure and regular graphs of median-like classes

61%
Brešar B.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
215-225
EN
We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of the gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph of the graph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional property. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron.
15
Content available remote

The Crossing Numbers of Products of Path with Graphs of Order Six

61%
Klešč M., Petrillová J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
571-582
EN
The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collected
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Parity vertex colouring of graphs

61%
Borowiecki P., Budajová K., Jendrol' S., Krajci S.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
183-195
EN
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the structure of path-like trees

51%
Muntaner-Batle F., Rius-Font M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
249-265
EN
We study the structure of path-like trees. In order to do this, we introduce a set of trees that we call expandable trees. In this paper we also generalize the concept of path-like trees and we call such generalization generalized path-like trees. As in the case of path-like trees, generalized path-like trees, have very nice labeling properties.
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ć.