프톨레마이오스 그래프

Ptolemaic graph
프톨레마이오스 그래프
보석 그래프나 3-팬은 Ptolemaic이 아니다.
블록 그래프, Ptolemaic 그래프의 특별한 경우
거리-연속 그래프를 구성할 수 있는 세 가지 연산. 프톨레마이크 그래프의 경우, 가짜 쌍둥이의 이웃이 패거리 형성을 제한하여 여기에 나타난 4사이클의 건설을 방해한다.

그래프 이론에서 프톨레마이오스 그래프최단 경로 거리가 프톨레마이오스의 불평등을 따르는 비방향 그래프로, 그리스 천문학자수학자 프톨레마이오스의 이름을 따서 명명되었다. Ptolemaic 그래프는 정확히 코드와 거리-계통 그래프[1] 모두 포함하는 그래프로서, 블록 그래프를 포함하고 완벽한 그래프의 하위 등급이다.

특성화

그래프는 다음과 같은 동등한 조건을 준수하는 경우에만 Ptolemaic이다.

  • 최단 경로 거리는 프톨레마이오스의 불평등을 따른다: 4개의 꼭지점 u, v, w, x마다 불평등 d(u,v)d(w,x) + d(u,x)d(v,w) , d(u,w)d(v,x) hold.[1] 예를 들어 이 그래프 d(u,w)d(v,x) = 4, d(u,v)d(w,x) + d(u,x)d(v,w) = 3보다 크기 때문에 그림의 보석 그래프(3-fan)는 Ptolemaic이 아니다.
  • 겹치는 두 개의 최대 패거리에 대해 두 패밀리의 교차점은 두 패밀리의 차이를 분할하는 분리형이다.[2] 보석 그래프의 그림에서 이것은 사실이 아니다: clique uvywxy는 교차로에 의해 분리되지 않는다. clique를 연결하지만 교차로에는 교차를 피하는 엣지 vw가 있기 때문이다.
  • 모든 k-vertex 사이클에는 적어도 3(k - 3)/2개의 대각선이 있다.[2]
  • 그래프는 코드(길이 3보다 큰 모든 사이클은 대각선으로 표시됨)와 거리 계통(연결된 모든 유도 하위그래프는 전체 그래프와 동일한 거리를 가진다)[2]이다. 표시된 보석은 화음이지만 거리-계통은 아니다: ubwx에 의해 유도된 서브그래프에서 u에서 x까지의 거리는 3으로 전체 그래프에서 동일한 정점 사이의 거리보다 크다. 왜냐하면 화음 그래프와 거리 계통 그래프는 모두 완벽한 그래프이기 때문에 프톨레마이오스 그래프도 마찬가지다.[3]
  • 그래프는 화음이며 유도된 보석을 포함하지 않는다. 이 그래프는 두 개의 교차하지 않는 대각선을 오각형에 추가함으로써 형성된다.[3]
  • 그래프는 거리 계통이며 유도 4 사이클을 포함하지 않는다.[4]
  • 그래프는 새로운 도원(진자) 정점을 추가하거나 기존 정점을 중복(승자)하는 일련의 연산에 의해 단일 정점에서 구성할 수 있으며, 예외적으로 새로운 중복 정점이 쌍둥이에 인접하지 않는 쌍둥이 연산은 쌍둥이의 이웃이 패거리를 형성할 때만 적용할 수 있다. 이 세 가지 작업은 예외 없이 모든 거리-연속 그래프를 형성한다. 모든 Ptolemaic 그래프를 형성하기 위해, 펜던트 정점과 트윈스를 사용하는 것만으로는 충분하지 않다; 때때로 거짓 쌍둥이의 예외적인 사례도 필요하다.[5]
  • 최대 집단의 비어 있지 않은 교차점에 대한 부분 집합 관계의 Hasse 다이어그램지향적인 트리를 형성한다.[6]
  • 정점의 볼록 부분 집합(부분집합에서 두 정점 사이의 모든 최단 경로를 포함하는 하위 집합)은 볼록 형상을 형성한다. 즉, 모든 볼록 세트는 나머지 정점 사이의 어떤 최단 경로에도 속하지 않는 극한 정점을 반복적으로 제거함으로써 설정된 전체 정점에서 도달할 수 있다.[7] 보석에서 볼록 세트 uxyv도 w도 극단적이지 않기 때문에 이런 식으로 도달할 수 없다.

계산 복잡성

지향적인 나무에 의한 특성화를 바탕으로 프톨레마이오스 그래프를 선형적으로 인식할 수 있다.[6]

열거

Ptolemaic 그래프의 생성 함수상징적으로 설명할 수 있어 이러한 그래프의 수를 신속하게 계산할 수 있다. 방법에 따라, =1, ,,…에 대해 정점이 n개인 Ptolemaic 그래프의 수는 [8] 같은 것으로 밝혀졌다

1, 1, 4, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 10199156831963, …(OEIS의 경우 연속 A2878866)

참조

  1. ^ a b Kay, David C.; Chartrand, Gary (1965), "A characterization of certain ptolemaic graphs", Canadian Journal of Mathematics, 17: 342–346, doi:10.4153/CJM-1965-034-0, hdl:10338.dmlcz/126208, MR 0175113.
  2. ^ a b c Howorka, Edward (1981), "A characterization of Ptolemaic graphs", Journal of Graph Theory, 5 (3): 323–331, doi:10.1002/jgt.3190050314, MR 0625074.
  3. ^ a b "Graphclass: ptolemaic", Information System on Graph Classes and their Inclusions, retrieved 2016-06-05.
  4. ^ McKee, Terry A. (2010), "Clique graph representations of Ptolemaic graphs", Discussiones Mathematicae Graph Theory, 30 (4): 651–661, doi:10.7151/dmgt.1520, MR 2761626.
  5. ^ Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, MR 0859310.
  6. ^ a b Uehara, Ryuhei; Uno, Yushi (2009), "Laminar structure of Ptolemaic graphs with applications", Discrete Applied Mathematics, 157 (7): 1533–1543, doi:10.1016/j.dam.2008.09.006, MR 2510233.
  7. ^ Farber, Martin; Jamison, Robert E. (1986), "Convexity in graphs and hypergraphs", SIAM Journal on Algebraic and Discrete Methods, 7 (3): 433–444, doi:10.1137/0607049, hdl:10338.dmlcz/127659, MR 0844046.
  8. ^ Bahrani, Maryam; Lumbroso, Jérémie (2018), "Enumerations, forbidden subgraph characterizations, and the split-decomposition", Electronic Journal of Combinatorics, 25 (4)