류블랴나 그래프

류블랴나 그래프
Heawood 그래프의 커버 그래프로서의 Ljubljana 그래프
정점	112
가장자리	168
반지름	7
지름	8
둘레	10
자동형성	168
색수	2
색도 지수	3
특성.	큐빅 반대칭 해밀턴어
그래프 및 모수 표

그래프 이론의 수학 분야에서, Ljubljana 그래프는 112 정점과 168개의 가장자리를 가진 간접적인 초당적 그래프다.^[1]

직경 8, 반지름 7, 색도 번호 2 및 색도 지수 3의 입방 그래프다.둘레는 10이고 길이 10의 168 사이클이 정확히 들어 있다.또한 길이 12의 168 사이클이 있다.^[2]

건설

The Ljubljana graph is Hamiltonian and can be constructed from the LCF notation : [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39]².

Ljubljana 그래프는 Ljubljana 구성을 Levi 그래프로, 56개의 선과 56개의 점을 가진 쿼드랑글 프리 구성이다.^[2]이 구성에서 각 선은 정확히 3개의 점을 포함하며, 각 선은 정확히 3개의 선에 속하며, 두 선은 최대 한 점에서 교차한다.

대수적 특성

Ljubljana 그래프의 자동형성 그룹은 순서 168의 그룹이다.그것은 그래프의 가장자리에서 전이적으로 작용하지만 그것의 꼭지점에서는 작용하지 않는다: 모든 가장자리는 다른 가장자리로 가져가지만 모든 꼭지점을 다른 가장자리로 가져가지는 않는 대칭이 있다.따라서 Ljubljana 그래프는 반대칭 그래프로서 54 정점의 그레이 그래프와 110 정점의 이오피노바-이바노프 그래프 다음으로 가능한 세 번째로 작은 입방형 반대칭 그래프다.^[3]

Ljubljana 그래프의 특성 다항식은

${\displaystyle (x-3)x^{14}(x+3)(x^{2}-x-4)^{7}(x^{2}-2)^{6}(x^{2}+x-4)^{7}(x^{4}-6x^{2}+4)^{14}.\ }$

역사

Ljubljana 그래프는 Bruwer, Dejter, Thomassen에^[4] 의해 Dejter 그래프의 자기 완성 하위 그래프로 1993년에 처음 출판되었다.^[5]

1972년에 Bouwer는 이미 112-수직 가장자리- 그럼에도 불구하고 R. M. Foster에 의해 발견된 정점 변환 입방 그래프를 말하고 있었다.^[6]콘더, 말니치, 마루시치, 피산스키, 포토치니크 등은 2002년 이 112-수직 그래프를 재발견해 슬로베니아의 수도 이름을 따서 루블자나 그래프라고 명명했다.^[2]그들은 그것이 고유한 112-수직 가장자리라는 것을 증명했지만 정점 변환 입방그래프는 아니었고 따라서 포스터가 발견한 그래프라는 것을 증명했다.

갤러리

• 

  Ljubljana 그래프는 Hamiltonian이고 초당적이다.

• 

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

• 

  Ljubljana 그래프의 대체 도면.

• 

  Ljubljana 그래프는 이 구성의 Levi 그래프다.

참조