그래프의 사전 산물
Lexicographic product of graphs
그래프 이론에서 그래프 G와 H의 사전 편찬 제품 또는 (그래프) 구성 G ∙ H는 다음과 같은 그래프다.
- G ∙ H의 꼭지점 세트는 데카르트 제품 V(G) × V(H)이다.
- 어떤 두 꼭지점(u,v)과 (x,y)은 G의 x에 인접하거나 u = x와 v가 H의 y에 인접한 경우에만 G ∙ H에 인접한다.
두 그래프의 가장자리 관계가 순서 관계라면, 사전 편찬 제품의 가장자리 관계는 해당 사전 편찬 순서다.
사전 편찬 제품은 펠릭스 하우스도르프(1914년)가 처음 연구했다.파이겐바움&셰퍼(1986)가 보여주듯, 그래프가 사전 편찬 제품인지를 인식하는 문제는 그래프 이형성 문제와 복잡성이 동일하다.
특성.
사전 편찬 제품은 일반적으로 비협조적이다: G ∙ H ∙ H ∙ G. 단, (A + B) ∙ C = A ∙ C + B ∙ C.또한 C(G ∙ H) = C(G) ∙ C(H)의 보완에 관한 정체성을 만족시킨다.특히 두 개의 자기 완성 그래프의 사전 편찬 제품은 자기 완성형이다.
사전 편찬 제품의 독립성 번호는 그 요인으로부터 쉽게 계산할 수 있다(Geller & Stahl 1975).
- α(G ∙ H) = α(G)α(H).
사전 편찬 제품의 클라이크 수는 다음과 같이 곱할 수 있다.
- Ω(G ∙ H) = Ω(G)Ω(H)
사전 편찬 제품의 색도 번호는 B-폴드 색도 G와 같고, b는 색도 H와 동일하다.
- χ(G ∙ H) = χb(G), 여기서 b = χ(H)이다.
두 그래프의 사전 편찬 제품은 두 요인이 모두 완벽할 경우에만 완벽한 그래프다(Ravindra & Parthasarathy 1977).
참조
- Feigenbaum, J.; Schäffer, A. A. (1986), "Recognizing composite graphs is equivalent to testing graph isomorphism", SIAM Journal on Computing, 15 (2): 619–627, doi:10.1137/0215045, MR 0837609.
- Geller, D.; Stahl, S. (1975), "The chromatic number and other functions of the lexicographic product", Journal of Combinatorial Theory, Series B, 19: 87–95, doi:10.1016/0095-8956(75)90076-3, MR 0392645.
- Hausdorff, F. (1914), Grundzüge der Mengenlehre, Leipzig
- Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
- Ravindra, G.; Parthasarathy, K. R. (1977), "Perfect product graphs", Discrete Mathematics, 20 (2): 177–186, doi:10.1016/0012-365X(77)90056-5, hdl:10338.dmlcz/102469, MR 0491304.
