반대칭 그래프
Semi-symmetric graph
| 자동화에 의해 정의된 그래프 패밀리 | ||||
|---|---|---|---|---|
| 거리 변환의 | → | 거리 규칙의 | ← | 매우 규칙적인. |
| ↓ | ||||
| 대칭(대칭 변환) | ← | t-변환, t ≥ 2 | 꼬불꼬불한 | |
| ↓ | ||||
| (연결된 경우) 정점 및 에지 변환 | → | 가장자리-변환적이고 규칙적인 | → | 가장자리-변환성 |
| ↓ | ↓ | ↓ | ||
| 정점 변환의 | → | 정칙의 | → | (양립할 경우) 복엽의 |
| ↑ | ||||
| 케이리 그래프 | ← | 무궤도적 | 비대칭의 | |
그래프 이론의 수학적 분야에서, 반대칭 그래프는 가장자리-변환적이고 규칙적이지만 정점-변환성이 아닌 비방향 그래프다.즉, 각 정점마다 입사 가장자리 수가 같을 경우 그래프는 반대칭이고, 그래프의 가장자리 중 하나를 다른 가장자리로 가져가는 대칭성이 있지만, 첫 번째 정점에는 대칭성이 없는 정점 쌍이 있다.
특성.
반대칭 그래프는 초당적이어야 하며, 그 자동형 그래프의 자동형 집단은 양분적 두 꼭지점 집합 각각에 대해 전이적으로 작용해야 한다(사실 이 속성을 보유하는 데는 규칙성이 필요하지 않다).예를 들어, 여기에 나타난 포크맨 그래프의 도표에서 녹색 정점들은 어떤 자동형성에 의해서도 빨간 정점에 매핑될 수 없지만, 같은 색의 정점 두 개마다 서로 대칭이다.
역사
반대칭 그래프는 처음에 E를 연구했다.F학번인 도버.Harary, 논문에서 더 이상 사용할 수 없는 "On line-but not point-symmetric graphs".이것은 1967년에 출판된 Jon Folkman에 의해 보여졌다. 그의 논문은 현재 Folkman 그래프라고 알려진 가장 작은 반대칭 그래프를 20개의 정점에 포함하고 있다.[1]"반대칭"이라는 용어는 클린 등이 1978년에 발표한 논문에서 처음 사용되었다.[2]
입방 그래프
가장 작은 입방체 반대칭 그래프(즉, 각 정점이 정확히 세 개의 가장자리에 입사하는 그래프)는 54개의 정점에 있는 회색 그래프다.처음에 부워(1968년)에 의해 반대칭으로 관측되었다.드라간 마루시치와 알렉산더 말니치가 쓴 가장 작은 입방체 반대칭 그래프로 입증됐다.[3]
정점 최대 768개의 정점에 있는 모든 입방체 반대칭 그래프가 알려져 있다.콘더, 말니치, 마루시치, 포토치니크에 따르면 그레이 그래프 다음으로 가장 작은 입방형 반대칭 그래프는 110 정점의 이오피노바-이바노프 그래프, 112 정점의 류블랴나 그래프,[4] 둘레 8의 정점 120 정점 그래프, 투테 12-캐이지의 정점 그래프다.[5]
참조
- ^ Folkman, J. (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory, 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3.
- ^ Klin, Lauri & Ziv-Av (2011). "Links between two semisymmetric graphs on 112 vertices through the lens of association schemes" (PDF). Retrieved 17 August 2015.
{{cite journal}}:Cite 저널은 필요로 한다.journal=(도움말) - ^ Bouwer, I. Z. (1968), "An edge but not vertex transitive cubic graph", Canadian Mathematical Bulletin, 11 (4): 533–535, doi:10.4153/CMB-1968-063-0.
- ^ Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002), "The Ljubljana Graph" (PDF), IMFM Preprints, Ljubljana: Institute of Mathematics, Physics and Mechanics, vol. 40, no. 845.
- ^ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics, 23 (3): 255–294, doi:10.1007/s10801-006-7397-3.