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ę "k-tree" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 17
Tytuł:
More on the Minimum Size of Graphs with Given Rainbow Index
Autorzy:
Zhao, Yan
Powiązania:
https://bibliotekanauki.pl/articles/32083808.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Steiner distance
rainbow S -tree
k -rainbow index
Opis:
The concept of k-rainbow index rxk(G) of a connected graph G, introduced by Chartrand et al., is a natural generalization of the rainbow connection number of a graph. Liu introduced a parameter t(n, k, ℓ) to investigate the problems of the minimum size of a connected graph with given order and k-rainbow index at most ℓ and obtained some exact values and upper bounds for t(n, k, ℓ). In this paper, we obtain some exact values of t(n, k, ℓ) for large ℓ and better upper bounds of t(n, k, ℓ) for small ℓ and k = 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 227-241
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Nowhere-Zero Unoriented 6-Flows on Certain Triangular Graphs
Autorzy:
Yang, Fan
Li, Liangchen
Zhou, Sizhong
Powiązania:
https://bibliotekanauki.pl/articles/32309450.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
nowhere-zero k -flow
triangle-tree
triangle-star
bidirected graph
Opis:
A nowhere-zero unoriented flow of graph G is an assignment of non-zero real numbers to the edges of G such that the sum of the values of all edges incident with each vertex is zero. Let k be a natural number. A nowhere-zero unoriented k-flow is a flow with values from the set {±1, . . ., ±(k − 1)}, for short we call it NZ-unoriented k-flow. Let H1 and H2 be two graphs, H1⊕H2 denote the 2-sum of H1 and H2, if E(H1⊕H2) = E(H1) ∪ E(H2), |V(H1)∩V(H2)|=2, and |E(H1)∩E(H2)| = 1. A triangle-path in a graph G is a sequence of distinct triangles T1, T2, . . ., Tm in G such that for 1 ≤ i ≤ m, |E(Ti)∩E(Ti+1)| = 1 and E(Ti)∩E(Tj)=∅ if j>i+1. A triangle-star is a graph with triangles such that each triangle having one common edges with other triangles. Let G be a graph which can be partitioned into some triangle-paths or wheels H1, H2, . . ., Ht such that G = H1⊕H2⊕...⊕Ht. In this paper, we prove that G except a triangle-star admits an NZ-unoriented 6-flow. Moreover, if each Hi is a triangle-path, then G except a triangle-star admits an NZ-unoriented 5-flow.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 727-746
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Two Generalized Connectivities of Graphs
Autorzy:
Sun, Yuefang
Li, Fengwei
Jin, Zemin
Powiązania:
https://bibliotekanauki.pl/articles/31342427.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k -connectivity
pendant tree-connectivity
Cartesian product
Cayley graph
Opis:
The concept of generalized $k$-connectivity $ \kappa_k (G) $, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. The pendant tree-connectivity $ \tau_k (G) $ was also introduced by Hager in 1985, which is a specialization of generalized $k$-connectivity but a generalization of the classical connectivity. Another generalized connectivity of a graph $G$, named $k$-connectivity $ \kappa_k^' (G) $, introduced by Chartrand et al. in 1984, is a generalization of the cut-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of $ \kappa_k^' (G) $ and $ \tau_k(G) $ by showing that for a connected graph $G$ of order $n$, if $ \kappa_k^' (G) \ne n − k + 1 $ where $ k \ge 3 $, then $ 1 \le \kappa_k^' (G) − \tau_k (G) \le n − k $; otherwise, $ 1 \le κ_k^' (G) − \tau_k(G) \le n − k + 1 $. Moreover, all of these bounds are sharp. We get a sharp upper bound for the 3-connectivity of the Cartesian product of any two connected graphs with orders at least 5. Especially, the exact values for some special cases are determined. Among our results, we also study the pendant tree-connectivity of Cayley graphs on Abelian groups of small degrees and obtain the exact values for $ \tau_k(G) $, where $G$ is a cubic or 4-regular Cayley graph on Abelian groups, $ 3 \le k \le n $.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 245-261
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Minimum Size of a Graph with Given Tree Connectivity
Autorzy:
Sun, Yuefang
Sheng, Bin
Jin, Zemin
Powiązania:
https://bibliotekanauki.pl/articles/32083875.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
generalized connectivity
tree connectivity
eneralized k-connectivity
generalized k-edge-connectivity
packing
Opis:
For a graph $G = (V, E)$ and a set $S ⊆ V$ of at least two vertices, an $S$-tree is a such subgraph $T$ of $G$ that is a tree with $S ⊆ V(T)$. Two $S$-trees $T_1$ and $T_2$ are said to be internally disjoint if $E(T_1) ∩ E(T_2) = ∅$ and $V(T_1) ∩ V(T_2) = S$, and edge-disjoint if $E(T_1) ∩ E(T_2) = ∅$. The generalized local connectivity $κ_G(S)$ (generalized local edge-connectivity $λ_G(S)$, respectively) is the maximum number of internally disjoint (edge-disjoint, respectively) $S$-trees in $G$. For an integer $k$ with $2 ≤ k ≤ n$, the generalized $k$-connectivity (generalized $k$-edge-connectivity, respectively) is defined as $κ_k(G) = min{κ_G(S) | S ⊆ V(G), |S| = k} (λ_k(G) = min{λ_G(S) | S ⊆ V(G), |S| = k}$, respectively). Let $f(n, k, t)$ ($g(n, k, t)$, respectively) be the minimum size of a connected graph $G$ with order $n$ and $κ_k(G) = t$ ($λ_k(G) = t$, respectively), where $3 ≤ k ≤ n$ and \(1≤t≤n-⌈\frac{k}{2}⌉\). For general $k$ and $t$, Li and Mao obtained a lower bound for $g(n, k, t)$ which is tight for the case $k = 3$. We show that the bound also holds for $f(n, k, t)$ and is tight for the case $k = 3$. When t is general, we obtain upper bounds of both $f(n, k, t)$ and $g(n, k, t)$ for $k ∈ {3, 4, 5}$, and all of these bounds can be attained. When $k$ is general, we get an upper bound of $g(n, k, t)$ for $t ∈ {1, 2, 3, 4}$ and an upper bound of $f(n, k, t)$ for $t ∈ {1, 2, 3}$. Moreover, both bounds can be attained.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 409-425
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
L(2, 1)-Labelings of Some Families of Oriented Planar Graphs
Autorzy:
Sen, Sagnik
Powiązania:
https://bibliotekanauki.pl/articles/30147217.pdf
Data publikacji:
2014-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
homomorphism
planar graph
girth
partial k-tree
outerplanar graph
cactus
2-dipath L(2, 1)-labeling
oriented L(2, 1)-labeling
Opis:
In this paper we determine, or give lower and upper bounds on, the 2-dipath and oriented L(2, 1)-span of the family of planar graphs, planar graphs with girth 5, 11, 16, partial k-trees, outerplanar graphs and cacti.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 31-48
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Przydatność danych lidarowych do zwiększenia potencjału informacyjnego bazy danych topograficznych w klasie „drzewo”
LiDAR data for increasing the informational potential of topographical database in case of “tree” features
Autorzy:
Piasecka, Ż.
Pluto-Kossakowska, J.
Powiązania:
https://bibliotekanauki.pl/articles/132192.pdf
Data publikacji:
2017
Wydawca:
Polskie Towarzystwo Geograficzne
Tematy:
BDOT10k
LiDAR
detekcja drzew
model 3D
aktualizacja bazy danych
tree detection
3D model
database updating
Opis:
Celem artykułu jest przedstawienie możliwości aktualizacji Bazy Danych Obiektów Topograficznych (BDOT10k) oraz zaprezentowanie koncepcji pozyskania dodatkowych danych w celu zasilenia, a tym samym zwiększenia potencjału informacyjnego bazy danych. Koncepcja aktualizacji, jak i pozyskania dodatkowych danych polega na wykorzystaniu chmury punktów pozyskanej za pomocą lotniczego skanowania laserowego. Dokonano przeglądu literatury z zakresu aktualizacji baz danych, głównie BDOT10k, a także z zakresu systemu LiDAR i metod ekstrakcji obiektów z chmury punktów. W badaniach przeprowadzono detekcję pojedynczych drzew metodą automatyczną w oprogramowaniu ENVI LiDAR wraz z oceną dokładności. Obiekty będące wynikiem ekstrakcji w ENVI LiDAR porównano z drzewami występującymi na badanym obszarze testowym. Problemem przy identyfikacji drzew było określenie optymalnego parametru minimalnej wartości promienia korony drzewa. Przedstawiono możliwość edycji w celu wyeliminowania błędów i przygotowania klasy obiektów „drzewo” oraz jej atrybutów do zasilenia BDOT10k. W artykule przedstawiono również możliwości aktualizacji wybranych obiektów bazy na podstawie chmury punktów, a także podjęto dyskusję na temat potrzeby zasilenia bazy obiektami typu „pojedyncze drzewo”. Badania będące przedmiotem artykułu mają znaczenie dla późniejszej możliwości konwersji tak bogatej informacyjnie bazy do postaci 3D, w celu stworzenia trójwymiarowych modeli miast. Uzyskane wyniki potwierdzają przydatność danych LiDARowych do aktualizacji i pozyskiwania dodatkowych obiektów z dobrą skutecznością. Napotkane problemy i wyniki automatycznej detekcji udowadniają, że obiekty pozyskane zaproponowaną metodą wymagają manualnej edycji. W ramach badań, oprócz detekcji i ekstrakcji obiektów, zaproponowano modyfikację schematu aplikacyjnego dla klasy obiektów „obiekty inne”, w przypadku zasilenia jej pojedynczymi drzewami.
The subject of this paper is to present the possibility of updating of selected object class in topographical database (BDOT10k) and to present the concept of obtaining additional data in order to supply and thereby increase the potential of the database in case of “tree” features. The object “tree” detection and extraction are based on the point cloud set obtained by airborne laser scanning (LiDAR). A literature review in the field of topographical database updating, mainly BDOT10k, and the methods of object extraction from the point cloud was performed. The extraction of individual trees was carried out by an automated method in ENVI LiDAR software. The accuracy assessment of tree objects extraction was made based on actual state of trees (field measurement). The main problem with trees extracting was determination of the optimum parameter of tree crowns radius. In order to eliminate errors and to prepare layers and attributes, the possibility of editing and detection improvement was presented. The discussion of database updating possibility and necessity based on point cloud in case of “tree” features was presented. The research undertaken is important for the subsequent conversion of such information-rich database to 3D in order to create three-dimensional models of cities. The obtained results confirm the usefulness of LiDAR data for updating and obtaining “tree” objects with good efficiency. However, problems that were encountered and results of extraction prove that objects which are obtained by proposed automatic method require manual intervention. As part of the research, it was proposed to modify the application scheme for the „other objects” features in case of individual trees.
Źródło:
Teledetekcja Środowiska; 2017, 57; 15-26
1644-6380
Pojawia się w:
Teledetekcja Środowiska
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A contribution to the systematics of the genus Tilia with respect to some hybrids by RAPD analysis
Autorzy:
Liesebach, H
Sinko, Z.
Powiązania:
https://bibliotekanauki.pl/articles/41216.pdf
Data publikacji:
2008
Wydawca:
Polska Akademia Nauk. Instytut Dendrologii PAN
Tematy:
Tilia
linden
taxonomy
hybrid
DNA
UPGMA method
systematics
random amplified polymorphic DNA
Szent Istvan tree
K3 tree
cluster analysis
Opis:
The putative hybrid character of two Tilia varieties selected as avenue trees (‘Szent Istvan’ and‘K3’) should be clarified for further breeding activities. Their ancestor species should be identified by a genetic comparison with reference material (Tilia cordata, T. platyphyllos, T. dasystyla, T. × euchlora, T. × europaea and others). RAPD marker data were evaluated by UPGMA cluster and neighbour-joining analysis. The genetic comparison of the two selected clones with the collection of reference material offers insights into some systematic relationships within the genus Tilia. It was supplemented by a critical discussion of methods of RAPD data evaluation for taxonomic purposes.
Źródło:
Dendrobiology; 2008, 59; 13-22
1641-1307
Pojawia się w:
Dendrobiology
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with 3-Rainbow Index n − 1 and n − 2
Autorzy:
Li, Xueliang
Schiermeyer, Ingo
Yang, Kang
Zhao, Yan
Powiązania:
https://bibliotekanauki.pl/articles/31339126.pdf
Data publikacji:
2015-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow S-tree
k-rainbow index
Opis:
Let $G = (V(G),E(G))$ be a nontrivial connected graph of order $n$ with an edge-coloring $c : E(G) → {1, 2, . . ., q}, q ∈ \mathbb{N}$, where adjacent edges may be colored the same. A tree $T$ in $G$ is a rainbow tree if no two edges of $T$ receive the same color. For a vertex set $S ⊆ V (G)$, a tree connecting $S$ in $G$ is called an $S$-tree. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow $S$-tree for each $k$-subset $S$ of $V(G)$ is called the $k$-rainbow index of $G$, denoted by $rx_k(G)$, where $k$ is an integer such that $2 ≤ k ≤ n$. Chartrand et al. got that the $k$-rainbow index of a tree is $n−1$ and the $k$-rainbow index of a unicyclic graph is $n−1$ or $n−2$. So there is an intriguing problem: Characterize graphs with the $k$-rainbow index $n − 1$ and $n − 2$. In this paper, we focus on $k = 3$, and characterize the graphs whose $3$-rainbow index is $n − 1$ and $n − 2$, respectively.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 105-120
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with 4-Rainbow Index 3 and n − 1
Autorzy:
Li, Xueliang
Schiermeyer, Ingo
Yang, Kang
Zhao, Yan
Powiązania:
https://bibliotekanauki.pl/articles/31339468.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow S-tree
k-rainbow index
Opis:
Let $G$ be a nontrivial connected graph with an edge-coloring $ c : E(G) \rightarrow $ $ {1, 2, . . ., q}, $ $q \in \mathbb{N} $, where adjacent edges may be colored the same. A tree $T$ in $G$ is called a rainbow tree if no two edges of $T$ receive the same color. For a vertex set $ S \subseteq V (G) $, a tree that connects $S$ in $G$ is called an $S$-tree. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow $S$-tree for every set $S$ of $k$ vertices of $V (G)$ is called the $k$-rainbow index of $G$, denoted by $ r x_k (G) $. Notice that a lower bound and an upper bound of the $k$-rainbow index of a graph with order $n$ is $k − 1$ and $n − 1$, respectively. Chartrand et al. got that the $k$-rainbow index of a tree with order $n$ is $n − 1$ and the $k$-rainbow index of a unicyclic graph with order $n$ is $n − 1$ or $n − 2$. Li and Sun raised the open problem of characterizing the graphs of order $n$ with $r x_k (G) = n − 1$ for $ k \ge 3 $. In early papers we characterized the graphs of order $n$ with 3-rainbow index 2 and $n − 1$. In this paper, we focus on $k = 4$, and characterize the graphs of order $n$ with 4-rainbow index 3 and $n − 1$, respectively.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 387-398
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Algorithmic aspects of total-subdomination in graphs
Autorzy:
Harris, Laura
Hattingh, Johannes
Henning, Michael
Powiązania:
https://bibliotekanauki.pl/articles/744186.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total k-subdomination
algorithm
tree
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 5-18
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Degree Sum Condition for the Existence of Spanning k-Trees in Star-Free Graphs
Autorzy:
Furuya, Michitaka
Maezawa, Shun-ichi
Matsubara, Ryota
Matsuda, Haruhide
Tsuchiya, Shoichi
Yashima, Takamasa
Powiązania:
https://bibliotekanauki.pl/articles/32361756.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
spanning tree
k -tree
star-free
degree sum condition
Opis:
For an integer k ≥ 2, a k-tree T is defined as a tree with maximum degree at most k. If a k-tree T spans a graph G, then T is called a spanning k-tree of G. Since a spanning 2-tree is a Hamiltonian path, a spanning k-tree is an extended concept of a Hamiltonian path. The first result, implying the existence of k-trees in star-free graphs, was by Caro, Krasikov, and Roditty in 1985, and independently, Jackson and Wormald in 1990, who proved that for any integer k with k ≥ 3, every connected K1,k-free graph contains a spanning k-tree. In this paper, we focus on a sharp condition that guarantees the existence of a spanning k-tree in K1,k+1-free graphs. In particular, we show that every connected K1,k+1-free graph G has a spanning k-tree if the degree sum of any 3k−3 independent vertices in G is at least |G|−2, where |G| is the order of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 5-13
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Closure for spanning trees and distant area
Autorzy:
Fujisawa, Jun
Saito, Akira
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/743839.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
spanning tree
k-ended tree
closure
Opis:
A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $deg_G u + deg_G v ≥ n-1$, G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $deg_G u + deg_G v$ and the structure of the distant area for u and v. We prove that if the distant area contains $K_r$, we can relax the lower bound of $deg_G u + deg_G v$ from n-1 to n-r. And if the distant area itself is a complete graph and G is 2-connected, we can entirely remove the degree sum condition.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 143-159
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the Signed Roman k-Domination Number of a Digraph
Autorzy:
Chen, Xiaodan
Hao, Guoliang
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/31343713.pdf
Data publikacji:
2019-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
signed Roman k-dominating function
signed Roman k-domination number
digraph
oriented tree
Opis:
Let $k$ be a positive integer. A signed Roman $k$-dominating function (SRkDF) on a digraph $D$ is a function $ f : V (D) \rightarrow \{−1, 1, 2 \} $ satisfying the conditions that (i) $ \Sigma_{ x \in N^− [v] } f(x) \ge k $ for each $ v \in V (D) $, where $ N^− [v] $ is the closed in-neighborhood of $v$, and (ii) each vertex $u$ for which $f(u) = −1$ has an in-neighbor $v$ for which $f(v) = 2$. The weight of an SRkDF $f$ is $ \Sigma_{ v \in V (D) } f(v) $. The signed Roman $k$-domination number $ \gamma_{sR}^k (D) $ of a digraph $D$ is the minimum weight of an SRkDF on $D$. We determine the exact values of the signed Roman $k$-domination number of some special classes of digraphs and establish some bounds on the signed Roman $k$-domination number of general digraphs. In particular, for an oriented tree $T$ of order $n$, we show that $ \gamma_{sR}^2 (T) \ge (n + 3)//2 $, and we characterize the oriented trees achieving this lower bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 67-79
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The 3-Rainbow Index of a Graph
Autorzy:
Chen, Lily
Li, Xueliang
Yang, Kang
Zhao, Yan
Powiązania:
https://bibliotekanauki.pl/articles/31339122.pdf
Data publikacji:
2015-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow tree
S-tree
k-rainbow index
Opis:
Let $G$ be a nontrivial connected graph with an edge-coloring $c : E(G) → {1, 2, . . ., q}, q ∈ ℕ$, where adjacent edges may be colored the same. A tree $T$ in $G$ is a rainbow tree if no two edges of $T$ receive the same color. For a vertex subset $S ⊆ V (G)$, a tree that connects $S$ in $G$ is called an $S$-tree. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow $S$-tree for each $k$-subset $S$ of $V(G)$ is called the $k$-rainbow index of $G$, denoted by $rx_k(G)$. In this paper, we first determine the graphs of size $m$ whose 3-rainbow index equals $m$, $m − 1$, $m − 2$ or $2$. We also obtain the exact values of $rx_3(G)$ when $G$ is a regular multipartite complete graph or a wheel. Finally, we give a sharp upper bound for $rx_3(G)$ when $G$ is 2-connected and 2-edge connected. Graphs $G$ for which $rx_3(G)$ attains this upper bound are determined.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 81-94
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decomposition tree and indecomposable coverings
Autorzy:
Breiner, Andrew
Deogun, Jitender
Ille, Pierre
Powiązania:
https://bibliotekanauki.pl/articles/744120.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
interval
indecomposable
k-covering
decomposition tree
Opis:
Let G = (V,A) be a directed graph. With any subset X of V is associated the directed subgraph G[X] = (X,A ∩ (X×X)) of G induced by X. A subset X of V is an interval of G provided that for a,b ∈ X and x ∈ V∖X, (a,x) ∈ A if and only if (b,x) ∈ A, and similarly for (x,a) and (x,b). For example ∅, V, and {x}, where x ∈ V, are intervals of G which are the trivial intervals. A directed graph is indecomposable if all its intervals are trivial. Given an integer k > 0, a directed graph G = (V,A) is called an indecomposable k-covering provided that for every subset X of V with |X| ≤ k, there exists a subset Y of V such that X ⊆ Y, G[Y] is indecomposable with |Y| ≥ 3. In this paper, the indecomposable k-covering directed graphs are characterized for any k > 0.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 37-44
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 17

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