Informacja

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

Wyszukujesz frazę "k-tree" wg kryterium: Temat


Tytuł:
Structural results on maximal k-degenerate graphs
Autorzy:
Bickle, Allan
Powiązania:
https://bibliotekanauki.pl/articles/743285.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k-degenerate
k-core
k-tree
degree sequence
Ramsey number
Opis:
A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we conjecture that a maximal k-degenerate graph is class two if and only if it is overfull, and prove this in some special cases. We present some results on decompositions and arboricity of maximal k-degenerate graphs and provide two characterizations of the subclass of k-trees as maximal k-degenerate graphs. Finally, we define and prove a formula for the Ramsey core numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 659-676
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ł:
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ł:
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ł:
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ł:
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ł:
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ł
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ł:
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ł:
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ł:
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ł:
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 strong 3-rainbow index of some certain graphs and its amalgamation
Autorzy:
Awanis, Zata Yumni
Salman, A.N.M.
Powiązania:
https://bibliotekanauki.pl/articles/2216176.pdf
Data publikacji:
2022
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
amalgamation
rainbow coloring
rainbow Steiner tree
strong k-rainbow index
Opis:
We introduce a strong k-rainbow index of graphs as modification of well-known k-rainbow index of graphs. A tree in an edge-colored connected graph G, where adjacent edge may be colored the same, is a rainbow tree if all of its edges have distinct colors. Let k be an integer with 2 ≤ k ≤ n. The strong k-rainbow index of G, denoted by $srx_k(G)$, is the minimum number of colors needed in an edge-coloring of G so that every k vertices of G is connected by a rainbow tree with minimum size. We focus on k = 3. We determine the strong 3-rainbow index of some certain graphs. We also provide a sharp upper bound for the strong 3-rainbow index of amalgamation of graphs. Additionally, we determine the exact values of the strong 3-rainbow index of amalgamation of some graphs.
Źródło:
Opuscula Mathematica; 2022, 42, 4; 527-547
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł

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