사소한 완벽 그래프

Trivially perfect graph
중첩된 간격 및 나무의 도달 가능성 관계에서 사소한 완벽 그래프의 구성

그래프 이론에서, 사소한 것으로 완벽한 그래프는 각각의 유도 하위 그래프에서 최대 독립된 세트의 크기가 최대 패거리의 수와 같다는 속성을 가진 그래프다.[1]소소하게 완벽한 그래프는 처음에 (월크 1962년, 1965년)에 의해 연구되었지만 골룸빅(1978년)에 의해 명명되었다; 골룸빅은 "그런 그래프가 완벽하다는 것을 보여주는 것은 사소한 것이기 때문에 선택된 이름"이라고 쓰고 있다.소소하게 완벽한 그래프는 나무의 비교가능성 그래프,[2] 형광 비교가능성 그래프,[3] 준임계 그래프로도 알려져 있다.[4]

등가 특성화

소소하게 완벽한 그래프에는 몇 가지 다른 동등한 특성이 있다.

  • 그것들은 질서-이론적 나무의 비교가능성 그래프들이다.즉, 각 t t T에 대해 집합 {s t T : s < t}이(가) 관계 <에 의해 잘 정렬되어 있고, 또한 T는 최소 요소 r을 소유하는 부분 순서가 되도록 한다.그러면 T의 비교가능성 그래프는 사소한 것 없이 완벽하며, 모든 사소한 것에도 완벽한 그래프는 이런 방식으로 형성될 수 있다.[5]
  • 유도 하위 그래프로서 P4 경로 그래프나 C4 사이클 그래프가 없는 그래프들이다.[6]
  • 그것들은 연결된 모든 유도 하위 그래프들이 보편적인 꼭지점을 포함하는 그래프들이다.[7]
  • 내포된 구간 집합에 대한 구간 그래프로 나타낼 수 있는 그래프들이다.세트의 두 구간마다 두 구간이 분리되거나 한 구간이 다른 구간을 포함하는 경우 일련의 구간이 중첩된다.[8]
  • 그것들은 화음과 cograph 둘 다인 그래프들이다.[9]이는 3개 이상의 길이의 유도 주기가 없는 그래프로 화음 그래프를 특성화하고 4개의 꼭지점(P4)에 유도 경로가 없는 그래프로 cograph를 특성화한 데서 비롯된다.
  • 그것들은 cograph와 interval graph 둘 다인 그래프들이다.[9]
  • 그것들은 하나의 vertex 그래프에서 시작하여 두 개의 연산을 통해 형성될 수 있는 그래프들이다. 두 개의 작은 완벽 그래프와 작은 완벽 그래프의 모든 정점에 인접한 새로운 정점 추가.[10]이러한 작전은, 밑의 숲에서, 두 개의 작은 숲이 분리된 결합에 의해 새로운 숲을 형성하고, 새로운 뿌리 노드를 숲의 모든 나무의 뿌리에 연결함으로써 나무를 형성하는 것에 대응한다.
  • 이 그래프는 모든 에지 UV에 대해 u와 v(u와 v 자체를 포함)의 주변이 중첩되는 그래프로서, 한 동네는 다른 동네의 하위 집합이어야 한다.[11]
  • 스택 정렬 가능한 순열에서 정의된 순열 그래프 입니다.[12]
  • 이러한 그래프들은 각각의 유도 하위 그래프에서 clique cover 번호가 최대 clique의 수와 같다는 속성을 가진 그래프들이다.[13]
  • 그것들은 각각의 유도 하위 그래프에서 clique 숫자가 사이비-그룬디 숫자와 같다는 속성을 가진 그래프들이다.[13]
  • 그것들은 각각의 유도 하위 그래프에서 색소수가 사이비-그룬디 숫자와 같다는 속성이 있는 그래프들이다.[13]

그래프의 관련 클래스

그것은 모든 사소한 완벽한 그래프가 또한 cograph, coordal graph, ptolemaic graph, interval graph, perfect graph라는 사소한 완벽함 그래프의 등가 특성화로부터 따온 것이다.

임계값 그래프는 그 자체로 사소한 완벽함과 사소한 완벽한 그래프(동반적으로 완벽한 그래프)의 보완점이다.[14]

풍차 그래프는 아주 완벽하다.

인식

Chu(2008)는 사전 편찬 폭 우선 검색을 기반으로, 사소한 것으로 완벽한 그래프를 인식하기 위한 간단한 선형 시간 알고리즘을 설명한다.LexBFS 알고리즘이 큐의 첫 번째 집합에서 정점 v를 제거할 때마다 알고리즘은 v의 나머지 모든 인접 항목이 동일한 집합에 속하는지 검사한다. 그렇지 않으면 v에서 금지된 유도 하위 그래프 중 하나를 구성할 수 있다. 만약 이 검사가 모든 v에 대해 성공한다면 그래프는 사소한 것 없이 완벽하다.알고리즘은 또한 그래프가 사소한 것으로 완벽한 그래프의 보완 그래프인지 여부를 선형 시간으로 테스트하기 위해 수정할 수 있다.

일반 그래프가 사소한 완벽 그래프에서 k 에지 삭제인지 판단하면 NP-완전하고 [15]고정 매개변수가 추적 가능하며[16] O(2.45k(m + n) 시간 내에 해결할 수 있다.[17]

메모들

  1. ^ Brandstédt, Le & Spinrad(1999), 정의 2.6.2, 페이지 34, 골룸빅(1978).
  2. ^ 월크(1962);월크(1965년).
  3. ^ 도넬리&이사악(1999년).
  4. ^ 옌, 첸&장(1996년).
  5. ^ Brandstét, Le & Spinrad(1999), 정리 6.6.1, 페이지 99, 골룸빅(1978), 각막 4.
  6. ^ Brandstédt, Le & Spinrad(1999), 정리 6.6.1, 페이지 99, 골룸빅(1978), 정리 2.월크(1962)와 월크(1965)는 이를 뿌리 숲의 비교가능성 그래프로 증명했다.
  7. ^ 월크(1962년).
  8. ^ Brandstédt, Le & Spinrad(1999), 페이지 51.
  9. ^ a b Brandstét, Le & Spinrad(1999), 페이지 248; Yan, Chen & Chang(1996), 정리 3.
  10. ^ Yan, Chen & Chang(1996년), Gurski(2006년).
  11. ^ Yan, Chen & Chang (1996년), 정리 3.
  12. ^ 로템(1981년).
  13. ^ a b c 루비오몬티엘(2015년).
  14. ^ Brandstét, Le & Spinrad(1999), 정리 6.6.3, 페이지 100; 골룸빅(1978), 각색 5.
  15. ^ 샤란(2002년).
  16. ^ 카이(1996년).
  17. ^ 나스토스 & 가오(2010년).

참조

  • Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Cai, L. (1996), "Fixed-parameter tractability of graph modification problems for hereditary properties", Information Processing Letters, 58 (4): 171–176, doi:10.1016/0020-0190(96)00050-6.
  • Chu, Frank Pok Man (2008), "A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements", Information Processing Letters, 107 (1): 7–12, doi:10.1016/j.ipl.2007.12.009.
  • Donnelly, Sam; Isaak, Garth (1999), "Hamiltonian powers in threshold and arborescent comparability graphs", Discrete Mathematics, 202 (1–3): 33–44, doi:10.1016/S0012-365X(98)00346-X
  • Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics, 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4.
  • Gurski, Frank (2006), "Characterizations for co-graphs defined by restricted NLC-width or clique-width operations", Discrete Mathematics, 306 (2): 271–277, doi:10.1016/j.disc.2005.11.014.
  • Nastos, James; Gao, Yong (2010), "A Novel Branching Strategy for Parameterized Graph Modification Problems", Lecture Notes in Computer Science, 6509: 332–346, arXiv:1006.3020.
  • Rotem, D. (1981), "Stack sortable permutations", Discrete Mathematics, 33 (2): 185–196, doi:10.1016/0012-365X(81)90165-5, MR 0599081.
  • Rubio-Montiel, C. (2015), "A new characterization of trivially perfect graphs", Electronic Journal of Graph Theory and Applications, 3 (1): 22–26, doi:10.5614/ejgta.2015.3.1.3.
  • Sharan, Roded (2002), "Graph modification problems and their applications to genomic research", PhD Thesis, Tel Aviv University.
  • Wolk, E. S. (1962), "The comparability graph of a tree", Proceedings of the American Mathematical Society (5 ed.), 13: 789–795, doi:10.1090/S0002-9939-1962-0172273-0.
  • Wolk, E. S. (1965), "A note on the comparability graph of a tree", Proceedings of the American Mathematical Society (1 ed.), 16: 17–20, doi:10.1090/S0002-9939-1965-0172274-5.
  • Yan, Jing-Ho; Chen, Jer-Jeong; Chang, Gerard J. (1996), "Quasi-threshold graphs", Discrete Applied Mathematics, 69 (3): 247–255, doi:10.1016/0166-218X(96)00094-7.

외부 링크