On the skewness of Cartesian products with trees

被引：3

作者：

Ouyang, Zhangdong ^{[1
]}

Dong, Fengming ^{[2
]}

Tay, Eng Guan ^{[2
]}

机构：

[1] Hunan First Normal Univ, Sch Math & Computat Sci, Changsha 410205, Hunan, Peoples R China

[2] Nanyang Technol Univ, Math & Math Educ, Natl Inst Educ, Singapore 637616, Singapore

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 267卷

基金：

中国国家自然科学基金;

关键词：

Skewness of graph; Cartesian product; Zip product; Tree; CROSSING NUMBERS; GRAPHS;

D O I：

10.1016/j.dam.2019.05.014

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. It is a parameter that measures how non-planar a graph is, and it also has important applications to VLSI design, but there are few results for skewness of graphs. In this paper, we first prove that the skewness is additive for the Zip product under certain conditions. We then present results on the lower bounds for the skewness of Cartesian products of graphs with trees and paths, respectively. Some exact values of the skewness for Cartesian products of complete graphs with trees, as well as of stars and wheels with paths are obtained by applying these lower bounds. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：131 / 141

页数：11

共 21 条

[1] On the crossing numbers of Cartesian products with trees [J].