거리 변환 그래프
Distance-transitive graph |
가장 큰 3-정규 거리 변환 그래프인 Biggs-Smith 그래프.
| 자동화에 의해 정의된 그래프 패밀리 | ||||
|---|---|---|---|---|
| 거리 변환의 | → | 거리 규칙의 | ← | 매우 규칙적인. |
| ↓ | ||||
| 대칭(대칭 변환) | ← | t-변환, t ≥ 2 | 꼬불꼬불한 | |
| ↓ | ||||
| (연결된 경우) 정점 및 에지 변환 | → | 가장자리-변환적이고 규칙적인 | → | 가장자리-변환성 |
| ↓ | ↓ | ↓ | ||
| 정점 변환의 | → | 정칙의 | → | (양립할 경우) 복엽의 |
| ↑ | ||||
| 케이리 그래프 | ← | 무궤도적 | 비대칭의 | |
그래프 이론의 수학적 분야에서 거리 변환 그래프는 어떤 거리 i에서든 어떤 두 개의 꼭지점 v와 w, 그리고 같은 거리에서 어떤 다른 두 꼭지점 x와 y를 볼 때, v에서 x까지 그리고 w에서 y까지를 전달하는 그래프의 자동형이 존재하는 그래프다.거리 변환 그래프는 1971년 노르만 L. Biggs와 D에 의해 처음 정의되었다.H. 스미스.
거리 변환 그래프는 부분적으로 큰 자동형 그룹을 가지고 있기 때문에 흥미롭다.몇몇 흥미로운 유한집단은 특히 지름이 2인 그래프의 거리 전이 그래프의 자동모형 그룹이다.
예
거리 변환 그래프 패밀리의 일부 첫 번째 예는 다음과 같다.
세제곱 거리-변환 그래프 분류
1971년 그것들을 소개한 후, Biggs와 Smith는 유한 3밸런스 거리-변환 그래프가 12개밖에 없다는 것을 보여주었다.다음은 다음과 같다.
| 그래프 이름 | 정점수 | 지름 | 둘레 | 교차로 배열 |
|---|---|---|---|---|
| 사면 그래프 또는4 전체 그래프 K | 4 | 1 | 3 | {3;1} |
| 완전3,3 양분 그래프 K | 6 | 2 | 4 | {3,2;1,3} |
| 피터슨 그래프 | 10 | 2 | 5 | {3,2;1,1} |
| 입체 그래프 | 8 | 3 | 4 | {3,2,1;1,2,3} |
| 히우드 그래프 | 14 | 3 | 6 | {3,2,2;1,1,3} |
| 파푸스 그래프 | 18 | 4 | 6 | {3,2,2,1;1,1,2,3} |
| 콕시터 그래프 | 28 | 4 | 7 | {3,2,2,1;1,1,1,2} |
| 투테-콕시터 그래프 | 30 | 4 | 8 | {3,2,2,2;1,1,1,3} |
| 도데카헤드 그래프 | 20 | 5 | 5 | {3,2,1,1,1;1,1,1,2,3} |
| 데스아게네스 그래프 | 20 | 5 | 6 | {3,2,2,1,1;1,1,2,2,3} |
| Biggs-Smith 그래프 | 102 | 7 | 9 | {3,2,2,2,1,1,1;1,1,1,1,1,1,3} |
| 포스터 그래프 | 90 | 8 | 10 | {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3} |
거리 정규 그래프와의 관계
모든 거리-변환 그래프는 거리-정규형이지만, 그 역이 반드시 사실인 것은 아니다.
Biggs-Smith 정의가 발표되기 전인 1969년 Georgy Adelson-Velsky가 이끄는 러시아 그룹은 거리-정규적이지만 거리-변환성이 아닌 그래프가 존재한다는 것을 보여주었다.거리 변환이 아닌 가장 작은 거리 정규 그래프는 16 정점과 6도를 갖는 슈리칸데 그래프다.이 유형의 그래프 중 3도는 126-Vertex Tute 12-cage이다.거리 변환 그래프의 전체 목록은 3보다 큰 일부 도에 대해 알려져 있지만, 임의로 큰 정점도를 갖는 거리 변환 그래프의 분류는 열린 상태로 남아 있다.
참조
- 초기 작업
- Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; Faradžev, I. A. (1969), "An example of a graph which has no transitive group of automorphisms", Doklady Akademii Nauk SSSR, 185: 975–976, MR 0244107.
- Biggs, Norman (1971), "Intersection matrices for linear graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23, MR 0285421.
- Biggs, Norman (1971), Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series, vol. 6, London & New York: Cambridge University Press, MR 0327563.
- Biggs, N. L.; Smith, D. H. (1971), "On trivalent graphs", Bulletin of the London Mathematical Society, 3 (2): 155–158, doi:10.1112/blms/3.2.155, MR 0286693.
- Smith, D. H. (1971), "Primitive and imprimitive graphs", The Quarterly Journal of Mathematics, Second Series, 22 (4): 551–557, doi:10.1093/qmath/22.4.551, MR 0327584.
- 설문 조사
- Biggs, N. L. (1993), "Distance-Transitive Graphs", Algebraic Graph Theory (2nd ed.), Cambridge University Press, pp. 155–163, 20장.
- Van Bon, John (2007), "Finite primitive distance-transitive graphs", European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014, MR 2287450.
- Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), "Distance-Transitive Graphs", Distance-Regular Graphs, New York: Springer-Verlag, pp. 214–234, 7장.
- Cohen, A. M. Cohen (2004), "Distance-transitive graphs", in Beineke, L. W.; Wilson, R. J. (eds.), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, pp. 222–249.
- Godsil, C.; Royle, G. (2001), "Distance-Transitive Graphs", Algebraic Graph Theory, New York: Springer-Verlag, pp. 66–69, 섹션 4.5.
- Ivanov, A. A. (1992), "Distance-transitive graphs and their classification", in Faradžev, I. A.; Ivanov, A. A.; Klin, M.; et al. (eds.), The Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Series), vol. 84, Dordrecht: Kluwer, pp. 283–378, MR 1321634.
