Browsing by Subject "path"

Now showing 1 - 10 of 10

Access status: Restricted ,
Cykle i ścieżki w turniejach
(Data obrony: 2016-10-24) Szwed, Gabriela
Wydział Matematyki Stosowanej
Access status: Restricted ,
Hipoteza Erdősa-Sós
(Data obrony: 2009-10-15) Pieczka, Marcelina
Wydział Matematyki Stosowanej
Access status: Restricted ,
Implementacja i testy algorytmu A*W
(Data obrony: 2017-01-24) Krzeszowiak, Mateusz
Wydział Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej
Access status: Restricted ,
Liczba Ramseya dla ścieżek w grafach spełniających warunek typu Orego
(Data obrony: 2017-07-26) Kościołek, Izabela
Wydział Matematyki Stosowanej
Access status: Restricted ,
O problemach wierzchołkowej stabilności w grafach
(Data obrony: 2012-09-27) Michałek, Natalia
Wydział Matematyki Stosowanej
Access status: Open Access ,
On the crossing numbers of join products of W4+Pn and W4+Cn
(Wydawnictwa AGH, 2021) Staš, Michal; Valiska, Juraj
The crossing number $cr(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. The main aim of the paper is to give the crossing number of the join product $W_{4}+P_{n}$ and $W_{4}+C_{n}$ for the wheel $W_4$ on five vertices, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. Yue et al. conjectured that the crossing number of $W_{m}+C_{n}$ is equal to $Z(m+1)Z(n)+(Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n+ \big\lceil\frac{m}{2}\big\rceil +2$, for all $m,n \geq 3$, and where the Zarankiewicz's number $Z(n)=\big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor$ is defined for $n \geq 1$. Recently, this conjecture was proved for $W_{3}+C_{n}$ by Klešč. We establish the validity of this conjecture for $W_{4}+C_{n}$ and we also offer a new conjecture for the crossing number of the join product $W_{m}+P_{n}$ for $m \geq 3$ and $n \geq 2$.
Access status: Open Access ,
On the path partition of graphs
(Wydawnictwa AGH, 2023) Kouider, Mekkia; Zamime, Mohamed
Let $G$ be a graph of order $n$. The maximum and minimum degree of $G$ are denoted by $\Delta$ and $\delta$, respectively. The path partition number $\mu(G)$ of a graph $G$ is the minimum number of paths needed to partition the vertices of $G$. Magnant, Wang and Yuan conjectured that $\mu(G)\leq\max \left\{\frac{n}{\delta+1},\frac{(\Delta-\delta)n}{\Delta+\delta}\right\}.$ In this work, we give a positive answer to this conjecture, for $\Delta \geq 2\delta$.
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 ,
The crossing numbers of join products of four graphs of order five with paths and cycles
(Wydawnictwa AGH, 2023) Staš, Michal; Timková, Mária
The crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join products $G^\ast + P_n$ and $G^\ast + C_n$ for the disconnected graph $G^\ast$ consisting of the complete tripartite graph $K_{1,1,2}$ and one isolated vertex are given, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. In the paper also the crossing numbers of $H^{\ast}+P_{n}$ and $H^{\ast}+C_{n}$ are determined, where $H^{\ast}$ is isomorphic to the complete tripartite graph $K_{1,1,3}$. Finally, by adding new edges to the graphs $G^\ast$ and $H^\ast$, we are able to obtain crossing numbers of join products of two other graphs $G_1$ and $H_1$ with paths and cycles.
Access status: Open Access ,
The crossing numbers of join products of paths with three graphs of order five
(Wydawnictwa AGH, 2022) Staš, Michal; Švecová, Mária
The main aim of this paper is to give the crossing number of the join product $G^\ast+P_n$ for the disconnected graph $G^\ast$ of order five consisting of the complete graph $K_4$ and one isolated vertex, where $P_n$ is the path on n vertices. The proofs are done with the help of a lot of well-known exact values for the crossing numbers of the join products of subgraphs of the graph $G^\ast$ with the paths. Finally, by adding new edges to the graph $G^\ast$, we are able to obtain the crossing numbers of the join products of two other graphs with the path $P_n$.