6K-04
カクタスグラフにおけるGeneral position problem について
○木村俊彦,金 鎔煥,片山喜章(名工大)
グラフG=(V,E)におけるS⊆Vで, GにおけるSの任意の2頂点間の全ての最短経路にSの頂点が3頂点以上含まれないときSをgeneral position set(gps)という.与えられたGにおけるgpsのサイズの最大値を general position number(gpn)といい,gpnを求める問題をgeneral position problem(gpp)という. 既存研究では,特定の条件を満たすカクタスグラフのgpnについて知られている. 本研究では, 任意のカクタスグラフのgpnを示す.