论文标题
区分广义的mycielskian图
Distinguishing Generalized Mycielskian Graphs
论文作者
论文摘要
图形$ g $是$ d $ - 如果有$ d $颜色的顶点的颜色，则只有琐碎的自动形态才能保留颜色类别。最小的$ d $是区分数字，$ \ permatatorname {dist}（g）$。图$ g $的mycielskian $μ（g）$是通过为每个顶点添加$ g $的每个顶点$ v_i $ of $ g $的shadow vertex $ u_i $和一个额外的顶点$ w $并添加边缘，以便$ n（u_i）〜= 〜n_g（v_i）〜n_g（v_i）广义的mycielskian $μ_t（g）$是一个带有$ t $ t $ shadow顶点的Mycielskian图，每个都在上方和下方的边缘。本文探讨了传统和广义迈西尔斯基图的区别数量。值得注意的是，如果$ g〜 \ neq〜k_1，〜k_2 $和$μ_t（g）$中的隔离顶点的数量最多是$ \ permatatorName {dist}（g）$，则$ \ operatotorname {dist} {dist}（μ__t（g）（g）（g））该结果证明并超过了Alikhani和Soltani的猜想。
A graph $G$ is $d$-distinguishable if there is a coloring of the vertices with $d$ colors so that only the trivial automorphism preserves the color classes. The smallest such $d$ is the distinguishing number, $\operatorname{Dist}(G)$. The Mycielskian $μ(G)$ of a graph $G$ is constructed by adding a shadow vertex $u_i$ for each vertex $v_i$ of $G$ and one additional vertex $w$ and adding edges so that $N(u_i)~=~N_G(v_i)~\cup~\{w\}$. The generalized Mycielskian $μ_t(G)$ is a Mycielskian graph with $t$ layers of shadow vertices, each with edges to layers above and below. This paper examines the distinguishing number of the traditional and generalized Mycielskian graphs. Notably, if $G~\neq ~K_1,~K_2$ and the number of isolated vertices in $μ_t(G)$ is at most $\operatorname{Dist}(G)$, then $\operatorname{Dist}(μ_t(G)) \le \operatorname{Dist}(G)$. This result proves and exceeds a conjecture of Alikhani and Soltani.
