Wyniki wyszukiwania - BazTech

1

The crossing numbers of join products of four graphs of order five with paths and cycles

Staš Michal, Timková Mária

Opuscula Mathematica

|

2023

|

Vol. 43, no. 6

865--883

EN

The crossing number 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∗ + Pn and G∗ + Cn for the disconnected graph G∗ consisting of the complete tripartite graph K1,1,2 and one isolated vertex are given, where Pn and Cn are the path and the cycle on n vertices, respectively. In the paper also the crossing numbers of H∗ + Pn and H∗ + Cn are determined, where H∗ is isomorphic to the complete tripartite graph K1,1,3. Finally, by adding new edges to the graphs G∗ and H∗, we are able to obtain crossing numbers of join products of two other graphs G1 and H1 with paths and cycles.

2

Every graph is local antimagic total and its applications

Lau Gee-Choon, Schaffer Karl, Shiu Wai-Chee

Opuscula Mathematica

|

2023

|

Vol. 43, no. 6

841--864

EN

Let G = (V,E) be a simple graph of order p and size q. A graph G is called local antimagic (total) if G admits a local antimagic (total) labeling. A bijection g : E → {1, 2, . . . , q} is called a local antimagic labeling of G if for any two adjacent vertices u and v, we have g+(u)≠g+(v), where g+(u) = ∑e∈E(u) g(e), and E(u) is the set of edges incident to u. Similarly, a bijection f : V (G)∪E(G) → {1, 2, . . . , p+q} is called a local antimagic total labeling of G if for any two adjacent vertices u and v, we have wf (u)≠wf (v), where wf (u) = f(u) + ∑e∈E(u) f(e). Thus, any local antimagic (total) labeling induces a proper vertex coloring of G if vertex v is assigned the color g+(v) (respectively, wf (u)). The local antimagic (total) chromatic number, denoted χla(G) (respectively χlat(G)), is the minimum number of induced colors taken over local antimagic (total) labeling of G. We provide a short proof that every graph G is local antimagic total. The proof provides sharp upper bound to χlat(G). We then determined the exact χlat(G), where G is a complete bipartite graph, a path, or the Cartesian product of two cycles. Consequently, the χla(G ∨ K1) is also obtained. Moreover, we determined the χla(G ∨ K1) and hence the χlat(G) for a class of 2-regular graphs G (possibly with a path). The work of this paper also provides many open problems on χlat(G). We also conjecture that each graph G of order at least 3 has χlat(G) ≤ χla(G).

3

The crossing numbers of join products of paths with three graphs of order five

Staš Michal, Švecová Mária

Opuscula Mathematica

|

2022

|

Vol. 42, no. 4

635--651

EN

The main aim of this paper is to give the crossing number of the join product G∗ + Pn for the disconnected graph G∗ of order five consisting of the complete graph K4 and one isolated vertex, where Pn 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∗ with the paths. Finally, by adding new edges to the graph G∗, we are able to obtain the crossing numbers of the join products of two other graphs with the path Pn.

4

On the crossing numbers of join products of W4 + Pn and W4 + Cn

Stas Michal, Valiska Juraj

Opuscula Mathematica

|

2021

|

Vol. 41, no. 1

95-112

EN

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 W4 + Pn and W4 + Cn for the wheel W4 on five vertices, where Pn and Cn are the path and the cycle on n vertices, respectively. Yue et al. conjectured that the crossing number of Wm + Cn is equal to [formula], for all m,n ≥ 3, and where the Zarankiewicz’s number[formula] is defined for n ≥ 1. Recently, this conjecture was proved for W3 + Cn by Klesc. We establish the validity of this conjecture for W4 + Cn and we also offer a new conjecture for the crossing number of the join product Wm + Pn for m ≥ 3 and n ≥ 2.

5

On the crossing numbers of join products of five graphs of order six with the discrete graph

Stas Michal

Opuscula Mathematica

|

2020

|

Vol. 40, no. 3

383--397

EN

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* + Dn, where the disconnected graph G* 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*, the crossing numbers of Gi + Dn for four other graphs Gi of order six will be also established