论文标题
确定广义Mycielskian图的数量和成本
Determining Number and Cost of Generalized Mycielskian Graphs
论文作者
论文摘要
如果每种$ g $的自动形态都是由其在$ S $上的操作而唯一确定的，则一组$ s $的顶点是图$ g $的确定集。 $ g $的最小确定集的大小称为其确定号码，$ det（g）$。如果有$ d $颜色的顶点着色，则图$ g $可与$ d $ distance condine，因此只有微不足道的自动形态保留了颜色类别。最小的$ d $是区分数字，$ dist（g）$。如果$ dist（g）= 2 $，则2-距离区分的成本，$ρ（g）$，是所有2级呈$ g $的颜色最小的颜色类的大小。图$ g $的mycielskian，$μ（g）$是通过添加shadow master vertex $ w $来构建的，对于每个顶点$ v_i $ g $的每个顶点$ v_i $ of $ g $添加了带有$ u_i $ in $ u_i $ in $ v _i $的$ v_i $ g $ v_i $ g y的$ u_i $ in COU $ v_i $ g y的$ u_i $ in COM $ v_i $ g w w。也就是说，$ n（u_i）= n_g（v_i）\ cup \ {w \} $。图$ g $的广义mycielskian $μ^{（t）}（g）$是带有$ t $ t $ shadow Vertices的Mycielskian Graph，每个图都在上方和下方的边缘，仅在$ w $上，仅$ w $仅与顶部阴影顶点相邻。如果没有相同的邻居的顶点，则图形是无与伦比的。本文探讨了确定数量的数量，并在相关时，是迈西尔斯基人的2差分成本，并普遍化了简单图形的迈西尔斯基人，而没有孤立的顶点。特别是，如果$ g \ neq k_2 $是双人的，没有孤立的顶点，则$ det（μ^{（t）}（g））= det（g）$。此外，如果$ det（g）= k \ geq 2 $和$ t \ ge k-1 $，则$ dist（μ^{（t）}（g））= 2 $和$ det（μ^{（t）}（g）（g））=ρ（μ^{（t）}（g）（g）（g）（g）（g））= k $。对于与双胞胎的$ g $，我们使用商图开发了一个关于双顶点的等效类别的框架，以在确定的Mycielskians数量上提供界限。此外，我们将$ det（μ^{（t）}（g））=（t {+} 1）det（g）$的$ det（μ^{（t）}（g））识别出图类。
A set $S$ of vertices is a determining set for a graph $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The size of a smallest determining set for $G$ is called its determining number, $Det(G)$. A graph $G$ is said to be $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, $Dist(G)$. If $Dist(G) = 2$, the cost of 2-distinguishing, $ρ(G)$, is the size of a smallest color class over all 2-distinguishing colorings of $G$. The Mycielskian, $μ(G)$, of a graph $G$ is constructed by adding a shadow master vertex $w$, and for each vertex $v_i$ of $G$ adding a shadow vertex $u_i$ with edges so that the neighborhood of $u_i$ in $μ(G)$ is the same as the neighborhood of $v_i$ in $G$ with the addition of $w$. That is, $N(u_i)=N_G(v_i)\cup\{w\}$. The generalized Mycielskian $μ^{(t)}(G)$ of a graph $G$ is a Mycielskian graph with $t$ layers of shadow vertices, each with edges to layers above and below, and $w$ only adjacent to the top layer of shadow vertices. A graph is twin-free if it has no pair of vertices with the same set of neighbors. This paper examines the determining number and, when relevant, the cost of 2-distinguishing for Mycielskians and generalized Mycielskians of simple graphs with no isolated vertices. In particular, if $G \neq K_2$ is twin-free with no isolated vertices, then $Det(μ^{(t)}(G)) = Det(G)$. Further, if $Det(G) = k \geq 2$ and $t \ge k-1$, then $Dist(μ^{(t)}(G))=2$, and $Det(μ^{(t)}(G)) = ρ(μ^{(t)}(G))= k$. For $G$ with twins, we develop a framework using quotient graphs with respect to equivalence classes of twin vertices to give bounds on the determining number of Mycielskians. Moreover, we identify classes of graphs with twins for which $Det(μ^{(t)}(G)) = (t{+}1) Det(G)$.
