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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 27
Tytuł:
Spanning tree congestion of rooks graphs
Autorzy:
Kozawa, Kyohei
Otachi, Yota
Powiązania:
https://bibliotekanauki.pl/articles/743607.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
spanning tree congestion
Rook's graph
Opis:
Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 4; 753-761
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ł:
Spanning trees with a bounded number of leaves
Autorzy:
Cai, J.
Flandrin, E.
Li, H.
Sun, Q.
Powiązania:
https://bibliotekanauki.pl/articles/255239.pdf
Data publikacji:
2017
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
spanning tree
implicit degree
leaves
Opis:
n 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph G with n ≥ 3 vertices, if d(u) + d(y) ≥n — k + 1 for all non-adjacent vertices u and v of G (k ≥ 1), then G has a spanning tree with at most k leaves. In this paper, we generalize this result by using implicit degree sum condition of t (2≤ t ≤k) independent vertices and we prove what follows: Let G be a connected graph on n ≥ 3 vertices and k ≥ 2 be an integer. If the implicit degree sum of any t independent vertices is at least [formula] for (k≥ t ≥ 2), then G has a spanning tree with at most k leaves.
Źródło:
Opuscula Mathematica; 2017, 37, 4; 501-508
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Spanning Trees whose Stems have a Bounded Number of Branch Vertices
Autorzy:
Yan, Zheng
Powiązania:
https://bibliotekanauki.pl/articles/31340783.pdf
Data publikacji:
2016-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
spanning tree
stem
branch vertex
Opis:
Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T − Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 773-778
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Spanning Trees with Disjoint Dominating and 2-Dominating Sets
Autorzy:
Miotk, Mateusz
Żyliński, Paweł
Powiązania:
https://bibliotekanauki.pl/articles/32361736.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
2-domination
spanning tree
Opis:
In this paper, we provide a structural characterization of graphs having a spanning tree with disjoint dominating and 2-dominating sets.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 299-308
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
Autorzy:
Dereniowski, Dariusz
Powiązania:
https://bibliotekanauki.pl/articles/743173.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
computational complexity
vertex ranking
spanning tree
Opis:
A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410] that the decision problem: given a simple graph G, decide whether there exists a spanning tree T of G such that T has a vertex 4-ranking, is NP-complete. In this paper we improve this result by proving NP-hardness of finding for a given chordal graph its spanning tree having vertex 3-ranking. This bound is the best possible. On the other hand we prove that MVRST problem can be solved in linear time for proper interval graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 253-261
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On a Spanning $k$-Tree in which Specified Vertices Have Degree Less Than $k$
Autorzy:
Matsumura, Hajime
Powiązania:
https://bibliotekanauki.pl/articles/31339152.pdf
Data publikacji:
2015-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
spanning tree
degree bounded tree
degree sum condition
Opis:
A $k$-tree is a tree with maximum degree at most $k$. In this paper, we give a degree sum condition for a graph to have a spanning $k$-tree in which specified vertices have degree less than $k$. We denote by $\sigma_k(G)$ the minimum value of the degree sum of $k$ independent vertices in a graph $G$. Let $k ≥ 3$ and s $≥ 0$ be integers, and suppose $G$ is a connected graph and $\sigma_k(G) ≥ |V (G)|+s−1$. Then for any $s$ specified vertices, $G$ contains a spanning $k$-tree in which every specified vertex has degree less than $k$. The degree condition is sharp.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 191-196
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Completely Independent Spanning Trees in k-th Power of Graphs
Autorzy:
Hong, Xia
Powiązania:
https://bibliotekanauki.pl/articles/31342277.pdf
Data publikacji:
2018-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
completely independent spanning tree
power of graphs
spanning trees
Opis:
Let T1, T2, . . ., Tk be spanning trees of a graph G. For any two vertices u, v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T1, T2, . . ., Tk are completely independent. Araki showed that the square of a 2-connected graph G on n vertices with n ≥ 4 has two completely independent spanning trees. In this paper, we prove that the k-th power of a k-connected graph G on n vertices with n ≥ 2k has k completely independent spanning trees. In fact, we prove a stronger result: if G is a connected graph on n vertices with δ(G) ≥ k and n ≥ 2k, then the k-th power Gk of G has k completely independent spanning trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 801-810
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Minimum Number of Spanning Trees in Cubic Multigraphs
Autorzy:
Bogdanowicz, Zbigniew R.
Powiązania:
https://bibliotekanauki.pl/articles/32083837.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic multigraph
spanning tree
regular graph
enumeration
Opis:
Let G2n, H2n be two non-isomorphic connected cubic multigraphs of order 2n with parallel edges permitted but without loops. Let t(G2n), t (H2n) denote the number of spanning trees in G2n, H2n, respectively. We prove that for n ≥ 3 there is the unique G2n such that t(G2n) < t(H2n) for any H2n. Furthermore, we prove that such a graph has t(G2n) = 522n−3 spanning trees. Based on our results we give a conjecture for the unique r-regular connected graph H2n of order 2n and odd degree r that minimizes the number of spanning trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 149-159
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ł:
Minimum congestion spanning trees of grids and discrete toruses
Autorzy:
Castejón, Alberto
Ostrovskii, Mikhail
Powiązania:
https://bibliotekanauki.pl/articles/744453.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
minimum congestion spanning tree
grid graph
discrete torus
Opis:
The paper is devoted to estimates of the spanning tree congestion for grid graphs and discrete toruses of dimensions two and three.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 3; 511-519
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A self-stabilizing algorithm for detecting fundamental cycles in a graph with DFS spanning tree given
Autorzy:
Bielak, H.
Pańczyk, M.
Powiązania:
https://bibliotekanauki.pl/articles/106174.pdf
Data publikacji:
2013
Wydawca:
Uniwersytet Marii Curie-Skłodowskiej. Wydawnictwo Uniwersytetu Marii Curie-Skłodowskiej
Tematy:
self-stabilizing algorithm
fundamental cycles
graph
DFS spanning tree
Opis:
This paper presents a linear time self-stabilizing algorithm for detecting the set of fundamental cycles on an undirected connected graph modelling asynchronous distributed system.The previous known algorithm has O(n^2) time complexity, whereas we prove that this one stabilizesafter O(n) moves. The distributed adversarial scheduler is considered. Both algorithms assume that the depth-search spanning tree of the graph is given. The output is given in a distributed manner asa state of variables in the nodes.
Źródło:
Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica; 2013, 13, 1; 7-10
1732-1360
2083-3628
Pojawia się w:
Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on the computation of ordered supported non-dominated solutions in the bi-criteria minimum spanning tree problems
Autorzy:
Silva, C. G.
Cli'maco, J. C. N.
Powiązania:
https://bibliotekanauki.pl/articles/308580.pdf
Data publikacji:
2007
Wydawca:
Instytut Łączności - Państwowy Instytut Badawczy
Tematy:
minimum spanning tree
supported non-dominated solutions
combinatorial problems
Opis:
This paper presents a new procedure for computing the set of supported non dominated solutions of bi-criteria minimum spanning tree problems in ordered manner. The procedure is based on the systematic detection of edges which must be replaced in one efficient solution to obtain the adjacent one, in the criteria space. This new approach avoids solving unnecessary problems and makes use of previous computations.
Źródło:
Journal of Telecommunications and Information Technology; 2007, 4; 11-15
1509-4553
1899-8852
Pojawia się w:
Journal of Telecommunications and Information Technology
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The graph theory approach to analyze critical infrastructures of transportation systems
Autorzy:
Guze, S.
Powiązania:
https://bibliotekanauki.pl/articles/2069516.pdf
Data publikacji:
2014
Wydawca:
Uniwersytet Morski w Gdyni. Polskie Towarzystwo Bezpieczeństwa i Niezawodności
Tematy:
critical infrastructures
domination set
domination number
minimal spanning tree
Opis:
The main aim of the paper is to use algorithms and parameters of graph theory as tool to analyze the transpiration systems. To realize this goal the well-known information about graph theory algorithms and parameters will be introduced and described. The possible application of graph theory algorithms and parameters to analyze the critical infrastructures of exemplary transportation system will be shown.
Źródło:
Journal of Polish Safety and Reliability Association; 2014, 5, 2; 57--62
2084-5316
Pojawia się w:
Journal of Polish Safety and Reliability Association
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decompositions of Cubic Traceable Graphs
Autorzy:
Liu, Wenzhong
Li, Panpan
Powiązania:
https://bibliotekanauki.pl/articles/31867897.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
decomposition
cubic traceable graph
spanning tree
matching
2-regular graph
Opis:
A traceable graph is a graph with a Hamilton path. The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular graph and a matching. We prove the conjecture for cubic traceable graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 35-49
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 27

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