Source author record

Lauren Keough

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

5works

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

An Extremal Problem for the Neighborhood Lights Out Game

Neighborhood Lights Out is a game played on graphs. Begin with a graph and a vertex labeling of the graph from the set $\{0,1,2,\dots, \ell-1\}$ for $\ell \in \mathbb{N}$ . The game is played by toggling vertices: when a vertex is toggled, that vertex and each of its neighbors has its label increased by $1$ (modulo $\ell$ ). The game is won when every vertex has label 0. For any $n\in\mathbb{N}$ it is clear that one cannot win the game on $K_n$ unless the initial labeling assigns all vertices the same label. Given that the $K_n$ has the maximum number of edges of any simple graph on $n$ vertices it is natural to ask how many edges can be in a graph so that the Neighborhood Lights Out game is winnable regardless of the initial labeling. We find all such extremal graphs on $n$ vertices that have $\binom{n}{2} - c$ edges for $c\leq \lceil\frac{n}{2}\rceil +3$ and all those that have minimum degree $n-3$ . The proofs of our results require us to introduce a new version of the Lights Out game that can be played given any square matrix.

preprint2016arXiv

The Avalanche Polynomial of a Graph

The (univariate) avalanche polynomial of a graph, introduced by Cori, Dartois and Rossin in 2006, captures the distribution of the length of (principal) avalanches in the abelian sandpile model. This polynomial has been used to show that the avalanche distribution in the sandpile model on a multiple wheel graph does not follow the expected power law function. In this article, we introduce the (multivariate) avalanche polynomial that enumerates the toppling sequences of all principal avalanches. This polynomial generalizes the univariate avalanche polynomial and encodes more information. In particular, the avalanche polynomial of a tree uniquely identifies the underlying tree. In this paper, the avalanche polynomial is characterized for trees, cycles, wheels, and complete graphs.

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.

Lauren Keough

Research overview

Is this your work?

5 publications

Determining Number and Cost of Generalized Mycielskian Graphs

Distinguishing Generalized Mycielskian Graphs

Symmetry Parameters for Mycielskian Graphs

An Extremal Problem for the Neighborhood Lights Out Game

The Avalanche Polynomial of a Graph

See the researcher in context

Building this map preview