하이퍼그래프의 선 그래프

Line graph of a hypergraph

그래프 이론에서, 특히 하이퍼그래프 이론에서, L(H)로 표시된 하이퍼그래프 H의 선 그래프는 H의 성화 집합인 그래프인데, 해당 성화가 H에 비어 있지 않은 교차점을 가질 때 L(H)에 인접한 두 정점이 있다.즉, L(H)는 유한 집합의 계열을 교차 그래프로 나타낸 것이다.그래프의 선 그래프를 일반화한 것이다.

하이퍼그래프의 선 그래프에 대한 질문은 종종 그래프의 선 그래프에 대한 질문의 일반화다.예를 들어, 가장자리가 모두 k인 하이퍼그래프를 k-uniform이라고 한다. (2-uniform hypergraph는 그래프)하이퍼그래프 이론에서, 하이퍼그래프는 종종 k-uniform이라고 요구하는 것은 당연하다.모든 그래프는 일부 하이퍼그래프의 선 그래프지만, 고정된 에지 크기 k를 고려할 때 모든 그래프가 일부 K-형 하이퍼그래프의 선 그래프는 아니다.주요 문제는 각각의 k ≥ 3에 해당하는 것들을 특징짓는 것이다.

하이퍼그래프는 각 한 쌍의 혼합물이 최대 하나의 꼭지점에서 교차하는 경우 선형이다.모든 그래프는 선 그래프로, 일부 하이퍼그래프뿐만 아니라 일부 선형 하이퍼그래프(Verge 1989년)도 있다.

K-균일 하이퍼그래프의 선 그래프, k k 3

Beineke(1968)는 9개의 금지된 유도 하위 그래프 목록을 통해 그래프의 선 그래프를 특징으로 한다. (선 그래프에 대한 기사 참조)금지된 유도 하위그래프에 의한 특성화는 k ≥ 3에 대한 k-균일형 하이퍼그래프의 선 그래프로 알려져 있지 않으며, Lovász(1977)는 k = 3일 경우 유한 리스트에 의한 그러한 특성화가 없음을 보여주었다.

Krausz(1943)는 클라이크 커버 측면에서 그래프의 선 그래프를 특징으로 한다. (선 그래프 참조)어떤 k k 3에 대한 k-uniform hypergraphs의 선 그래프를 위한 Krausz 유형의 글로벌 특성화는 Berge(1989년)에 의해 주어졌다.

K-균일 선형 하이퍼그래프의 선 그래프, k ≥ 3

k ≥ 3에 대한 k-uniform 선형 하이퍼그래프의 선 그래프를 위한 Krausz 유형의 글로벌 특성화는 Naik 외 연구진(1980)이 제공했다.동시에 그들은 최소 정점도가 최소 69인 선형 3-균일 하이퍼그래프에 대해 금지된 유도 하위그래프의 유한 목록을 발견했다.메텔스키&티슈케비치(1997년)와 제이콥슨, 케즈디&레헬(1997)은 이를 19개로 개선했다.마침내 스쿰스, 스즈달' & 타이슈케비치(2005) 목표 CITREFSkums 2005는 이것을 16으로 줄였다.메텔스키&티슈케비치(1997)도 만약 k > 3이라면, 어떤 하한을 도에 두더라도 선형 k-균일 하이퍼그래프에 대해 그러한 유한 목록이 존재하지 않는다는 것을 증명했다.

선형 k-통일형 하이퍼그래프의 특성화를 찾기 어려운 것은 금지된 유도 하위그래프가 무한히 많기 때문이다.예를 들어, m > 0에 대해 연속 다이아몬드가 2도의 정점을 공유하도록 m 다이아몬드 그래프의 체인을 고려한다.k ≥ 3의 경우, 2도 또는 4도의 모든 꼭지점에 펜던트 가장자리를 추가하여 여기에 표시된 것처럼 Naik, Rao 및 Shrikhande 등(1980, 1982년)의 최소 금지 서브그래프 제품군 중 하나를 얻으십시오.이것은 다항식 인식의 존재나 Beineke의 선 그래프 그래프와 유사한 금지된 유도 서브그래프 특성화의 가능성을 배제하지 않는다.

Repeated diamond graph.svg

몇가지 흥미로운 characterizations 선형 k-uniform hypergraphs의 라인 그래프에 대한 다양한 작가들은 최소 학위나 G. 최소 가장자리 degre의 최소 끝 정도에 제약 조건 하에서(Naik, Rao&Shrikhande(알. 1980년 1982년, 야콥슨, Kézdy &, Lehel 1997년, Metelsky &, Tyshkevich 1997년 Zverovich 2004년)때문에 이용할 수 있다.e적어도 k3-2k2+1 in Naik et al.(1980)은 2k-3k2+1 in Jacobson, Kézdy & Lehel(1997), Zverovich(2004)로 축소되어 k ≥ 3에 대한 k-uniform 선형 하이퍼그래프의 선 그래프를 특성화한다.

최소 도(또는 최소 에지 도)에 제약 없이 선형 k-균일 하이퍼그래프의 선 그래프를 인식하는 복잡성은 알려져 있지 않다.k = 3 이상 최소 19도의 경우, 다항 시간(Jacobson, Kézdy & Lehel 1997, Metelsky & Tyshkevich 1997)에 인식이 가능하다.스쿰스, 스즈달' & 타이슈케비치(2005) CITREFSkums 2005는 최소도를 10으로 줄였다.

나이크 외, 자코보손 외, 메텔스키 외, 즈베로비치 등에는 많은 흥미로운 개방적인 문제와 추측이 있다.

불연속도 그래프

하이퍼그래프 H의 절연 그래프는 D(H)로 표시된 정점 세트가 H의 성화 집합인 그래프로, 해당 성화가 H에서 분리될 때 D(H)에 인접한 두 정점이 있다.[1]즉, D(H)는 L(H)의 보완 그래프인 것이다.D(H)의 클라이크는 L(H)의 독립 집합에 해당하며, 그 반대의 경우도 마찬가지다.

참조

  1. ^ Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.
  • Heydemann, M. C.; Sotteau, D. (1976), "Line graphs of hypergraphs II", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Colloq. Math. Soc. J. Bolyai, vol. 18, pp. 567–582, MR 0519291.
  • Krausz, J. (1943), "Démonstration nouvelle d'une théorème de Whitney sur les réseaux", Mat. Fiz. Lapok, 50: 75–85, MR 0018403. (헝가리어로 프랑스어 추상어로)
  • Lovász, L. (1977), "Problem 9", Beiträge zur Graphentheorie und deren Anwendungen, Vorgetragen auf dem Internationalen Kolloquium in Oberhof (DDR), p. 313.
  • Naik, Ranjan N.; Rao, S. B.; Shrikhande, S. S.; Singhi, N. M. (1980), "Intersection graphs of k-uniform hypergraphs", Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978), Annals of Discrete Mathematics, vol. 6, pp. 275–279, MR 0593539.
  • Skums, P. V.; Suzdal', S. V.; Tyshkevich, R. I. (2009), "Edge intersection of linear 3-uniform hypergraphs", Discrete Mathematics, 309: 3500–3517, doi:10.1016/j.disc.2007.12.082.