반투명 그래프

Half-transitive graph
자동화에 의해 정의된 그래프 패밀리
거리 변환의 → 거리 규칙의 ← 매우 규칙적인.
↓
대칭(대칭 변환) ← t-변환, t ≥ 2 꼬불꼬불한
↓
(연결된 경우)
정점 및 에지 변환 		→ 가장자리-변환적이고 규칙적인 → 가장자리-변환성
↓ ↓ ↓
정점 변환의 → 정칙의 → (양립할 경우)
복엽의
↑
케이리 그래프 ← 무궤도적 비대칭의

그래프 이론의 수학적 분야에서 반투명 그래프는 정점 변환과 에지 변환 둘 다지만 대칭은 아닌 그래프다.[1]즉, 그래프의 자동모형 집단이 정점과 가장자리 모두에 대해 전이적으로 작용하지만, 연결된 정점의 순서 쌍에는 작용하지 않는 경우, 그래프는 절반의 변환성이 있다.

홀트 그래프는 가장 작은 반투명 그래프다.이 그림의 반사적 대칭성의 결여는 가장자리가 그들의 역행과 같지 않다는 사실을 강조한다.

연결된 모든 대칭 그래프는 정점-변환성 및 에지-변환성이어야 하며,[2] 반전은 홀수도의 그래프는 참이므로 홀수도의 반변환성 그래프는 존재하지 않는다.그러나 반투명 그래프는 짝수 정도로 존재한다.[3]가장 작은 반투명 그래프는 Holt 그래프인데, 도 4와 27 정점을 가지고 있다.[4][5]

참조

  1. ^ Gross, J.L.; Yellen, J. (2004). Handbook of Graph Theory. CRC Press. p. 491. ISBN 1-58488-090-2.
  2. ^ Babai, L (1996). "Automorphism groups, isomorphism, reconstruction". In Graham, R; Grötschel, M; Lovász, L (eds.). Handbook of Combinatorics. Elsevier.
  3. ^ Bouwer, Z. (1970). "Vertex and Edge Transitive, But Not 1-Transitive Graphs". Canadian Mathematical Bulletin. 13: 231–237. doi:10.4153/CMB-1970-047-8.
  4. ^ Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. ISBN 0-521-45897-8.
  5. ^ Holt, Derek F. (1981). "A graph which is edge transitive but not arc transitive". Journal of Graph Theory. 5 (2): 201–204. doi:10.1002/jgt.3190050210..