مجموع ه‌هاي تفكيك‌ كننده رأس ‌ها در گراف‌ ها با كوچكترين اندازه

فرض كنيم G يك گراف ساده همبند با مجموعه رأس‌هاي V(G) و مجموعه يال‌هاي E(G)\ باشد. زيرمجموعه S=\{s_1, s_2,\ldots,s_l \} از رأس‌هاي گراف G يك مجموعه تفكيك‌كننده دوگانه براي گراف G ناميده مي‌شود، هرگاه براي هر دو رأس متمايز u و v از گراف G، عضوهاي x و y از S موجود باشند كه .d\left(u,\ x\right)-d\left(u,\ y\right)\neq \ d\left(v,\ x\right)\mathrm{-}d\left(v,\ y\right) اندازه كوچك‌ترين مجموعه تفكيك‌كننده دوگانه در گراف G را با {\psi} (G) نشان مي‌دهند. در اين مقاله، ضمن آشنايي با مفهوم و خواص {\psi} (G), برخي مجموعه‌هاي تفكيك‌كننده رأس‌ها با كوچكترين اندازه را براي گراف يالي L(C_n\circ{\overline{K}}_m) و گراف (C_n\circ{\overline{K}}_m)\square P_k محاسبه مي‌كنيم، كه در آن نمادهاي \circ و \square به‌ترتيب حاصل‌ضرب كرونا و حاصل‌ضرب دكارتي بين دو گراف را مشخص مي‌كنند. به‌ويژه، در پاسخ به مسأله مشخص نمودن گراف‌هاي G و H، كه براي آن‌ها تساوي {\psi}(G\square H)={\psi}(G)+{\psi}(H)-1 برقرار است \cite{15}، ما نشان مي‌دهيم كه اگر n\ge 3 و m,k\ge 2 عددهاي صحيح باشند، آن‌گاه {\psi} \left((C_n\circ{\overline{K}}_m)\square P_k\right) برابر است با .{\psi} \left(C_n\circ{\overline{K}}_m)+{\psi} (P_k\right)-1