Browsing by Subject "cyclic permutation"

Now showing 1 - 3 of 3

Access status: Open Access ,
On the crossing numbers of join products of five graphs of order six with the discrete graph
(Wydawnictwa AGH, 2020) Staš, Michal
The main purpose of this article is broaden known results concerning crossing numbers for join of graphs of order six. We give the crossing number of the join product $G^{\ast}+D_{n}$, where the disconnected graph $G^{\ast}$ of order six consists of one isolated vertex and of one edge joining two nonadjacent vertices of the $5$-cycle. In our proof, the idea of cyclic permutations and their combinatorial properties will be used. Finally, by adding new edges to the graph $G^{\ast}$, the crossing numbers of $G_{i}+D_{n}$ for four other graphs $G_{i}$ of order six will be also established.
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 ,
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$.