مجموعه های تفکیک کننده راس ها در گراف ها با کوچکترین اندازه

فرض کنیم G یک گراف ساده همبند با مجموعه راس های V(G) و مجموعه یال های E(G)\ باشد. زیرمجموعه S=\{s_۱, s_۲,\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)-۱ برقرار است \cite{۱۵}، ما نشان می دهیم که اگر n\ge ۳ و m,k\ge ۲ عددهای صحیح باشند، آن گاه {\psi} \left((C_n\circ{\overline{K}}_m)\square P_k\right) برابر است با .{\psi} \left(C_n\circ{\overline{K}}_m)+{\psi} (P_k\right)-۱

Keywords:

مجموعه تفکیک کننده دوگانه , حاصل ضرب دکارتی , حاصل ضرب کرونا , گراف یالی