에지 변환 그래프

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

그래프 이론의 수학적 분야에서, 가장자리-변환성 그래프는 G의 어떤₁ 두 가장자리₂ e와 e를 볼 때, e를₁ e에 매핑하는₂ G의 자동형이 존재하는 그래프 G이다.^[1]

즉, 그래프의 자동모형 집단이 가장자리에서 전이적으로 작용하면 가장자리-변환성이 된다.

예제 및 속성

n 꼭지점에 연결된 간단한 에지 변환 그래프의 수는 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28 … (OEIS의 경우 시퀀스 A095424)이다.

에지 변환 그래프에는 큐브의 꼭지점 및 에지와 같은 모든 대칭 그래프가 포함된다.^[1]대칭 그래프도 정점 변환(연결된 경우)이지만, 일반적으로 에지 변환 그래프는 정점 변환일 필요가 없다.정점 변환이 아닌 모든 에지 변환 그래프는 초당적이어야 ^[1]하며(따라서 두 가지 색상만 사용할 수 있음), 반대칭 또는 이선형이어야 한다.^[2]

에지는 아니지만 정점은 아닌 전체 양분 그래프 ${\displaystyle {Km,}_{}}$ n ${\$을(를) 포함하며, 여기서$$ m ≠n은 별 그래프 ${\displaystyle {K\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$,${\displaystyle n_{}}$ ${\$ 정점에 있는 그래프의 경우 홀수 n과 (n-2)에 대한 그래프가 있다.대칭이 아닌 추가 에지 전이성 그래프는 특정 경우 이러한 완전한 바이파이트 그래프의 하위 그래프로 형성될 수 있다.완전한_m,n 초당적 그래프 K의 하위 그래프는 m과 n이 2보다 큰 요인을 공유할 때 존재한다.최대 공통인자가 2일 경우 2n/m이 짝수이거나 m=4와 n이 6의 홀수배수인 경우 하위그래프가 존재한다.^[3]따라서 에지 전이적 서브그래프는 K_3,6, K_4,6, K에_5,10 대해 존재하지만 K에는_4,10 존재하지 않는다.일부 에지 전이성 그래프의 대체 구조는 v 정점과 e 가장자리가 있는 대칭 그래프의 가장자리 중간점에 정점을 추가하여 순서 2의 e 정점과 순서 2e/v의 v 정점을 갖는 초당적 그래프를 만드는 것이다.

정규적이지만 여전히 정점은 아닌 에지 변환 그래프를 반대칭이라고 한다.54 정점에 있는 입방형 그래프인 회색 그래프는 에지 변환이지만 정점이 아닌 일반 그래프의 예다.포크맨 그래프, 정점 20에 4분위수 그래프가 가장 작은 그래프다.

에지 변환 그래프의 정점 연결은 항상 최소도와 동일하다.^[4]

참고 항목

• 모서리 변환(지오메트리)

참조

외부 링크

• Weisstein, Eric W. "Edge-transitive graph". MathWorld.