정점-변환 그래프
Vertex-transitive graph| 자동화에 의해 정의된 그래프 패밀리 | ||||
|---|---|---|---|---|
| 거리 변환의 | → | 거리 규칙의 | ← | 매우 규칙적인. |
| ↓ | ||||
| 대칭(대칭 변환) | ← | t-변환, t ≥ 2 | 꼬불꼬불한 | |
| ↓ | ||||
| (연결된 경우) 정점 및 에지 변환 | → | 가장자리-변환적이고 규칙적인 | → | 가장자리-변환성 |
| ↓ | ↓ | ↓ | ||
| 정점 변환의 | → | 정칙의 | → | (양립할 경우) 복엽의 |
| ↑ | ||||
| 케이리 그래프 | ← | 무궤도적 | 비대칭의 | |
그래프 이론의 수학적 분야에서 정점 변환 그래프는 G의 어떤 두 정점1 v와2 v를 볼 때 어떤 자동형성이 있는 그래프 G이다.
그런
즉, 그래프의 자동형성 그룹이 정점에 대해 전이적으로 작용한다면 그래프는 정점 변환이다.[1]그래프는 그룹 동작이 동일하기 때문에 그래프 보완이 동일한 경우에만 정점 변환이다.
분리된 정점이 없는 모든 대칭 그래프는 정점 변환이고, 모든 정점 변환 그래프는 규칙적이다.그러나 모든 정점 변환 그래프가 대칭인 것은 아니며(예: 잘린 사면체의 가장자리) 모든 정규 그래프가 정점 변환인 것은 아니다(예: Frucht 그래프와 Tietze의 그래프).
유한한 예
유한 정점 변환 그래프에는 대칭 그래프(Petersen 그래프, Heawood 그래프, Platonic solid의 정점과 가장자리 등)가 포함된다.유한 Cayley 그래프(입방체 연결 사이클 등)도 Archimedeans 고형물의 정점과 가장자리처럼 정점 변환이다(이 중 두 개만 대칭이지만).Potochnik, Spiga 및 Verret은 최대 1280 정점에 연결된 모든 입방 정점-변환 그래프의 인구조사를 구성했다.[2]
모든 Cayley 그래프는 정점-변환성이지만, Cayley 그래프가 아닌 다른 정점-변환 그래프가 존재한다.가장 유명한 예는 피터슨 그래프지만,[3] 다른 그래프들은 정점이 홀수인 가장자리 전이 비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비
특성.
정점-변환 그래프의 가장자리-연결도는 도 d와 같고, 정점-연결도는 최소 2(d + 1)/3이 된다.[1]정도가 4 이하거나 그래프도 에지 변환성이거나 그래프가 최소 카이리 그래프라면 정점 연결성도 d와 같을 것이다.[4]
무한 예제
무한정 정점 변환 그래프에는 다음이 포함된다.
- 무한 경로(양방향 모두 무한)
- 무한 일반 나무, 예를 들어 자유 그룹의 Cayley 그래프
- 일반 다각형에 의한 모든 기울기를 포함하여 균일한 테셀레이션의 그래프(평면 테셀레이션의 전체 목록 참조)
- 무한 케이리 그래프
- 라도 그래프
두 개의 계수 가능한 정점 변환 그래프는 거리 함수의 비율이 아래로부터 경계와 위로부터 경계인 경우 준 등축도라고 불린다.잘 알려진 추측에 따르면 모든 무한정 정점 변환 그래프는 케이리 그래프와 준 등축이라고 한다.2001년 디에스텔과 리더가 백범례를 제안했다.[5]2005년, 에스킨, 피셔, 와우테는 백범례를 확인했다.[6]
참고 항목
참조
- ^ a b Godsil, Chris; Royle, Gordon (2013) [2001], Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer, ISBN 978-1-4613-0163-9.
- ^ Potočnik P., Spiga P. & Verret G. (2013), "Cubic vertex-transitive graphs on up to 1280 vertices", Journal of Symbolic Computation, 50: 465–477, arXiv:1201.5317, doi:10.1016/j.jsc.2012.09.002, S2CID 26705221.
- ^ 라우리와 스카펠레는 마크 왓킨스에게 이 공사를 맡겼다Lauri, Josef; Scapellato, Raffaele (2003), Topics in graph automorphisms and reconstruction, London Mathematical Society Student Texts, vol. 54, Cambridge University Press, p. 44, ISBN 0-521-82151-7, MR 1971819.
- ^ Babai, L. (1996), Technical Report TR-94-10, University of Chicago, archived from the original on 2010-06-11
- ^ Diestel, Reinhard; Leader, Imre (2001), "A conjecture concerning a limit of non-Cayley graphs" (PDF), Journal of Algebraic Combinatorics, 14 (1): 17–25, doi:10.1023/A:1011257718029, S2CID 10927964.
- ^ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "Quasi-isometries and rigidity of solvable groups". arXiv:math.GR/0511647..
외부 링크
- Weisstein, Eric W. "Vertex-transitive graph". MathWorld.
- 연결된 작은 입방정점-변환 그래프의 인구조사. 프리모o 포토치니크, 파블로 스피가, 가브리엘 베레트, 2012.
