Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "trees" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 34
Tytuł:
On Independent [1, 2]-Sets in Trees
Autorzy:
Aleid, Sahar A.
Cáceres, José
Puertas, María Luz
Powiązania:
https://bibliotekanauki.pl/articles/31342284.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
independence
spanning trees
excellent trees
Opis:
An [1, k]-set S in a graph G is a dominating set such that every vertex not in S has at most k neighbors in it. If the additional requirement that the set must be independent is added, the existence of such sets is not guaranteed in every graph. In this paper we solve some problems previously posed by other authors about independent [1, 2]-sets. We provide a necessary condition for a graph to have an independent [1, 2]-set, in terms of spanning trees, and we prove that this condition is also sufficient for cactus graphs. We follow the concept of excellent tree and characterize the family of trees such that any vertex belongs to some independent [1, 2]-set. Finally, we describe a linear algorithm to decide whether a tree has an independent [1, 2]-set. This algorithm can be easily modified to obtain the cardinality of a smallest independent [1, 2]-set of a tree.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 645-660
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Completely Independent Spanning Trees in (Partial) k-Trees
Autorzy:
Matsushita, Masayoshi
Otachi, Yota
Araki, Toru
Powiązania:
https://bibliotekanauki.pl/articles/31339419.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
completely independent spanning trees
partial k-trees
Opis:
Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that ⌈k/2⌉ ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {⌈k/2⌉, . . ., k − 1}, there exist infinitely many k-trees G such that cist(G) = p. Finally we consider algorithmic aspects for computing cist(G). Using Courcelle’s theorem, we show that there is a linear-time algorithm that computes cist(G) for a partial k-tree, where k is a fixed constant.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 427-437
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Arbitrarily vertex decomposable caterpillars with four or five leaves
Autorzy:
Cichacz, Sylwia
Görlich, Agnieszka
Marczyk, Antoni
Przybyło, Jakub
Woźniak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/743967.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
arbitrarily vertex decomposable graphs
trees
caterpillars
star-like trees
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 291-305
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Smallest Harmonic Index of Trees with Given Maximum Degree
Autorzy:
Rasi, Reza
Sheikholeslami, Seyed Mahmoud
Powiązania:
https://bibliotekanauki.pl/articles/31342320.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
harmonic index
trees
Opis:
The harmonic index of a graph G, denoted by H(G), is defined as the sum of weights 2/[d(u) + d(v)] over all edges uv of G, where d(u) denotes the degree of a vertex u. In this paper we establish a lower bound on the harmonic index of a tree T.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 499-513
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Autorzy:
Azarija, Jernej
Powiązania:
https://bibliotekanauki.pl/articles/30098147.pdf
Data publikacji:
2013-09-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cartesian product graphs
spanning trees
number of spanning trees
inequality
Opis:
Let $ G_1 $ and $ G_2 $ be simple graphs and let $ n_1 = |V (G_1)| $, $ m_1 = |E(G_1)| $ , $ n_2 = |V (G_2)|$ and $ m_2 = |E(G_2)|$. In this paper we derive sharp upper and lower bounds for the number of spanning trees $ \tau $ in the Cartesian product $ G_1 \square G_2 $ of $ G_1 $ and $ G_2 $. We show that: $$ \tau (G_1 \square G_2 ) \geq \frac{2(n_1-1)(n_2-1)}{n_1 n_2} (\tau (G_1) n_1 )^\frac{n_2+1}{2} (\tau(G_2)n_2)^\frac{n_1+1}{2} $$ and $$ \tau(G_1 \square G_2 ) \leq \tau (G_1) \tau (G_2) \left[ \frac{2m_1}{n_1-1} + \frac{2m_2}{n_2-1} \right]^{(n_1 - 1)(n_2 -1)} . $$ We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in $ K_{n_1} \square K_{n_2} $ which turns out to be $ n_1^{n_1-2} n_2^{n_2-2} (n_1 + n_2 )^{(n_1-1)(n_2-1)} $.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 785-790
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the dominator colorings in trees
Autorzy:
Merouane, Houcine
Chellali, Mustapha
Powiązania:
https://bibliotekanauki.pl/articles/743280.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominator coloring
domination
trees
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 677-683
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree
Autorzy:
Henning, Michael A.
Marcon, Alister J.
Powiązania:
https://bibliotekanauki.pl/articles/31341173.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
semitotal domination
trees
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 71-93
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with equal domination and 2-distance domination numbers
Autorzy:
Raczek, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/743916.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
trees
unicyclic graphs
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 375-385
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Unique Minimum Dominating Sets in Some Cartesian Product Graphs
Autorzy:
Hedetniemi, Jason T.
Powiązania:
https://bibliotekanauki.pl/articles/31339313.pdf
Data publikacji:
2015-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
vertex domination
graph products
trees
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 4; 615-628
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with Large Generalized (Edge-)Connectivity
Autorzy:
Li, Xueliang
Mao, Yaping
Powiązania:
https://bibliotekanauki.pl/articles/31340594.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
(edge-)connectivity
Steiner tree
internally disjoint trees
edge-disjoint trees
packing
generalized (edge-)connectivity
Opis:
The generalized $k$-connectivity $ \kappa_k (G) $ of a graph $G$, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized $k$-edge-connectivity $ \lambda_k (G)$. In this paper, graphs of order $n$ such that $ \kappa_k (G) = n - k/2 - 1 $ and $ \lambda_k (G) = n - k/2 - 1 $ for even $k$ are characterized.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 931-958
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterization of trees with equal 2-domination number and domination number plus two
Autorzy:
Chellali, Mustapha
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743587.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
2-domination number
domination number
trees
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 4; 687-697
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Cyclic decompositions of complete graphs into spanning trees
Autorzy:
Froncek, Dalibor
Powiązania:
https://bibliotekanauki.pl/articles/744515.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph factorization
graph labelling
spanning trees
Opis:
We examine decompositions of complete graphs with an even number of vertices, $K_{2n}$, into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 2; 345-353
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
End Simplicial Vertices in Path Graphs
Autorzy:
Gutierrez, Marisa
Tondato, Silvia B.
Powiązania:
https://bibliotekanauki.pl/articles/31340940.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chordal graphs
clique trees
path graphs
Opis:
A graph is a path graph if there is a tree, called UV -model, whose vertices are the maximal cliques of the graph and for each vertex x of the graph the set of maximal cliques that contains it induces a path in the tree. A graph is an interval graph if there is a UV -model that is a path, called an interval model. Gimbel [3] characterized those vertices in interval graphs for which there is some interval model where the interval corresponding to those vertices is an end interval. In this work, we give a characterization of those simplicial vertices x in path graphs for which there is some UV -model where the maximal clique containing x is a leaf in this UV -model.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 393-408
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds On The Disjunctive Total Domination Number Of A Tree
Autorzy:
Henning, Michael A.
Naicker, Viroshan
Powiązania:
https://bibliotekanauki.pl/articles/31341124.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
disjunctive total domination
trees
Opis:
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, $ \gamma_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, $ \gamma_t^d (G) $, is the minimum cardinality of such a set. We observe that $ \gamma_t^d (G) \ge \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 $ \mathcal{l} $ leaves and $s$ support vertices, then $ 2(n−\mathcal{l}+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 $ \gamma_t(T) // \gamma_t^d (T) <2 $ and this bound is asymptotically tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 153-171
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with Unique Maximum Packing of Closed Neighborhoods
Autorzy:
Božović, Dragana
Peterin, Iztok
Powiązania:
https://bibliotekanauki.pl/articles/32304193.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
unique maximum packing
closed neighborhoods
trees
Opis:
A packing of a graph G is a subset P of the vertex set of G such that the closed neighborhoods of any two distinct vertices of P do not intersect. We study graphs with a unique packing of the maximum cardinality. We present several general properties for such graphs. These properties are used to characterize the trees with a unique maximum packing. Two characterizations are presented where one of them is inductive based on five operations.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 779-797
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 34

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies