کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421254 | 684171 | 2011 | 5 صفحه PDF | دانلود رایگان |
For a graph GG with vertices v1,v2,…,vnv1,v2,…,vn, a simple set representation of GG is a family F={S1,S2,…,Sn}F={S1,S2,…,Sn} of distinct nonempty sets such that |Si∩Sj|=1|Si∩Sj|=1 if vivjvivj is an edge in GG, and |Si∩Sj|=0|Si∩Sj|=0 otherwise. Let S(F)=⋃i=1nSi, and let ωs(G) denote the minimum |S(F)| of a simple set representation FF of GG. If, for every two minimum simple set representations FF and F′F′ of GG, FF can be obtained from F′F′ by a bijective mapping from S(F′) to S(F), then GG is said to be ss-uniquely intersectable. In this paper, we are concerned with the ss-unique intersectability of diamond-free graphs, where a diamond is a K4K4 with one edge deleted. Moreover, for a diamond-free graph GG, we also derive a formula for computing ωs(G).
Journal: Discrete Applied Mathematics - Volume 159, Issue 8, 28 April 2011, Pages 774–778