그래프의 주파수 파티션

그래프 이론, 수학 내에서의 부문, 그래프의 주파수 분할(단순 그래프)은 그 정도별로 그룹화된 정점의 분할이다.예를 들어, 아래 왼쪽 그래프의 도 순서는 (3, 3, 3, 2, 1)이고 주파수 파티션은 6 = 3 + 2 + 1이다.이것은 어느 정도 정점 3개, 어느 정도 다른 정도 정점 2개, 그리고 3도 정점 1개를 가지고 있다는 것을 나타낸다.아래 가운데에 있는 초당적 그래프의 도 순서는 (3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1)이며 빈도 분할은 9 = 5 + 3 + 1이다.아래 오른쪽 그래프의 도 순서는 (3, 3, 3, 3, 3, 3, 3, 2,)이며 주파수 파티션은 7 = 6 + 1이다.

• 

  주파수 분할이 6 = 3 + 2 + 1인 그래프.

• 

  주파수 분할이 9 = 5 + 3 + 1인 초당적 그래프.

• 

  주파수 분할이 7 = 6 + 1인 그래프.

일반적으로 주어진 주파수 분할을 가진 비이성형 그래프가 많다.그래프와 그 보완물은 동일한 주파수 분할을 가진다.파티션 p = f₂ + f₁ + ...+ 정수 p > 1의 f_k, p = 1 + 1 + 1 + ... 이외의 경우+ 1, 이 파티션을 주파수 파티션으로 하는 적어도 하나의 (연결된) 간단한 그래프가 있다.^[1]

다양한 그래프 패밀리의 주파수 파티션은 완전히 식별되며, 많은 그래프 패밀리의 주파수 파티션은 식별되지 않는다.

오일러 그래프의 주파수 파티션

주파수 파티션 p = f₂ + f₁ + ...정수 p의+fk, 1, 이의 그래픽 정도 시퀀스((1)f1,(d2)f2,())f3,...,(dk)fk)로 표시됩니다. 어디도 디들이 다르고fi ≥ fj에 나는 <, j.Bhat-Nayak(알.(1979년)는 오일러 그래프의 p의 k부품, k≤(p1−)/2{\displaystyle(p-1)/2}의 전체 부분이 파티션은 주파수 partition[2]다와 반대로 보여 주었다.

트리, 해밀턴 그래프, 토너먼트 및 과대 광고의 주파수 분할

나무,^[3] 해밀턴 그래프와^[4] 같은 그래프 패밀리의 빈도 칸막이는 그래프와^[5] 토너먼트, 그리고 K-uniform 하이퍼그래프를 지시하였다.^[6]특색이 있다

빈도 파티션에서 해결되지 않은 문제

다음 그래프 패밀리의 주파수 파티션은 아직 특징이 없다.

• 선 그래프
• 초당적 그래프 ^[7]

참조

외부 단면

• Berge, C. (1989), Hypergraphs, Combinatorics of Finite sets, Amsterdam: North-Holland, ISBN 0-444-87489-5