바그너 그래프

바그너 그래프
바그너 그래프
이름을 따서 명명됨	클라우스 바그너
정점	8
가장자리	12
반지름	2
지름	2
둘레	4
자동형성	16(D8)
색수	3
색도 지수	3
속	1
특성.	큐빅 해밀턴어 트라이앵글 정점 변환 토로이드 에이펙스
표기법	M8
그래프 및 모수 표

그래프 이론의 수학 분야에서 바그너 그래프는 정점이 8개, 가장자리가 12개인 3정형 그래프다.^[1]그것은 8-Vertex Möbius 사다리 그래프 입니다.

특성.

뫼비우스 사다리로서 바그너 그래프는 평면은 아니지만 넘버원(crossing number)을 가지고 있어 꼭지점 그래프가 된다.토러스나 투영면에 교차 없이 삽입할 수 있으므로, 토로이드 그래프이기도 하다.둘레 4, 지름 2, 반지름 2, 색채 번호 3, 색채 지수 3을 가지며, 3-버텍스 연결과 3-엣지 연결이다.

바그너 그래프는 392개의 스패닝 트리를 가지고 있다; 그것과 완전한 그래프 K는_3,3 정점의 수가 같은 모든 입방 그래프 중에서 가장 스패닝 트리를 가지고 있다.^[2]

바그너 그래프는 정점 변환 그래프지만 에지 변환 그래프는 아니다.그것의 완전 자동형 집단은 회전과 반사를 모두 포함한 팔각형의 대칭 집단인 순서 16의 이음계 그룹 D와₈ 이형성이다.

바그너 그래프의 특성 ${\displaystyle \mathrm{다항식}}$은${\displaystyle }$( ${\displaystyle x}$- ${\displaystyle 3}$)${\displaystyle }$( ${\displaystyle x}$- ${\displaystyle 1{}^{}}$) 2${\displaystyle }$( x +${\displaystyle 1}$) ( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$+ ${\displaystyle 2}$ ${\displaystyle x}$- ${\displaystyle 1{}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$ ${\$)이다$.$$^{2$ 이 특성 다항식을 가진 유일한 그래프로, 스펙트럼에 의해 결정되는 그래프가 된다.

바그너 그래프는 삼각형이 없고 3번 독립성을 가지고 있어 램지 번호 R(3,4)의 1/2(n-vertex 그래프가 삼각형 또는 4-vertex 독립 집합을 포함하는 최소 숫자 n)이 9라는 증거를 제공한다.^[3]

그래프 마이너

뫼비우스 사다리들은 그래프 미성년자 이론에서 중요한 역할을 한다.이러한 유형의 가장 초기 결과는 1937년 클라우스 바그너(와그너의 정리라고 알려진 결과 군집의 일부)의 정리인데₅, K 단위가 없는 그래프는 클릭섬 연산을 사용하여 평면 그래프와 뫼비우스 사다리 M을₈ 결합함으로써 형성될 수 있다.^[4]이러한 이유로 M은₈ 바그너 그래프라고 불린다.

그 바그너 그래프는 또한 4개의 최소한의 금지된 미성년자 treewidth이 크게 세가지의( 다른 3은 완전 그래프 K5는 정팔면체의 그래프, 오각형의 프리즘의 그래프)에서 그래프를 위한 하나, 그리고 4최소한의 금지된 미성년자 branchwidth의 그래프에서 크게 세가지의( 다른 3K5는 그래프의.t8면체 및 입방체 그래프).^[5][6]

건설

바그너 그래프는 입방형 해밀턴 그래프로서 LCF 표기법[4]⁸으로 정의할 수 있다.그것은 안드라스파이 그래프의 한 예로서, 정점을 사이클로 배열할 수 있고 각 정점을 1(모드 3)의 숫자로 다른 정점에 연결하는 순환 그래프의 일종이다.그것은 또한 원형 클라이크 K와_8/3 이형적이다.

위상학 뫼비우스 띠에 4rungs를 반복하여 만든 사다리 그래프로 그릴 수 있다.

갤러리

• 

  바그너 그래프의 색수는 3이다.

• 

  바그너 그래프의 색지수는 3이다.

• 

  뫼비우스 띠에 그려진 바그너 그래프.

참조

위키미디어 커먼즈에는 바그너 그래프와 관련된 미디어가 있다.