자가완성 그래프
Self-complementary graph
자기 보완 그래프는 그 보완점에 대해 이형화된 그래프다.가장 간단한 비교 자기 완성 그래프는 4Vertex 경로 그래프와 5Vertex 주기 그래프다.자기 완성 그래프의 알려진 특성화는 없다.
예
모든 Paley 그래프는 자기 완성형이다.[1]예를 들어, 3 × 3 루크의 그래프(순서 9의 창백한 그래프)는 중심 정점은 유지하되 4측 중간점과 격자의 4개 모서리의 역할을 교환하는 대칭에 의해 자기 완성형이다.[2]37 꼭지점 이하인 강력 정규 자기 완성 그래프는 모두 Paley 그래프지만 37, 41, 49 꼭지점에 Paley 그래프가 아닌 강력한 정규 그래프가 있다.[3]
특성.
n-vertex 자가 완성 그래프는 전체 그래프의 정확히 절반의 에지 수를 가지고 있다. 즉, n(n - 1)/4 에지, (두 개의 꼭지점이 있을 경우) 직경이 2 또는 3이어야 한다.[1]n(n -1)은 4로 분할해야 하므로 n은 0 또는 1모드 4로 합치되어야 한다. 예를 들어, 6-Vertex 그래프는 자체 보완적일 수 없다.
계산 복잡성
두 개의 자기 완성 그래프가 이형인지 확인하는 문제와 주어진 그래프가 자기 완성인지 확인하는 문제는 일반적인 그래프 이형성 문제와 동등한 다항 시간이다.[5]
참조
- ^ a b Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen, 9: 270–288, MR 0151953.
- ^ Shpectorov, S. (1998), "Complementary l1-graphs", Discrete Mathematics, 192 (1–3): 323–331, doi:10.1016/S0012-365X(98)0007X-1, MR 1656740.
- ^ Rosenberg, I. G. (1982), "Regular and strongly regular selfcomplementary graphs", Theory and practice of combinatorics, North-Holland Math. Stud., vol. 60, Amsterdam: North-Holland, pp. 223–238, MR 0806985.
- ^ Cameron, Peter J. (1997), "The random graph", The mathematics of Paul Erdős, II, Algorithms Combin., vol. 14, Berlin: Springer, pp. 333–351, arXiv:1301.7544, Bibcode:2013arXiv1301.7544C, MR 1425227. 제안 5를 참조하십시오.
- ^ Colbourn, Marlene J.; Colbourn, Charles J. (1978), "Graph isomorphism and self-complementary graphs", SIGACT News, 10 (1): 25–29, doi:10.1145/1008605.1008608.
