풍차 그래프

Windmill graph
풍차 그래프
Windmill graph Wd(5,4).svg
Windmill 그래프 Wd(5,4).
정점(k-1)n+1
가장자리nk(k−1)/2
반지름1
지름2
둘레3 만약 k > 2
색수k
색도 지수n(k-1)
표기법Wd(k,n)
그래프 및 모수 표

그래프 이론의 수학적 분야에서 풍차 그래프 Wd(k,n)는 공유 범용 꼭지점에서 전체 그래프k K의 n 복사본을 결합하여 k ≥ 2와 n ≥ 2를 위해 구성한 비방향 그래프다.즉, 이 전체 그래프를 1개 표로 요약한 것이다.[1]

특성.

(k-1)n+1 정점과 nk(k-1)/2 에지,[2] 둘레 3(k > 2) 반지름 1과 직경 2가 있다.중심 정점이 관절점이기 때문에 정점 연결성 1이 있지만, 그것이 형성된 전체 그래프와 마찬가지로 (k-1) 에지로 연결되어 있다.그것은 사소한 완벽함과 블록 그래프다.

특례

시공별로는 풍차 그래프 Wd(3,n)가 우정 그래프 Fn, 풍차 그래프 Wd(2,n)가 별 그래프 Sn, 풍차 그래프 Wd(3,2)가 나비 그래프다.

라벨링 및 착색

풍차 그래프는 색도 번호 k와 색도 지수 n(k-1)을 가지고 있다.그것의 색도 다항식은 전체 그래프의 색도 을 형성하여 추론할 수 있으며, xform= 1 k - ( -i ). 과 같다.

풍차 그래프 Wd(k,n)는 k > 5이면 우아하지 않다는 것이 증명된다.[3] 1979년 버몬드는 Wd(4,n)가 모든 n ≥ 4에 대해 우아하다고 추측했다.[4]완벽한 차이점 패밀리와의 동등성을 통해, 이것은 n 1000 1000에 대해 증명되었다.[5] 버몬드, 코치히, 투르건은 k = 4와 n = 2 또는 n = 3일 때, 그리고 k = 5와 m = 2일 때 Wd(k,n)가 우아하지 않다는 것을 증명했다.[6]풍차 Wd(3,n)는 n ≡ 0 (mod 4) 또는 n ≡ 1 (mod 4)일 경우에만 우아하다.[7]

갤러리

작은 풍차 그래프.

참조

  1. ^ Gallian, J. A. (3 January 2007). "A dynamic survey of graph labeling" (PDF). Electronic Journal of Combinatorics. DS6: 1–58. MR 1668059.
  2. ^ Weisstein, Eric W. "Windmill Graph". MathWorld.
  3. ^ Koh, K. M.; Rogers, D. G.; Teo, H. K.; Yap, K. Y. (1980). "Graceful graphs: some further results and problems". Congressus Numerantium. 29: 559–571. MR 0608456.
  4. ^ Bermond, J.-C. (1979). "Graceful graphs, radio antennae and French windmills". In Wilson, Robin J. (ed.). Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978). Research notes in mathematics. Vol. 34. Pitman. pp. 18–37. ISBN 978-0273084358. MR 0587620. OCLC 757210583.
  5. ^ Ge, G.; Miao, Y.; Sun, X. (2010). "Perfect difference families, perfect difference matrices, and related combinatorial structures". Journal of Combinatorial Designs. 18 (6): 415–449. doi:10.1002/jcd.20259. MR 2743134.
  6. ^ Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978). "On a combinatorial problem of antennas in radioastronomy". In Hajnal, A.; Sos, Vera T. (eds.). Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I. Colloquia mathematica Societatis János Bolyai. Vol. 18. North-Holland. pp. 135–149. ISBN 978-0-444-85095-9. MR 0519261.
  7. ^ Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978). "Systèmes de triplets et différences associées". Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloques internationaux du Centre National de la Recherche Scientifique. Vol. 260. Éditions du Centre national de la recherche scientifique. pp. 35–38. ISBN 978-2-222-02070-7. MR 0539936.