Temat: trees - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: On Independent [1, 2]-Sets in Trees
Autorzy:: Aleid, Sahar A.
Cáceres, José
Puertas, María Luz
Tematy:: domination
independence
spanning trees
excellent trees; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342284.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Completely Independent Spanning Trees in (Partial) k-Trees
Autorzy:: Matsushita, Masayoshi
Otachi, Yota
Araki, Toru
Tematy:: completely independent spanning trees
partial k-trees; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31339419.pdf Link otwiera się w nowym oknie
Opis:: Two spanning trees T₁ and T₂ of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T₁ and T₂ 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: Note: Sharp Upper and Lower Bounds on the Number of Spanning Trees in Cartesian Product of Graphs
Autorzy:: Azarija, Jernej
Tematy:: Cartesian product graphs
spanning trees
number of spanning trees
inequality; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30098147.pdf Link otwiera się w nowym oknie
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)} $.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: Arbitrarily vertex decomposable caterpillars with four or five leaves
Autorzy:: Cichacz, Sylwia
Görlich, Agnieszka
Marczyk, Antoni
Przybyło, Jakub
Woźniak, Mariusz
Tematy:: arbitrarily vertex decomposable graphs
trees
caterpillars
star-like trees; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743967.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: The Smallest Harmonic Index of Trees with Given Maximum Degree
Autorzy:: Rasi, Reza
Sheikholeslami, Seyed Mahmoud
Tematy:: harmonic index
trees; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31342320.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: On the dominator colorings in trees
Autorzy:: Merouane, Houcine
Chellali, Mustapha
Tematy:: dominator coloring
domination
trees; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743280.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree
Autorzy:: Henning, Michael A.
Marcon, Alister J.
Tematy:: domination
semitotal domination
trees; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31341173.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: Graphs with Large Generalized (Edge-)Connectivity
Autorzy:: Li, Xueliang
Mao, Yaping
Tematy:: (edge-)connectivity
Steiner tree
internally disjoint trees
edge-disjoint trees
packing
generalized (edge-)connectivity; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31340594.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Graphs with equal domination and 2-distance domination numbers
Autorzy:: Raczek, Joanna
Tematy:: domination number
trees
unicyclic graphs; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743916.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: On Unique Minimum Dominating Sets in Some Cartesian Product Graphs
Autorzy:: Hedetniemi, Jason T.
Tematy:: vertex domination
graph products
trees; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31339313.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "trees" wg kryterium: Temat