연음 그래프

Dually chordal graph

그래프 이론의 수학적 영역에서, 최대 집단의 하이퍼그래프가 비대형이라면 비방향 그래프 G는 다변 화음이다.그 이름은 그래프가 만약 최대 패거리의 하이퍼그래프가 비대의 이중일 경우에만 화음이라는 사실에서 유래한다.원래 이러한 그래프는 최대 근거리 순서에 의해 정의되었으며 다양한 특성을 가지고 있다.[1]화음 그래프의 경우와는 달리, 다변 화음 그래프의 유도 하위 그래프는 반드시 다변 화음(수직 화음 그래프는 정확히 강 화음 그래프)이 아니며, 일반적으로 다변 화음 그래프는 완벽한 화음 그래프가 아니다.HT-그래프라는 이름 아래 dolly coordal graphs가 먼저 나타났다.[2]

특성화

연음 그래프는 화음 그래프의 편협 그래프,[3] 즉 화음 그래프의 최대 편협한 교차 그래프를 의미한다.

다음 속성은 동일하다.[4]

  • G는 최대 근린 주문량을 가지고 있다.
  • G의 스패닝 트리 T가 있어서 G의 어떤 최대 집단이 T의 하위 트리를 유도한다.
  • 닫힌 G의 동네 하이퍼그래프 N(G)은 비대형이다.
  • G의 최대 클라이크 하이퍼그래프는 비대형이다.
  • G는 비대의 2단면 그래프다.

닫힌 이웃 하이퍼그래프의 조건은 사각형이 화음이고 닫힌 이웃 하이퍼그래프가 헬리 속성을 갖는 경우에만 그래프가 일 년에 한 번 화음이라는 것을 암시한다.

De Caria & Gutierrez(2012년)에서는 분리기 속성의 관점에서 월별 코드 그래프를 특징으로 한다.Breshar(2003년)에서, 정확하게 일별 화음 그래프는 반복 입체 복합체의 그래프의 최대 하이퍼큐브의 교차 그래프임을 보여주었다.

이중 화음 그래프의 구조와 알고리즘 사용은 모스카리니(1993)에 의해 주어진다.이것들은 화음과 일 년에 한 번 화음을 나타내는 그래프들이다.

인식

연음 그래프는 선형 시간에서 인식할 수 있으며, 연음 그래프의 최대 근린 순서는 선형 시간에서 찾을 수 있다.[5]

문제의 복잡성

최대 독립형 집합, 최대 클라이크, 컬러링 및 클라이크 커버와 같은 일부 기본 문제는 연음 그래프의 경우 NP-완전 상태로 유지되지만, 최소 지배형 집합 문제와 스타이너 트리는 연음 그래프에서 효율적으로 해결할 수 있다(그러나 독립 지배는 NP-완전 상태로 유지됨).[6]트리 스패너에 대한 일별 코드 그래프 속성을 사용하려면 Brandstédt, Chepoi & Dragan(1999)을 참조하고, 일별 코드 그래프에서 효율적인 지배와 효율적인 에지 지배의 선형 시간 알고리즘은 Brandstet, Leitert & Rautenbach(2012)를 참조한다.

메모들

  1. ^ Brandstädt et al. (1993); Brandstädt, Chepoi & Dragan (1994); Brandstädt et al. (1994); Brandstädt et al. (1998); Brandstädt, Le & Spinrad (1999)
  2. ^ 드라간(1989); 드라간, 프리사카루 & 체포이(1992); 드라간(1993)
  3. ^ 구티에레스 & 오우비나(1996); 즈워크피터 & 본슈타인(1994)
  4. ^ Brandstédt 외 연구진(1993);Brandstédt, Chepoi & Dragan(1998);브란슈타트 외 연구진(1998); 드라간, 프리사카루 & 체포이(1992); 드라간(1993)
  5. ^ Brandstédt, Chepoi & Dragan(1998);드라간 (1989)
  6. ^ 브란슈타트, 체포이 & 드라간(1998), 드라간, 프리사카루 & 체포이(1992), 드라간(1993)

참조

  • Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1998), "The algorithmic use of hypertree structure and maximum neighborhood orderings", Discrete Applied Mathematics, 82: 43–77, doi:10.1016/s0166-218x(97)00125-x.
  • Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1999), "Distance approximating trees for chordal and dually chordal graphs", Journal of Algorithms, 30: 166–184, doi:10.1006/jagm.1998.0962.
  • Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1993), "Dually Chordal Graphs", Lecture Notes in Computer Science, 790: 237–251.
  • Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics, 11: 437–455, doi:10.1137/s0895480193253415.
  • 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.
  • Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), "Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs", Lecture Notes in Computer Science, 7676: 267–277, arXiv:1207.0953.
  • Brešar, Boštjan (2003), "Intersection graphs of maximal hypercubes", European Journal of Combinatorics, 24: 195–209, doi:10.1016/s0195-6698(02)00142-7.
  • De Caria, Pablo; Gutierrez, Marisa (2012), "On Minimal Vertex Separators of Dually Chordal Graphs: Properties and Characterizations", Discrete Applied Mathematics, 160: 2627–2635, doi:10.1016/j.dam.2012.02.022.
  • Dragan, Feodor (1989), Centers of Graphs and the Helly Property (in Russian), Ph.D. thesis, Moldova State University, Moldova.
  • Dragan, Feodor; Prisacaru, Chiril; Chepoi, Victor (1992), "Location problems in graphs and the Helly property (in Russian)", Discrete Math. (Moscow), 4: 67–73.
  • Dragan, Feodor (1993), "HT-graphs: centers, connected r-domination and Steiner trees", Comput. Sci. J. of Moldova (Kishinev), 1: 64–83.
  • Gutierrez, Marisa; Oubina, L. (1996), "Metric Characterizations of proper Interval Graphs and Tree-Clique Graphs", Journal of Graph Theory, 21: 199–205, doi:10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m.
  • McKee, Terry A.; McMorris, FR. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications.
  • Moscarini, Marina (1993), "Doubly Chordal Graphs, Steiner trees and connected domination", Networks, 23: 59–69, doi:10.1002/net.3230230108.
  • Szwarcfiter, Jayme L.; Bornstein, Claudson F. (1994), "Clique Graphs of Chordal and Path Graphs", SIAM Journal on Discrete Mathematics, 7: 331–336, CiteSeerX 10.1.1.52.521, doi:10.1137/s0895480191223191.