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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 46
Tytuł:
Trees with Distinguishing Index Equal Distinguishing Number Plus One
Autorzy:
Alikhani, Saeid
Klavžar, Sandi
Lehner, Florian
Soltani, Samaneh
Powiązania:
https://bibliotekanauki.pl/articles/31804165.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
automorphism group
distinguishing index
distinguishing number
tree
unicyclic graph
Opis:
The distinguishing number (index) D(G) (D′ (G)) of a graph G is the least integer d such that G has an vertex (edge) labeling with d labels that is preserved only by the trivial automorphism. It is known that for every graph G we have D′ (G) ≤ D(G) + 1. In this note we characterize finite trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D′ (G) = D(G).
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 875-884
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ł:
Statuses and double branch weights of quadrangular outerplanar graphs
Autorzy:
Bielak, Halina
Powroźnik, Kamil
Powiązania:
https://bibliotekanauki.pl/articles/747004.pdf
Data publikacji:
2015
Wydawca:
Uniwersytet Marii Curie-Skłodowskiej. Wydawnictwo Uniwersytetu Marii Curie-Skłodowskiej
Tematy:
Centroid
median
outerplanar graph
status
tree
Opis:
In this paper we study some distance properties of outerplanar graphs with the Hamiltonian cycle whose all bounded faces are cycles isomorphic to the cycle C4. We call this family of graphs quadrangular outerplanar graphs. We give the lower and upper bound on the double branch weight and the status for this graphs. At the end of this paper we show some relations between median and double centroid in quadrangular outerplanar graphs.
Źródło:
Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica; 2015, 69, 1
0365-1029
2083-7402
Pojawia się w:
Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
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ł:
Parity vertex colouring of graphs
Autorzy:
Borowiecki, Piotr
Budajová, Kristína
Jendrol', Stanislav
Krajci, Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/743850.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
parity colouring
graph colouring
vertex ranking
ordered colouring
tree
hypercube
Fibonacci number
Opis:
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 183-195
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Arboreal structure and regular graphs of median-like classes
Autorzy:
Brešar, Bostjan
Powiązania:
https://bibliotekanauki.pl/articles/743403.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
median graph
tree
gatedness
amalgam
periphery
regular graph
Opis:
We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of the gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph of the graph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional property. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 215-225
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs that are Critical for the Packing Chromatic Number
Autorzy:
Brešar, Boštjan
Ferme, Jasmina
Powiązania:
https://bibliotekanauki.pl/articles/32318620.pdf
Data publikacji:
2022-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
packing coloring
critical graph
diameter
block graph
tree
Opis:
Given a graph G, a coloring c : V (G) → {1, …, k} such that c(u) = c(v) = i implies that vertices u and v are at distance greater than i, is called a packing coloring of G. The minimum number of colors in a packing coloring of G is called the packing chromatic number of G, and is denoted by χρ(G). In this paper, we propose the study of χρ-critical graphs, which are the graphs G such that for any proper subgraph H of G, χρ(H) < χρ(G). We characterize χρ-critical graphs with diameter 2, and χρ-critical block graphs with diameter 3. Furthermore, we characterize χρ-critical graphs with small packing chromatic number, and we also consider χρ-critical trees. In addition, we prove that for any graph G and every edge e ∈ E(G), we have (χρ(G)+1)/2 ≤ χρ(G−e) ≤ χρ(G), and provide a corresponding realization result, which shows that χρ(G − e) can achieve any of the integers between these bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 569-589
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A characterization of 2-tree probe interval graphs
Autorzy:
Brown, David E.
Flesch, Breeann M.
Lundgren, J. Richard
Powiązania:
https://bibliotekanauki.pl/articles/30148257.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
interval graph
probe interval graph
2-tree
Opis:
A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231]
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 509-527
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total connected domination game
Autorzy:
Bujtás, Csilla
Henning, Michael A.
Iršič, Vesna
Klavžar, Sandi
Powiązania:
https://bibliotekanauki.pl/articles/2050904.pdf
Data publikacji:
2021
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
connected domination game
total connected domination game
graph product
tree
Opis:
The (total) connected domination game on a graph $G$ is played by two players, Dominator and Staller, according to the standard (total) domination game with the additional requirement that at each stage of the game the selected vertices induce a connected subgraph of $G$. If Dominator starts the game and both players play optimally, then the number of vertices selected during the game is the (total) connected game domination number $(\gamma_{tcg}(G))(\gamma_{cg(G)})$ of $G$. We show that $\gamma_{tcg}(G) \in \{\gamma_{cg}(G), \gamma_{cg}(G)+1, \gamma_{cg}(G)+2\}$, and consequently define $G$ as Class $i$ if $\gamma_{tcg}(G) = \gamma_{cg}(G)+i$ for $i \in \{0, 1, 2\}$. A large family of Class 0 graphs is constructed which contains all connected Cartesian product graphs and connected direct product graphs with minimum degree at least 2. We show that no tree is Class 2 and characterize Class 1 trees. We provide an infinite family of Class 2 bipartite graphs.
Źródło:
Opuscula Mathematica; 2021, 41, 4; 453-464
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On non-z(mod k) dominating sets
Autorzy:
Caro, Yair
Jacobson, Michael
Powiązania:
https://bibliotekanauki.pl/articles/743399.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
tree
unicyclic graph
Opis:
For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 1, a subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x ∈ V(G), |N[x]∩D| ≢ z (mod k).For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with z < k and z ≠ 1, that a non-z(mod k) dominating set exist for all trees. Also, it will be shown that for k ≥ 4, z ≥ 1, 2 or 3 that any unicyclic graph contains a non-z(mod k) dominating set. We also give a few special cases of other families of graphs for which these dominating sets must exist.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 189-199
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ł:
Tree domatic number in graphs
Autorzy:
Chen, X. G.
Powiązania:
https://bibliotekanauki.pl/articles/255594.pdf
Data publikacji:
2007
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
tree domatic number
regular graph
planar graph
Cartesian product
Opis:
A dominating set S in a graph G is a tree dominating set of G if the subgraph induced by S is a tree. The tree domatic number of G is the maximum number of pairwise disjoint tree dominating sets in V(G). First, some exact values of and sharp bounds for the tree domatic number are given. Then, we establish a sharp lower bound for the number of edges in a connected graph of given order and given tree domatic number, and we characterize the extremal graphs. Finally, we show that a tree domatic number of a planar graph is at most 4 and give a characterization of planar graphs with the tree domatic number 3.
Źródło:
Opuscula Mathematica; 2007, 27, 1; 5-11
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On some aspects of graph theory for optimal transport among marine ports
Autorzy:
Chládek, P.
Smetanová, D.
Krile, S.
Powiązania:
https://bibliotekanauki.pl/articles/196424.pdf
Data publikacji:
2018
Wydawca:
Politechnika Śląska. Wydawnictwo Politechniki Śląskiej
Tematy:
graph theory
minimum spanning tree
seaport
Travelling Salesman Problem
teoria grafów
minimalne drzewo spinające
port morski
Opis:
This paper is devoted to the Travelling Salesman Problem as applied to Czechoslovak ocean shipping companies and their marine ports on the Black Sea. The shortest circular path around these ports is found and discussed. Formulation of the problem accounts for the fact that distances between the individual cities are not the same in both directions. The consequences that arise from this situation are studied. The used algorithms are based on graph theory and standard logistic methods. In addition, the results are compared with the results obtained by using a minimum spanning tree algorithm.
Źródło:
Zeszyty Naukowe. Transport / Politechnika Śląska; 2018, 101; 37-45
0209-3324
2450-1549
Pojawia się w:
Zeszyty Naukowe. Transport / Politechnika Śląska
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Upper bounds on distance vertex irregularity strength of some families of graphs
Autorzy:
Cichacz, Sylwia
Görlich, Agnieszka
Semaničová-Feňovčíková, Andrea
Powiązania:
https://bibliotekanauki.pl/articles/2216229.pdf
Data publikacji:
2022
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
distance vertex irregularity strength of a graph
hypercube
tree
graph
Opis:
For a graph G its distance vertex irregularity strength is the smallest integer k for which one can find a labeling f : V (G) → {1, 2, . . . , k} such that $ \sum_{x \in N(v)} f(x) \neq \sum_{x \in N(u)} f(x) $ for all vertices u, v of G, where N(v) is the open neighborhood of v. In this paper we present some upper bounds on distance vertex irregularity strength of general graphs. Moreover, we give upper bounds on distance vertex irregularity strength of hypercubes and trees.
Źródło:
Opuscula Mathematica; 2022, 42, 4; 561--571
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
ℤ2 × ℤ2 -Cordial Cycle-Free Hypergraphs
Autorzy:
Cichacz, Sylwia
Görlich, Agnieszka
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/32361757.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
V 4 -cordial graph
hypergraph
labeling of hypergraph
hyper-tree
Opis:
Hovey introduced A-cordial labelings as a generalization of cordial and harmonious labelings [7]. If A is an Abelian group, then a labeling f : V (G) → A of the vertices of some graph G induces an edge labeling on G; the edge uv receives the label f(u) + f(v). A graph G is A-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. The problem of A-cordial labelings of graphs can be naturally extended for hypergraphs. It was shown that not every 2-uniform hypertree (i.e., tree) admits a ℤ2 × ℤ2-cordial labeling [8]. The situation changes if we consider p-uniform hypertrees for a bigger p. We prove that a p-uniform hypertree is ℤ2 × ℤ2-cordial for any p > 2, and so is every path hypergraph in which all edges have size at least 3. The property is not valid universally in the class of hypergraphs of maximum degree 1, for which we provide a necessary and sufficient condition.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1021-1040
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 46

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