Probe Ptolemaic Graphs

摘要：

Given a class of graphs, G, a graph G is a probe graph of G if its vertices can be partitioned into two sets, P (the probes) and N (the nonprobes), where N is an independent set, such that G can be embedded into a graph of Q by adding edges between certain nonprobes. In this paper we study the probe graphs of ptolemaic graphs when the partition of vertices is unknown. We present some characterizations of probe ptolemaic graphs and show that there exists a polynomial-time recognition algorithm for probe ptolemaic graphs.

作者: David B. Chandler Maw-Shang Chang Ton Kloks Van Bang Le Sheng-Lung Peng

作者单位: Department of Mathematical Sciences University of Delaware Newark, Delaware 19716, USA Department of Computer Science and Information Engineering National Chung Cheng University, Chiayi 6 Institut für Informatik, Universitat Rostock, 18051 Rostock, Germany Department of Computer Science and Information Engineering National Dong Hwa University, Hualien 974

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 468-477

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）