지름이 2인 그래프에서의 상호 가시성 문제

그래프 G에서의 상호 가시성 문제는 집합 S⊆V(G)의 최대 크기를 묻는 것으로, S에 속하는 두 정점 x,y∈S에 대해 모든 내부 정점이 S에 속하지 않는 최단 x,y-경로 P가 존재해야 한다. 이는 x,y가 S에 대해 가시적이라고도 하며, 줄여서 S-가시적이라고 한다. 이 문제의 변형은 S 내부 및/또는 외부에 있는 정점의 가시성 특성의 확장에 따라 알려져 있다. 이러한 변형을 전체, 외부 및 이중 상호 가시성 문제라고 한다. 이 연구는 지름이 2인 그래프에서 해당 네 가지 가시성 매개변수를 연구하는 데 집중하며, 이러한 매개변수에 대한 경계 및/또는 닫힌 공식들을 보여준다. 두 개의 완전 그래프의 카르테시안 곱에서의 상호 가시성 문제는 유명한 자란키에비츠 문제의 (한 사례로서의) 동등하다. 여기에서는 두 개의 완전 그래프의 카르테시안 곱에 대한 이중 및 외부 상호 가시성 문제와 그러한 그래프의 직접곱에 대한 모든 상호 가시성 문제를 연구한다. 또한 완전 그래프와 완전 이분 그래프의 선 그래프에 대한 모든 상호 가시성 문제를 연구한다. 이 연구의 결과로, 언급된 문제들 간의 여러 관계와 고전적인 투란 문제의 몇 가지 사례를 제시한다. 더 나아가, cograph 및 최소 크기의 여러 비자명 지름 2 그래프에 대한 가시성 문제를 연구한다.