Browsing by Subject "tree"

Now showing 1 - 20 of 22

Access status: Open Access ,
A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
(Wydawnictwa AGH, 2025) Ziemann, Radosław; Żyliński, Paweł
We provide a linear time algorithm for determining the sets of vertices that belong to all, some and no minimum dominating sets of a tree, respectively, thus improving the quadratic time algorithm of Benecke and Mynhardt in 2008 [S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209]. Some algorithmic consequences are also discussed.
Access status: Open Access ,
A model for the inverse 1-median problem on trees under uncertain costs
(2016) Nguyen, Kien Trung; Nguyen, Thi Linh Chi
We consider the problem of justifying vertex weights of a tree under uncertain costs so that a prespecified vertex become optimal and the total cost should be optimal in the uncertainty scenario. We propose a model which delivers the information about the optimal cost which respect to each confidence level $\alpha \in [0,1]$. To obtain this goal, we first define an uncertain variable with respect to the minimum cost in each confidence level. If all costs are independently linear distributed, we present the inverse distribution function of this uncertain variable in $O(n^{2}\log n)$ time, where n is the number of vertices in the tree.
Access status: Open Access ,
An upper bound on the total outer-independent domination number of a tree
(2012) Krzywkowski, Marcin
A total outer-independent dominating set of a graph $G=(V (G), E(G))$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$, and the set $V(G) \setminus D$ is independent. The total outer-independent domination number of a graph $G$, denoted by $\gamma_t^{oi}(G)$, is the minimum cardinality of a total outer-independent dominating set of $G$. We prove that for every tree $T$ of order $n \geq 4$, with $l$ leaves and s support vertices we have $\gamma_t^{oi}(T) \leq (2n + s - l)/3$, and we characterize the trees attaining this upper bound.
Access status: Open Access ,
Bipartite embedding of (p, q)-trees
(2006) Orchel, Beata
A bipartite graph $G=(L,R;E)$ where $V(G)=L\cup R$, $|L|=p$, $|R|=q$ is called a $(p,q)$-tree if $|E(G)|=p+q−1$ and $G$ has no cycles. A bipartite graph $G=(L,R;E)$ is a subgraph of a bipartite graph $H=(L',R';E')$ if $L\subseteq L'$, $R\subseteq R'$ and $E\subseteq E'$. In this paper we present sufficient degree conditions for a bipartite graph to contain a $(p,q)$-tree.
Access status: Open Access ,
Colourings of (k-r,k)-trees
(Wydawnictwa AGH, 2017) Borowiecki, Mieczysław; Patil, H.P.
Trees are generalized to a special kind of higher dimensional complexes known as $(j,k)$-trees ([L. W. Beineke, R. E. Pippert, On the structure of $(m,n)$-trees, Proc. 8th S-E Conf. Combinatorics, Graph Theory and Computing, 1977, 75-80]), and which are a natural extension of $k$-trees for $j=k−1$. The aim of this paper is to study$(k−r,k)$-trees ([H. P. Patil, Studies on $k$-trees and some related topics, PhD Thesis, University of Warsaw, Poland, 1984]), which are a generalization of $k$-trees (or usual trees when $k=1$). We obtain the chromatic polynomial of $(k−r,k)$-trees and show that any two $(k−r,k)$-trees of the same order are chromatically equivalent. However, if $r\neq 1$ in any $(k−r,k)$-tree $G$, then it is shown that there exists another chromatically equivalent graph $H$, which is not a $(k−r,k)$-tree. Further, the vertex-partition number and generalized total colourings of $(k−r,k)$-trees are obtained. We formulate a conjecture about the chromatic index of $(k−r,k)$-trees, and verify this conjecture in a number of cases. Finally, we obtain a result of [M. Borowiecki, W. Chojnacki, Chromatic index of $k$-trees, Discuss. Math. 9 (1988), 55-58] as a corollary in which $k$-trees of Class 2 are characterized.
Access status: Restricted ,
Drzewa Aronszajna
(Data obrony: 2010-07-06) Kowalczyk, Małgorzata
Wydział Matematyki Stosowanej
Access status: Open Access ,
Evaluation of GPR surveys for assessment of trees condition in urbanized areas
(Wydawnictwa AGH, 2014) Mazurek, Ewelina; Łyskowski, Mikołaj
Modern measuring equipment is sometimes used for applications, for which it has not been originally designed. For example Ground Penetrating Radar (GPR), designed for subsurface structures analysis, can be used for tree tomography. Radar utilizes the phenomenon of propagation of the electromagnetic waves in a physical medium. Measurements can be carried out in situ, in a non-invasive manner on a living tree. Collected data allow for the tree condition determination. It is possible to detect voids and internal structure. Geophysical investigations can provide an estimation of the risk of falling of the trees. These methods also allow determination of the production quality of the tree by detecting knots inside the structure. Available literature shows only limited examples of the usage of other geophysical surveys, such as the ultrasound and geoelectrical method. However, in many cases these measurements are performed on samples in the form of profiles cut from the felled trees. Presented study was conducted on a set of 8 ash trees growing in the Krakow city parks. The measurement was carried out with high frequency antenna – 1600 MHz. Due to the lack of available literature and limited experience of the authors, only trees with known condition were tested. Despite many attempts, the authors were not able to developed a reliable measurement methodology which would allow for unambiguous classification and interpretation of results. In most cases, the results of the study permitted determination of the trees condition. However, some echograms, of the surveyed trees with visible voids pointed to a different tree state and misclassification. Despite that, the research results seem to be promising and the authors believe in the usefulness of the further development of measurement method along with its extension to other trees species.
Access status: Restricted ,
Hipoteza Erdősa-Sós
(Data obrony: 2009-10-15) Pieczka, Marcelina
Wydział Matematyki Stosowanej
Access status: Restricted ,
Indeks rozróżniający grafów planarnych
(Data obrony: 2017-07-25) Pal, Katarzyna
Wydział Matematyki Stosowanej
Access status: Open Access ,
More on linear and metric tree maps
(Wydawnictwa AGH, 2021) Kozerenko, Sergìj Oleksandrovič
We consider linear and metric self-maps on vertex sets of finite combinatorial trees. Linear maps are maps which preserve intervals between pairs of vertices whereas metric maps are maps which do not increase distances between pairs of vertices. We obtain criteria for a given linear or a metric map to be a positive (negative) under some orientation of the edges in a tree, we characterize trees which admit maps with Markov graphs being paths and prove that the converse of any partial functional digraph is isomorphic to a Markov graph for some suitable map on a tree.
Access status: Restricted ,
O zanurzaniu lasów ustalonego rozmiaru
(Data obrony: 2013-10-29) Pawińska, Karolina
Wydział Matematyki Stosowanej
Access status: Open Access ,
On Fibonacci numbers in edge coloured trees
(Wydawnictwa AGH, 2017) Bednarz, Urszula; Bród, Dorota; Szynal-Liana, Anetta; Włoch, Iwona; Wołowiec-Musiał, Małgorzata
In this paper we show the applications of the Fibonacci numbers in edge coloured trees. We determine the second smallest number of all $(A,2B)$-edge colourings in trees. We characterize the minimum tree achieving this second smallest value.
Access status: Open Access ,
On the multiplicative Zagreb coindex of graphs
(2013) Xu, Kexiang; Das, Kinkar Chandra; Tang, Kechao
For a (molecular) graph $G$ with vertex set $V(G)$ and edge set $E(G)$, the first and second Zagreb indices of $G$ are defined as $M_1(G) = \sum_{v \in V(G)} d_G(v)^2$ and $M_2(G) = \sum_{uv \in E(G)} d_G(u)d_G(v)$, respectively, where $d_{G}(v)$ is the degree of vertex $v$ in $G$. The alternative expression of $M_1(G)$ is $\sum_{uv \in E(G)}(d_G(u) + d_G(v))$. Recently Ashrafi, Došlić and Hamzeh introduced two related graphical invariants $\overline{M}_1(G) = \sum_{uv \notin E(G)}(d_G(u)+d_G(v))$ and $\overline{M}_2(G) = \sum_{uv \notin E(G)} d_G(u)d_G(v)$ named as first Zagreb coindex and second Zagreb coindex, respectively. Here we define two new graphical invariants $\overline{\Pi}_1(G) = \prod_{uv \notin E(G)}(d_G(u)+d_G(v))$ and $\overline{\Pi}_2(G) = \prod_{uv \notin E(G)} d_G(u)d_G(v)$ as the respective multiplicative versions of $\overline{M}_i$ for $i=1,2$. In this paper, we have reported some properties, especially upper and lower bounds, for these two graph invariants of connected (molecular) graphs. Moreover, some corresponding extremal graphs have been characterized with respect to these two indices.
Access status: Restricted ,
Podziały krawędziowe grafów gęstych
(Data obrony: 2018-07-16) Hubert, Maciej
Wydział Matematyki Stosowanej
Access status: Open Access ,
Seven largest trees pack
(Wydawnictwa AGH, 2024) Cisiński, Maciej; Żak, Andrzej
The Tree Packing Conjecture (TPC) by Gyárfás states that any set of trees $T_2,\dots,T_{n-1}, T_n$ such that $T_i$ has $i$ vertices pack into $K_n$. The conjecture is true for bounded degree trees, but in general, it is widely open. Bollobás proposed a weakening of TPC which states that $k$ largest trees pack. The latter is true if none tree is a star, but in general, it is known only for $k=5$. In this paper we prove, among other results, that seven largest trees packThe Tree Packing Conjecture (TPC) by Gyárfás states that any set of trees $T_2,\dots,T_{n-1}, T_n$ such that $T_i$ has $i$ vertices pack into $K_n$. The conjecture is true for bounded degree trees, but in general, it is widely open. Bollobás proposed a weakening of TPC which states that $k$ largest trees pack. The latter is true if none tree is a star, but in general, it is known only for $k=5$. In this paper we prove, among other results, that seven largest trees pack
Access status: Restricted ,
Silne kolorowania krawędziowe grafów
(Data obrony: 2013-10-30) Koniecka, Żaneta
Wydział Matematyki Stosowanej
Access status: Open Access ,
The extensive 1-median problem with radius on networks
(Wydawnictwa AGH, 2024) Nhân, Trần Hoài Ngọc; Nguyên, Thanh-hùng; Nguyễn, Kiên Trung
The median location problem concerns finding locations of one or several new facilities that minimize the overall weighted distances from the existing to the new facilities. We address the problem of locating one new facility with a radius $r$ on networks. Furthermore, the radius $r$ is flexible and the objective function is the conic combination of the traditional 1-median function and the value $r$. We call this problem an extensive 1-median problem with radius on networks. To solve the problem, we first induce the so-called finite dominating set, that contains all points on the underlying network and radius values which are candidate for the optimal solution of the problem. This helps to develop a combinatorial algorithm that solves the problem on a general network $G=(V,E)$ in $O(|E||V|^3)$ time. We also consider the underlying problem with improved algorithm on trees. Based the convexity of the objective function with variable radius, we develop a linear time algorithm to find an extensive 1-median with radius on the underlying tree.
Access status: Open Access ,
Total connected domination game
(Wydawnictwa AGH, 2021) Bujtás, Csilla; Henning, Michael A.; Iršič, Vesna; Klavžar, Sandi
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_{\rm tcg}(G)$) $\gamma_{\rm cg}(G)$ of $G$. We show that $\gamma_{\rm tcg}(G) \in \{\gamma_{\rm cg}(G),\gamma_{\rm cg}(G) + 1,\gamma_{\rm cg}(G) + 2\}$, and consequently define $G$ as Class $i$ if $\gamma_{\rm tcg}(G) = \gamma_{\rm cg} + 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 minumum 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.
Access status: Open Access ,
Upper bounds on distance vertex irregularity strength of some families of graphs
(Wydawnictwa AGH, 2022) Cichacz-Przeniosło, Sylwia; Görlich, Agnieszka; Semaničová-Feňovčíková, Andrea
For a graph $G$ its distance vertex irregularity strength is the smallest integer $k$ for which one can find a labeling $f: V(G)\to \{1, 2, \dots, 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.
Access status: Restricted ,
Wdzięczne etykietowanie drzew
(Data obrony: 2014-09-30) Szewczyk, Beata
Wydział Matematyki Stosowanej