프리즘 그래프

Prism graph

그래프 이론의 수학 분야에서 프리즘 그래프는 프리즘 중 하나를 골격으로 하는 그래프다.

예

개별 그래프는 연관된 솔리드의 이름을 따서 명명할 수 있다.

Triangular prismatic graph.png
Y3 = GP(3,1)		 Cubical graph.png
Y4 = Q3 = GP(4,1)		 Pentagonal prismatic graph.png
Y5 = GP(5,1)		 Hexagonal prismatic graph.png
Y6 = GP(6,1)		 Heptagonal prismatic graph.png
Y7 = GP(7,1)		 Octagonal prismatic graph.png
Y8 = GP(8,1)

기하학적으로 항성 폴리곤도 프리즘(자체 교차 및 비-콘벡스) 프리즘 폴리에드라의 다른 시퀀스의 얼굴을 형성하지만, 이러한 항성 프리즘의 그래프는 프리즘 그래프에 이형성이 있으며, 별도의 그래프 시퀀스를 형성하지 않는다.

건설

프리즘 그래프는 파라미터 GP(n,1)가 있는 일반화된 피터슨 그래프의 예다.그것들은 또한 단일 에지를 가진 사이클 그래프의 데카르트 산물로 구성될 수 있다.[1]

많은 정점 변환 그래프와 마찬가지로 프리즘 그래프는 Cayley 그래프로도 구성될 수 있다.순서-n-dihedral 그룹은 평면에 있는 일반 n-곤의 대칭 그룹이며, 회전과 반사에 의해 n-곤에 작용한다.2㎛/n 각도와 단일반사라는 두 개의 원소에 의해 생성될 수 있으며, 이 생성 세트가 있는 Cayley 그래프가 프리즘 그래프다.Abstractly, the group has the presentation (where r is a rotation and f is a reflection or flip) and the Cayley graph has r and f (or r, r−1, and f) as its generators.[1]

홀수 값이 n인 n-곤알 프리즘 그래프는 순환 그래프 , 그러나 이 구성은 n의 짝수 값에 대해서는 작동하지 않는다.[1]

특성.

n-곤 프리즘의 그래프는 정점이 2n이고 가장자리가 3n이다.그것들은 정규의 세제곱 그래프 입니다.프리즘은 각 정점을 서로 정점으로 가져가는 대칭이 있기 때문에 프리즘 그래프는 정점 변환 그래프다.다면 그래프로서, 그것들은 또한 3-Vertex로 연결된 평면 그래프이기도 하다.모든 프리즘 그래프에는 해밀턴 사이클이 있다.[2]

모든 쌍체 입방 그래프 중에서 프리즘 그래프는 가능한 가장 많은 수의 1-요인 상수 인자 내에 있다.1-요인화는 그래프의 가장자리 집합을 세 가지 완벽한 일치 항목으로 분할하거나, 마찬가지로 세 가지 색상으로 그래프를 가장자리 색상으로 채색하는 것이다.모든 biconected n-vertex 세제곱 그래프에는 O(2n/2) 1-요소가 있고, 프리즘 그래프에는 Ω(2) 1-요소가n/2 있다.[3]

n-곤 프리즘 그래프의 스패닝 트리 수는 공식에[4] 의해 주어진다.

n = 3, 4, 5, ...의 경우 이 숫자는

75, 384, 1805, 8100, 35287, 150528, ...(OEIS의 경우 시퀀스 A006235).

n의 짝수 값에 대한 n-곤 프리즘 그래프는 부분 입방체다.그들은 알려진 몇 안 되는 무한대의 큐빅 부분 큐빅 제품군 중 하나를 형성하며, (산발적인 네 가지 예는 제외) 정점 변환 큐빅 부분 큐빅 큐빅 제품군 중 유일한 것을 형성한다.[5]

오각형 프리즘은 나무 너비 3의 그래프에서 금지된 미성년자 중 하나이다.[6]삼각형 프리즘과 큐브 그래프는 나무 너비가 정확히 3개지만, 모든 큰 프리즘 그래프는 나무 너비 4개를 가지고 있다.

관련 그래프

다면체 그래프의 다른 무한 시퀀스에는 다면체 그래프의 일반 폴리곤 베이스와 유사한 방식으로 형성되며, 항정신병 그래프(반격의 그래프)와 휠 그래프(피라미드의 그래프)가 포함된다.다른 정점 변환 다면 그래프에는 아르키메데스 그래프가 포함된다.

프리즘 그래프의 두 사이클이 양쪽 사이클에서 동일한 위치에서 단일 에지를 제거하여 깨지면 그 결과는 래더 그래프가 된다.이 두 개의 제거된 가장자리가 두 개의 교차된 가장자리로 대체되면 그 결과는 뫼비우스 사다리라고 불리는 비 평면 그래프가 된다.[7]

참조

  1. ^ a b c Weisstein, Eric W. "Prism graph". MathWorld.
  2. ^ 영국 옥스포드주, R. C.와 윌슨, R. J. Atlas of Graphs, Oxford:옥스퍼드 대학 출판부, 2004년 재인쇄, 6장 특별 그래프 페이지 261, 270.
  3. ^ Eppstein, 데이비드(2013년),"bendless 3차원 직교 그래프 그리기의 복잡성", 저널 도표로 알고리즘 및 애플리케이션, 17(1):35–55의 arXiv:0709.4087, doi:10.7155/jgaa.00283, MR3019198.Eppstein 프리즘 그래프 가까이 그레그 Kuperberg여 개인 의사 소통에 1-factorizations의 최대 개수할 수 있다는 관측 때문이라고 한다.
  4. ^ Jagers, A. A. (1988), "A note on the number of spanning trees in a prism graph", International Journal of Computer Mathematics, 24 (2): 151–154, doi:10.1080/00207168808803639.
  5. ^ Marc, Tilen (2015), Classification of vertex-transitive cubic partial cubes, arXiv:1509.04565, Bibcode:2015arXiv150904565M.
  6. ^ Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), "Forbidden minors characterization of partial 3-trees", Discrete Mathematics, 80 (1): 1–19, doi:10.1016/0012-365X(90)90292-P, MR 1045920.
  7. ^ Guy, Richard K.; Harary, Frank (1967), "On the Möbius ladders", Canadian Mathematical Bulletin, 10: 493–496, doi:10.4153/CMB-1967-046-4, MR 0224499.