The Crossing Number of Flower Snarks and Related Graphs

Wenping, Zheng; Xiaohui, Lin; Yuansheng, Yang; Xiwu, Yang

Abstract

References

Ars Combinatoria

Volume 086
Pages: 57-64

Research article

The Crossing Number of Flower Snarks and Related Graphs

^¹,², ^³, ^³, ^¹

¹Department of Computer Science, Dalian University of Technology, Dalian, 116024, P. R. China

²School of Computer and Information Technology, Shanxi University, Taiyuan, 030006, P. R. China,

³ Department of Computer Science, Dalian University of Technology, Dalian, 116024, P. R. China

Published: 31/01/2008

Copyright Link
License

Abstract

For odd $n \geq 5$ , the Flower Snark $F_{n} = (V, E)$ is a simple undirected cubic graph with $4 n$ vertices, where $V = {a_{i} : 0 \leq i \leq n - 1} \cup {b_{i} : 0 \leq i \leq n - 1} \cup {c_{i} : 0 \leq i \leq 2 n - 1}$ and $E = {b_{i} b_{(i + 1) \mod (n)} : 0 \leq i \leq n - 1} \cup {c_{i} c_{(i + 1) \mod (2 n)} : 0 \leq i \leq 2 n - 1} \cup {a_{i} b_{i}, a_{i} c_{i}, a_{i} c_{n + i} : 0 \leq i \leq n - 1}$ . For $n = 3$ or even $n \geq 4$ , $F_{n}$ is called the related graph of Flower Snark. We show that the crossing number of $F_{n}$ equals $n - 2$ if $3 \leq n \leq 5$ , and $n$ if $n \geq 6$ .

Contents

Ars Combinatoria

The Crossing Number of Flower Snarks and Related Graphs

Abstract

Information

Guidelines

CP Initiatives

Follow CP