나비 그래프

나비 그래프
정점	5
가장자리	6
반지름	1
지름	2
둘레	3
자동형성	8 (D4)
색수	3
색도 지수	4
특성.	플라나르 단위 거리 오일러어 우아하지 않다
그래프 및 모수 표

그래프 이론의 수학 분야에서 나비 그래프(Bowtie Graph, 모래시계 그래프라고도 함)는 5개의 정점과 6개의 가장자리를 가진 평면형 비방향 그래프다.^[1][2]사이클 그래프 C의₃ 2부를 공통 꼭지점과 결합하여 구성할 수 있으며, 따라서 우정 그래프₂ F와 이형성이 있다.

나비 그래프는 지름 2, 둘레 3, 반지름 1, 색도 번호 3, 색도 지수 4를 가지며 오일러 그래프와 페니 그래프 둘 다(단위 거리 및 평면임을 의미한다)이다.또한 1Vertex 연결 그래프와 2Edge 연결 그래프이기도 하다.

5개의 꼭지점이 있는 3개의 비회상적인 단순 그래프가 있을 뿐이다.그 중 하나가 나비 그래프다.다른 두 가지는 사이클 그래프 C와₅ 전체 그래프 K이다₅.^[3]

Bowtie-free 그래프

그래프는 유도 서브그래프로서 나비가 없다면 보타이 없는 것이다.tie)가 없다.삼각형이 없는 그래프는 나비마다 삼각형이 있기 때문에 나비들이 없는 그래프다.

k-Vertex 연결 그래프에서 엣지(edge)의 수축이 k-연결 그래프로 귀결되면 엣지(edge)는 k-계약이 가능하다고 한다.안도, 가네코, 카와라바야시, 요시모토는 모든 k-베르텍스 연결 보타이 프리 그래프에 k-계약 가능한 엣지가 있음을 증명했다.^[4]

대수적 특성

나비 그래프의 완전 자동형 집단은 회전과 반사를 모두 포함한 사각형의 대칭 집단인 디헤드랄 그룹 D에₄ 대한 순서 8 이형성 집단이다.

나비 그래프의 특성 다항식은 -${\displaystyle }$( ${\displaystyle x}$- 1${\displaystyle }$)${\displaystyle }$( ${\displaystyle {x\mathrm{}}^{}}$+ 1${\displaystyle {}^{}}$) 2${\displaystyle {}^{}}$( x ${\displaystyle 2{}^{}}$- x${\displaystyle }$- ${\displaystyle 4}$) ${\displaystyle -$ $(x-1)(x+1)^{2}(x^{2}-x-4)}$ 입니다$.$

참조