Source author record

Debra Boutin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Determining Number and Cost of Generalized Mycielskian Graphs

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)$ .

preprint2021arXiv

Distinguishing Generalized Mycielskian Graphs

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.

preprint2021arXiv

Symmetry Parameters for Mycielskian Graphs

The Mycielskian construction, denoted $μ(G)$ , takes a finite simple graph $G$ to a larger graph with of the same clique number but larger chromatic number. The generalized Mycielskian construction, denoted $μ_t(G)$ , takes $G$ to a larger graph with the same chromatic number but with larger odd girth. In this chapter we look at symmetry parameters of $μ(G)$ and $μ_t(G)$ in terms of the same parameters of $G$ . These symmetry parameters include determining number, distinguishing number, and cost of distinguishing.

preprint2020arXiv

The Cost of 2-Distinguishing Hypercubes

A graph $G$ is said to be {\it $2$ -distinguishable} if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the labels. The minimum size of a label class, over all 2-distinguishing labelings, is called the {\it cost of $2$ -distinguishing}, denoted by $ρ(G)$ . For $n\geq 4$ the hypercubes $Q_n$ are 2-distinguishable, but the values for $ρ(Q_n)$ have been elusive, with only bounds and partial results previously known. This paper settles the question. The main result can be summarized as: for $n\geq 4$ , $ρ(Q_n) \in \{1+\lceil \log_2 n \rceil, 2 + \lceil \log_2 n\rceil\}$ . Exact values are be found using a recursive relationship involving a new parameter $ν_m$ , the smallest integer for which $ρ(Q_{ν_m})=m$ . The main result is\begin{gather*} 4\leq n \leq 12\Longrightarrow ρ(Q_n)=5, \text{ and } 5\leq m \leq 11 \Longrightarrow ν_m=4; \\ \text{ for } m\geq 6, ρ(Q_n) = m \iff 2^{m-2} - ν_{m-1} + 1 \leq n \leq 2^{m-1}-ν_m; \\ \text{ for } n\geq 5, ν_m = n \iff 2^{n-1} - ρ(Q_{n-1}) + 1\leq m \leq 2^{n}-ρ(Q_n).\end{gather*}

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Debra Boutin

Research overview

Is this your work?

4 publications

Determining Number and Cost of Generalized Mycielskian Graphs

Distinguishing Generalized Mycielskian Graphs

Symmetry Parameters for Mycielskian Graphs

The Cost of 2-Distinguishing Hypercubes

See the researcher in context

Building this map preview