서브 해밀턴 그래프

Subhamiltonian graph

그래프 이론과 그래프 도면에서 해밀턴식 하위 그래프는 평면형 해밀턴식 그래프의 하위 그래프다.[1][2]

정의

그래프 G는 동일한 정점에 있는 다른 그래프 aug(G)의 하위 그래프인 경우 해밀턴계 하위 그래프로서, ag(G)는 평면형이고 해밀턴계 주기를 포함한다.이것이 사실이기 위해서는 G 자체가 평면이어야 하며, 또한 각 정점을 정확히 한 번 통과하는 증강 그래프에서 주기를 생성하기 위해 평면성을 보존하면서 G에 가장자리를 추가하는 것이 가능해야 한다.그래프는 G의 해밀턴 증강이라고 불린다.[2]

이 큰 그래프가 동일한 꼭지점 세트를 가질 필요 없이 G가 해밀턴 평면 그래프의 하위 그래프인 경우 G를 서브 해밀턴어로 정의하는 것과 동등할 것이다.즉, 이 대체 정의를 위해서는 정점과 가장자리를 모두 G에 추가하여 해밀턴 사이클을 생성할 수 있어야 한다.그러나 정점과 가장자리를 추가하여 그래프를 해밀턴식으로 만들 수 있다면 가장자리만 추가해도 해밀턴식으로 만들 수 있기 때문에 이 여분의 자유는 정의를 바꾸지 않는다.[3]

서브 해밀턴 그래프에서 서브 해밀턴 사이클은 정점의 순환 시퀀스로서, 시퀀스에서 각 연속 쌍의 정점 사이에 에지를 추가하면 그래프의 평면성이 보존된다.그래프는 서브해밀턴 사이클이 있는 경우에만 서브해밀턴이다.[4]

기록 및 응용 프로그램

서브 해밀턴 그래프 등급(그러나 이 이름은 아니다)은 베른하트&카인(1979)에 의해 소개되었는데, 이들은 이 그래프들이 정확히 두 페이지 분량의 책이 임베딩된 그래프라는 것을 증명했다.[5]범용 포인트 세트에 그래프를 내장하는 문제, 다중 그래프를 동시에 내장하는 문제, 레이어드 그래프 도면에 서브 해밀턴 그래프와 해밀턴 증강도 그래프 도면에 적용됐다.[2]

관련 그래프 클래스

일부 평면 그래프의 클래스는 반드시 해밀턴식이고, 따라서 하위 해밀턴식이며, 여기에는 4개의 연결 평면 그래프와[6] 할린 그래프가 포함된다.[7]

최대 4도의 평면 그래프는 분리 삼각형이 없는 평면 그래프와 마찬가지로 [4]해밀턴 하위 그래프다.[8]임의 평면 그래프의 가장자리를 길이 2의 경로로 세분화하면, 결과적으로 세분화된 그래프는 항상 해밀턴 이하의 것이다.[2]

참조

  1. ^ Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 198–218, doi:10.1137/0608018, MR 0881181.
  2. ^ a b c d 디 자코모, 에밀리오, 리오타, 주세페(2010년),"그 해밀턴 증원 문제와 그 응용 프로그램 그림 그리기 그래프로", WALCOM:알고리즘과 계산, 4국제 워크숍 WALCOM 2010년, 다카, 방글라데시, 2월 10-12,2010년에는집, 강의 노트 컴퓨터 과학으로, 5942, 베를린:스프링거,를 대신하여 서명함. 35–46, vol.. doi:10.1007/978-3-642-11440-3_4, MR2749626.
  3. ^ 예를 들어 2003년 기술 보고서 "그래프의 책 임베딩과 휘트니의 정리"에서 폴 케인은 하위 해밀턴 그래프를 증가의 꼭지점 집합에 제한 없이 평면 해밀턴 그래프의 하위 그래프로 정의하지만, "하위 해밀턴 그래프의 정의에서 확장에는 t만 포함되도록 요구할 수 있다.그는 새로운 가장자리를 포함시켰다.
  4. ^ a b Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), "Two-page book embeddings of 4-planar graphs", STACS, arXiv:1401.0684, Bibcode:2014arXiv1401.0684B.
  5. ^ Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2.
  6. ^ Nishizeki, Takao; Chiba, Norishige (2008), "Chapter 10. Hamiltonian Cycles", Planar Graphs: Theory and Algorithms, Dover Books on Mathematics, Courier Dover Publications, pp. 171–184, ISBN 9780486466712.
  7. ^ Cornuéjols, G.; Naddef, D.; Pulleyblank, W. R. (1983), "Halin graphs and the travelling salesman problem", Mathematical Programming, 26 (3): 287–294, doi:10.1007/BF02591867.
  8. ^ Kainen, Paul C.; Overbay, Shannon (2007), "Extension of a theorem of Whitney", Applied Mathematics Letters, 20 (7): 835–837, doi:10.1016/j.aml.2006.08.019, MR 2314718.