적분 그래프
Integral graph그래프 이론의 수학 분야에서 적분 그래프는 인접 행렬의 스펙트럼이 모두 정수로 구성된 그래프다.즉, 인접 행렬의 특성 다항식의 모든 루트가 정수라면 그래프는 적분 그래프다.[1]
이 개념은 1974년 프랭크 하라리와 알렌 슈웬크에 의해 도입되었다.[2]
예
- 전체 그래프 K는n 모든 n에 통합되어 있다.[2]
- 통합된 유일한 사이클 그래프는 3 4 6 등이다[2]
- 예를 들어, 완전한 그래프의 보완인 엣지 없는 그래프가 통합되어 있는 경우 그래프의 보완도 그래프의 통합이다.예를 들어, 두 개의 그래프가 통합되어 있다면, 그들의 데카르트 제품과 강력한 제품,[2] 예를 들어, 두 개의 완전한 그래프의 데카르트 제품, 즉 루크의 그래프도 통합되어 있다.[3]마찬가지로, 하이퍼큐브 그래프는 K }}개의 완전한 그래프의 데카르트 제품으로서 일체형이다[2]
- 적분 그래프의 선 그래프는 다시 적분된다.예를 들어 K 의 선 그래프로서 팔면 그래프는 일체형이고, K 의 선 그래프의 보완형으로서 피터슨 그래프는 일체형이다[2]
- 입방 대칭 그래프 중에서 효용 그래프, 피터슨 그래프, 나우루 그래프, 데스아게스 그래프는 일체형이다.
- 히그만-심스 그래프, 홀-잔코 그래프, 클렙슈 그래프, 호프만-싱글턴 그래프, 슈리칸데 그래프, 호프만 그래프는 일체형이다.
- 정규 그래프는 적분 그래프인 경우에만 주기적이다.
- 완벽한 상태전환을 인정하는 보행정기 그래프는 일체형 그래프다.
- 스도쿠 그래프는 정점이 스도쿠 보드의 세포를 나타내고 가장자리가 같으면 안 되는 세포를 나타내는 그래프로서 필수적이다.[4]
참조
- ^ Weisstein, Eric W., "Integral Graph", MathWorld
- ^ a b c d e f Harary, Frank; Schwenk, Allen J. (1974), "Which graphs have integral spectra?", in Bari, Ruth A.; Harary, Frank (eds.), Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, Washington, D.C., June 18–22, 1973, Lecture Notes in Mathematics, vol. 406, Springer, pp. 45–51, doi:10.1007/BFb0066434, MR 0387124
- ^ Doob, Michael (1970), "On characterizing certain graphs with four eigenvalues by their spectra", Linear Algebra and its Applications, 3: 461–482, doi:10.1016/0024-3795(70)90037-6, MR 0285432
- ^ Sander, Torsten (2009), "Sudoku graphs are integral", Electronic Journal of Combinatorics, 16 (1): Note 25, 7, MR 2529816
