The Crossing Number of Join Product of kth Power of Path Pm with Isolated Vertices and Path Pn

Sun Yuan Hsieh; Cheng Chian Lin

doi:10.1109/ICS.2016.0021

The Crossing Number of Join Product of kth Power of Path P_m with Isolated Vertices and Path P_n

Sun Yuan Hsieh, Cheng Chian Lin

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

A graph G is said to have a crossing if two edges of G share an interior point. The minimum crossing number of G is denoted by cr(G). The crossing number problem is to find the minimum crossing solution of a graph, and it can be used in applications of circuit layout. Although the crossing numbers of join product graphs have been extensively studied, the crossing number of join product of power graphs with path is relatively unexplored. Let P_m and P_n be paths with m and n vertices, and D_n be a graph consisting of n isolated vertices. In this paper, we investigate the crossing number of kth power of path P_m that joins with isolated vertices D_n and path P_n. We have proved the minimum crossing numbers of P^k _m+D_n for m ≤ 6, n ≥ 1, and P^k _m+P_n for m ≤ 6, n ≥ 2.

Original language	English
Title of host publication	Proceedings - 2016 International Computer Symposium, ICS 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	62-67
Number of pages	6
ISBN (Electronic)	9781509034383
DOIs	https://doi.org/10.1109/ICS.2016.0021
Publication status	Published - 2017 Feb 16
Event	2016 International Computer Symposium, ICS 2016 - Chiayi, Taiwan Duration: 2016 Dec 15 → 2016 Dec 17

Publication series

Name	Proceedings - 2016 International Computer Symposium, ICS 2016

Other

Other	2016 International Computer Symposium, ICS 2016
Country/Territory	Taiwan
City	Chiayi
Period	16-12-15 → 16-12-17

All Science Journal Classification (ASJC) codes

Computer Vision and Pattern Recognition
Hardware and Architecture
Computer Networks and Communications
Computer Science Applications

Access to Document

10.1109/ICS.2016.0021

Cite this

Hsieh, S. Y., & Lin, C. C. (2017). The Crossing Number of Join Product of kth Power of Path P_m with Isolated Vertices and Path P_n. In Proceedings - 2016 International Computer Symposium, ICS 2016 (pp. 62-67). Article 7858443 (Proceedings - 2016 International Computer Symposium, ICS 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICS.2016.0021

@inproceedings{84357312655d43719e35c483da436870,

title = "The Crossing Number of Join Product of kth Power of Path Pm with Isolated Vertices and Path Pn",

abstract = "A graph G is said to have a crossing if two edges of G share an interior point. The minimum crossing number of G is denoted by cr(G). The crossing number problem is to find the minimum crossing solution of a graph, and it can be used in applications of circuit layout. Although the crossing numbers of join product graphs have been extensively studied, the crossing number of join product of power graphs with path is relatively unexplored. Let Pm and Pn be paths with m and n vertices, and Dn be a graph consisting of n isolated vertices. In this paper, we investigate the crossing number of kth power of path Pm that joins with isolated vertices Dn and path Pn. We have proved the minimum crossing numbers of Pk m+Dn for m ≤ 6, n ≥ 1, and Pk m+Pn for m ≤ 6, n ≥ 2.",

author = "Hsieh, {Sun Yuan} and Lin, {Cheng Chian}",

year = "2017",

month = feb,

day = "16",

doi = "10.1109/ICS.2016.0021",

language = "English",

series = "Proceedings - 2016 International Computer Symposium, ICS 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "62--67",

booktitle = "Proceedings - 2016 International Computer Symposium, ICS 2016",

address = "United States",

note = "2016 International Computer Symposium, ICS 2016 ; Conference date: 15-12-2016 Through 17-12-2016",

}

Hsieh, SY & Lin, CC 2017, The Crossing Number of Join Product of kth Power of Path P_m with Isolated Vertices and Path P_n. in Proceedings - 2016 International Computer Symposium, ICS 2016., 7858443, Proceedings - 2016 International Computer Symposium, ICS 2016, Institute of Electrical and Electronics Engineers Inc., pp. 62-67, 2016 International Computer Symposium, ICS 2016, Chiayi, Taiwan, 16-12-15. https://doi.org/10.1109/ICS.2016.0021

The Crossing Number of Join Product of kth Power of Path P_m with Isolated Vertices and Path P_n. / Hsieh, Sun Yuan; Lin, Cheng Chian.
Proceedings - 2016 International Computer Symposium, ICS 2016. Institute of Electrical and Electronics Engineers Inc., 2017. p. 62-67 7858443 (Proceedings - 2016 International Computer Symposium, ICS 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The Crossing Number of Join Product of kth Power of Path Pm with Isolated Vertices and Path Pn

AU - Hsieh, Sun Yuan

AU - Lin, Cheng Chian

PY - 2017/2/16

Y1 - 2017/2/16

N2 - A graph G is said to have a crossing if two edges of G share an interior point. The minimum crossing number of G is denoted by cr(G). The crossing number problem is to find the minimum crossing solution of a graph, and it can be used in applications of circuit layout. Although the crossing numbers of join product graphs have been extensively studied, the crossing number of join product of power graphs with path is relatively unexplored. Let Pm and Pn be paths with m and n vertices, and Dn be a graph consisting of n isolated vertices. In this paper, we investigate the crossing number of kth power of path Pm that joins with isolated vertices Dn and path Pn. We have proved the minimum crossing numbers of Pk m+Dn for m ≤ 6, n ≥ 1, and Pk m+Pn for m ≤ 6, n ≥ 2.

AB - A graph G is said to have a crossing if two edges of G share an interior point. The minimum crossing number of G is denoted by cr(G). The crossing number problem is to find the minimum crossing solution of a graph, and it can be used in applications of circuit layout. Although the crossing numbers of join product graphs have been extensively studied, the crossing number of join product of power graphs with path is relatively unexplored. Let Pm and Pn be paths with m and n vertices, and Dn be a graph consisting of n isolated vertices. In this paper, we investigate the crossing number of kth power of path Pm that joins with isolated vertices Dn and path Pn. We have proved the minimum crossing numbers of Pk m+Dn for m ≤ 6, n ≥ 1, and Pk m+Pn for m ≤ 6, n ≥ 2.

UR - http://www.scopus.com/inward/record.url?scp=85015328277&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015328277&partnerID=8YFLogxK

U2 - 10.1109/ICS.2016.0021

DO - 10.1109/ICS.2016.0021

M3 - Conference contribution

AN - SCOPUS:85015328277

T3 - Proceedings - 2016 International Computer Symposium, ICS 2016

SP - 62

EP - 67

BT - Proceedings - 2016 International Computer Symposium, ICS 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 International Computer Symposium, ICS 2016

Y2 - 15 December 2016 through 17 December 2016

ER -